stanford-oval/wikipedia huggingface dataset:
Windows 10
Các cập nhật và hỗ trợ

Không giống như các phiên bản trước của Windows, Windows Update không cho phép cài đặt các bản cập nhật một cách chọn lọc, và tất cả bản cập nhật (bao gồm bản vá lỗi, tính năng cập nhật và phần mềm trình điều khiển) được tải xuống và cài đặt tự động. Người dùng chỉ có thể quyết định liệu hệ thống của họ sẽ khởi động lại tự động để cài đặt bản cập nhật khi hệ thống không hoạt động hoặc được thông báo để lên lịch khởi động lại. Nếu một mạng không dây được chỉ định là "Metered" - một chức năng tự động giảm hoạt động của nền hệ điều hành để tiết kiệm giới hạn về việc sử dụng Internet, hầu hết các bản cập nhật sẽ không được tải xuống cho đến khi thiết bị được kết nối với một kết nối mạng không phải là "Metered". Redstone 2 cho phép các mạng có dây (Ethernet) được chỉ định làm đồng hồ, nhưng Windows vẫn có thể tải xuống một số cập nhật nhất định khi kết nối với một mạng metered.
Các bản cập nhật có thể gây ra sự tương thích hoặc các vấn đề khác. Microsoft đã phát triển một chương trình gỡ rối cho phép gỡ cài đặt các cập nhật này.
Windows Update cũng có thể sử dụng hệ thống peer to peer để phân phối các bản cập nhật. Theo mặc định, băng thông của người dùng được sử dụng để phân phối các bản cập nhật đã tải về trước đó cho người dùng khác, kết hợp với các máy chủ của Microsoft. Thay vào đó, người dùng có thể chọn chỉ sử dụng các cập nhật peer-to-peer trong mạng cục bộ của họ.
Bản phát hành RTM ban đầu của Windows 10 ("Windows 10, phát hành vào tháng 7 năm 2015") nhận được hỗ trợ chính thống trong 5 năm sau khi phát hành bản gốc, tiếp theo là 5 năm hỗ trợ kéo dài nhưng điều này tùy thuộc vào điều kiện. Chính sách hỗ trợ vòng đời hỗ trợ của Microsoft cho hệ điều hành lưu ý rằng "Bản cập nhật tích lũy, với mỗi bản cập nhật được xây dựng dựa trên tất cả các bản cập nhật trước nó", rằng "một thiết bị cần phải cài đặt bản cập nhật mới nhất vẫn được hỗ trợ" và khả năng của một thiết bị nhận được cập nhật trong tương lai sẽ phụ thuộc vào khả năng tương thích phần cứng, tính sẵn có của trình điều khiển và liệu thiết bị có nằm trong khoảng thời gian hỗ trợ của OEM - khía cạnh mới không được tính trong chính sách vòng đời cho các phiên bản trước đó. Chính sách này lần đầu tiên được triển khai vào năm 2017 để chặn các thiết bị Intel Clover Trail nhận Creators Update, vì Microsoft khẳng định rằng các bản cập nhật trong tương lai "yêu cầu hỗ trợ phần cứng bổ sung để cung cấp trải nghiệm tốt nhất có thể" và Intel không còn hỗ trợ hoặc trình điều khiển cho nền tảng. Microsoft tuyên bố rằng các thiết bị này sẽ không còn nhận được các bản cập nhật tính năng nữa, nhưng vẫn sẽ nhận được cập nhật bảo mật từ tháng 1 năm 2023.
Tiếp nhận > Tên gọi

Tuy nhiên, một thành viên trên diễn đàn Reddit, người tự xưng là một nhà phát triển của Microsoft, có câu trả lời thuyết phục hơn. Thực ra, Windows mới có tên Windows 10 để tránh nhầm lẫn nếu đặt tên là Windows 9. Bởi vì, họ muốn chỉ đọc một vài chữ đầu tiên của tên hệ điều hành đang dùng là có thể biết người dùng đang sử dụng phiên bản Windows nào, trong khi đó, nếu đặt tên cho hệ điều hành mới là Windows 9, họ có thể nhầm lẫn sang Windows 95 hoặc Windows 98.
Đó cũng như một dạng thảm họa y2k, vì các nhà lập trình không nghĩ rằng kế hoạch đặt tên cho Windows có thể vướng vào tình huống kiểu "Windows 9x", đồng thời các nhà lập trình cũng không muốn phải đưa thêm các đoạn mã mới để tránh tình thế nhầm lẫn "Windows 9" hay "Windows 95" hay "Windows 98". Tất nhiên, những suy đoán này chỉ là một lý thuyết chưa được chứng minh và Microsoft có thể cũng không bao giờ đưa ra lý do thực sự.
"Task View" là tính năng mới trên Windows 10, cho phép sử dụng nhiều không gian làm việc cùng một lúc.
Yêu cầu mở khóa Windows Hello trên Surface Pro 4 trong khi sử dụng Enpass (trình quản lý mật khẩu)
Bash đang chạy trên Windows 10
Chowdagonahalli, Nagamangala

| Chowdagonahalli |
| --- | --- |
—  Làng  —
 
Quốc gia:  Ấn Độ
Bang: Karnataka
Huyện: Mandya
Thành phố/thị trấn: Nagamangala
Múi giờ: IST (UTC+5:30)
Chowdagonahalli là một làng thuộc tehsil Nagamangala, huyện Mandya, bang Karnataka, Ấn Độ.
Campoletis oxylus

| Campoletis oxylus> Phân loại khoa học |
| --- | --- |
Giới (regnum): Animalia
Ngành (phylum): Arthropoda
Lớp (class): Insecta
Bộ (ordo): Hymenoptera
Họ (familia): Ichneumonidae
Chi (genus): Campoletis
Loài (species): C. oxylus
Danh pháp hai phần
Campoletis oxylus (Cresson, 1864) 
Campoletis oxylus là một loài tò vò trong họ Ichneumonidae.
Chú thích

↑  Bisby, F.A.; Roskov, Y.R.; Orrell, T.M.; Nicolson, D.; Paglinawan, L.E.; Bailly, N.; Kirk, P.M.; Bourgoin, T.; Baillargeon, G.; Ouvrard, D. (2011). “Species 2000 & ITIS Catalogue of Life: 2011 Annual Checklist”. Species 2000: Reading, UK. Truy cập ngày 22 tháng 6 năm 2014.
10900 Folkner

10900 Folkner (tên chỉ định: 1997 WF21) là một tiểu hành tinh vành đai chính. Nó được phát hiện bởi Takao Kobayashi ở Ōizumi Observatory ở Ōizumi, Gunma Prefecture, Nhật Bản, ngày 30 tháng 11 năm 1997. Nó được đặt theo tên William Folkner, a scientist ở Jet Propulsion Laboratory.
Campoletis mitis

| Campoletis mitis> Phân loại khoa học |
| --- | --- |
Giới (regnum): Animalia
Ngành (phylum): Arthropoda
Lớp (class): Insecta
Bộ (ordo): Hymenoptera
Họ (familia): Ichneumonidae
Chi (genus): Campoletis
Loài (species): C. mitis
Danh pháp hai phần
Campoletis mitis (Holmgren, 1860) 
Campoletis mitis là một loài tò vò trong họ Ichneumonidae.
Chú thích

↑  Bisby, F.A.; Roskov, Y.R.; Orrell, T.M.; Nicolson, D.; Paglinawan, L.E.; Bailly, N.; Kirk, P.M.; Bourgoin, T.; Baillargeon, G.; Ouvrard, D. (2011). “Species 2000 & ITIS Catalogue of Life: 2011 Annual Checklist”. Species 2000: Reading, UK. Truy cập ngày 22 tháng 6 năm 2014.
Attikuppe, Kanakapura

| Attikuppe |
| --- | --- |
—  Làng  —
 
Quốc gia:  Ấn Độ
Bang: Karnataka
Huyện: Ramanagara
Thành phố/thị trấn: Kanakapura
Múi giờ: IST (UTC+5:30)
Attikuppe là một làng thuộc tehsil Kanakapura, huyện Ramanagara, bang Karnataka, Ấn Độ.
Túc nam

Túc Nam (chữ Hán:肃男) là thụy hiệu của một số vị nam tước trong lịch sử các vương triều phong kiến Trung Quốc.
Danh sách

Đông Tấn Nam Thành Túc Nam Lưu Hoài Thận (thời Lưu Tống được tiến phong làm Nam Thành Túc Hầu)
Lưu Tống Chung Vũ Túc Nam (hoặc Tương Nam Túc Nam) Lã An Quốc (thời Nam Tề được tiến phong làm Tương Nam Túc Hầu)
Bắc Ngụy Nhạc Lăng Văn Túc Nam Thôi Sĩ Thái
Lasioglossum fulvitarse

| Lasioglossum fulvitarse> Phân loại khoa học |
| --- | --- |
Giới (regnum): Animalia
Ngành (phylum): Arthropoda
Lớp (class): Insecta
Bộ (ordo): Hymenoptera
Họ (familia): Halictidae
Phân họ (subfamilia): Halictinae
Tông (tribus): Halictini
Chi (genus): Lasioglossum
Loài (species): L. fulvitarse
Danh pháp hai phần
Lasioglossum fulvitarse (Morawitz, 1876) 
Lasioglossum fulvitarse là một loài Hymenoptera trong họ Halictidae. Loài này được Morawitz mô tả khoa học năm 1876.
Chú thích

↑  (2008) Integrated Taxonomic Information System (ITIS) Bee Checklist 3 oktober 2008
1091 Spiraea

| Khám phá |
| --- | --- |
Khám phá bởi: Karl Wilhelm Reinmuth
Ngày phát hiện: 26 tháng 2 năm 1928
Tên định danh
Đặt tên theo: Spiraea
Tên thay thế: 1928 DT
Danh mục tiểu hành tinh: Vành đai chính (Cybele)
Đặc trưng quỹ đạo
Kỷ nguyên JD 2445600.5
Cận điểm quỹ đạo: 3.2609316 AU
Độ lệch tâm: 0.0483983
Độ nghiêng quỹ đạo: 1.1596171°
Kinh độ điểm mọc: 80.3616426°
Góc cận điểm: 21.0099365°
Đặc trưng vật lý
Kích thước: 36 km
Suất phản chiếu: 0.15
Cấp sao tuyệt đối (H): 10.60
 
1091 Spiraea là một tiểu hành tinh bay quanh Mặt Trời. Ban đầu nó có tên là 1928 DT. The numerical designation indicates this was the 1091st asteroid discovered.
Peperomia trifolia

| Peperomia trifolia> Phân loại khoa học |
| --- | --- |
Giới (regnum): Plantae
(không phân hạng): Angiospermae
(không phân hạng): Magnoliidae
Bộ (ordo): Piperales
Họ (familia): Piperaceae
Chi (genus): Peperomia
Loài (species): P. trifolia
Danh pháp hai phần
Peperomia trifolia (L.) A. Dietr., 1831 
Peperomia trifolia là một loài thực vật có hoa trong họ Hồ tiêu. Loài này được (L.) A. Dietr. miêu tả khoa học đầu tiên năm 1831.
Chú thích

↑  The Plant List (2010). “Peperomia trifolia”. Truy cập ngày 9 tháng 6 năm 2013.
Neesiochloa barbata

| Neesiochloa barbata> Phân loại khoa học |
| --- | --- |
Giới (regnum): Plantae
(không phân hạng): Angiospermae
(không phân hạng): Monocots
Bộ (ordo): Poales
Họ (familia): Poaceae
Chi (genus): Neesiochloa
Loài (species): N. barbata
Danh pháp hai phần
Neesiochloa barbata (Nees) Pilg. 
Neesiochloa barbata là một loài thực vật có hoa trong họ Hòa thảo. Loài này được (Nees) Pilg. mô tả khoa học đầu tiên năm 1940.
Chú thích

↑  The Plant List (2010). “Neesiochloa barbata”. Truy cập ngày 6 tháng 6 năm 2013.
Nautilus (tàu ngầm)

Nautilus.
Nautilus là một tàu ngầm hư cấu có thuyền trưởng là Nemo trong các tiểu thuyết của nhà văn Jules Verne Hai vạn dặm dưới biển và Hòn đảo bí mật (1874). Verne đã đặt tên Nautilus theo tàu ngầm Nautilus (1800) có thật của Robert Fulton. Ba năm trước khi viết cuốn tiểu thuyết của mình, Jules Verne cũng nghiên cứu một mô hình tàu ngầm Hải quân Pháp mới được phát triển] Plongeur tại 1867 Exposition Universelle 1867, mà đã truyền cảm hứng cho ông trong việc xác định Nautilus.. "Nautilus" trở thành hiện thân của tiến bộ kỹ thuật, và tên gọi này đã trở thành phổ biến nhất trong số các tàu ngầm. Bởi vì ông, J. Verne đã được biết đến như là "cha của tàu ngầm". Để vinh danh "Nautilus" được dùng để đặt tên nhiều thiết bị điện tử, máy tính, tàu không gian, nhà hàng, khách sạn, ban nhạc rock, câu lạc bộ thể thao..
Xuất hiện trong các tác phẩm khác

Ngoài những lần xuất hiện trong Hai vạn dặm dưới biển và Hòn đảo bí ẩn, Nautilus và Thuyền trưởng Nemo đã xuất hiện trong nhiều tác phẩm khác.
Trong bộ phim chuyển thể từ cuốn Hai vạn dặm dưới biển năm 1954 và trong Sự trở lại của thuyền trưởng Nemo, có ý kiến cho rằng Nautilus được cung cấp năng lượng từ năng lượng hạt nhân (do chính Nemo khám phá ra), và Nemo sử dụng năng lượng tương tự để phá hủy Vulcania, hòn đảo căn cứ của Nautilus.
Trong bộ phim năm 1969 Thuyền trưởng Nemo và Thành phố dưới nước, Nautilus và tàu chị em của nó là Nautilus II được miêu tả là những con tàu giống như cá đuối được trang bị máy móc.
Trong Captain Nemo: The Fantastic History of a Dark Genius của Kevin J. Anderson, Nautilus xuất hiện như một chiếc tàu ngầm thực sự, có hình dáng giống như điếu xì gà trong tiểu thuyết, do Nemo chế tạo cho Đế chế Ottoman.
Trong The League of Extraordinary Gentlemen của Stephen Norrington, "Nautilus" xuất hiện như một chiếc tàu ngầm thực sự có màu trắng bạc.
Hình ảnh

Phòng khách của Nautilus.
Phòng của thuyền trưởng Nemo trong Nautilus.
Thư viện trên Nautilus.
Phòng máy của Nautilus.
Cửa sổ chính của Nautilus.
Đèn chiếu sáng của Nautilus
Thuyền trưởng Nemo trong lúc hấp hối trên tàu Nautilus
Thuyền trưởng Nemo giải thích cách ông chế tạo chiếc Nautilus, một hình ảnh trong "Hai vạn dặm dưới đáy biển" (1866-69) của Jules Verne do George Roux vẽ.
Mô hình tàu ngầm Plongeur
Nautilus, minh họa trong Hòn đảo bí mật
Bài toán người bán hàng

Nếu người bán hàng xuất phát từ điểm A, và nếu khoảng cách giữa hai điểm bất kì được biết thì đâu là đường đi ngắn nhất mà người bán hàng có thể thực hiện được sao cho đi hết tất cả các điểm mỗi điểm một lần để quay về lại điểm A ban đầu?
Bài toán người bán hàng (tiếng Anh: travelling salesman problem - TSP) là một bài toán NP-khó thuộc thể loại tối ưu rời rạc hay tổ hợp được nghiên cứu trong vận trù học hoặc lý thuyết khoa học máy tính. Bài toán được phát biểu như sau. Cho trước một danh sách các thành phố và khoảng cách giữa chúng, tìm chu trình ngắn nhất thăm mỗi thành phố đúng một lần.
Bài toán được nêu ra lần đầu tiên năm 1930 và là một trong những bài toán được nghiên cứu sâu nhất trong tối ưu hóa. Nó thường được dùng làm thước đo cho nhiều phương pháp tối ưu hóa. Mặc dù bài toán rất khó giải trong trường hợp tổng quát, có nhiều phương pháp giải chính xác cũng như heuristic đã được tìm ra để giải quyết một số trường hợp có tới hàng chục nghìn thành phố.
Ngay trong hình thức phát biểu đơn giản nhất, bài toán TSP đã có nhiều ứng dụng trong lập kế hoạch, hậu cần, cũng như thiết kế vi mạch.
Trong lý thuyết độ phức tạp tính toán, phiên bản quyết định của TSP (cho trước độ dài L, xác định xem có tồn tại hay không một chu trình đi qua mỗi đỉnh đúng một lần và có độ dài nhỏ hơn L) thuộc lớp NP-đầy đủ. Do đó, có nhiều khả năng là thời gian xấu nhất của bất kì thuật toán nào cho TSP đều tăng theo cấp số nhân với số thành phố.
TSP có một vài ứng dụng thậm chí trong dạng thức nguyên thủy của nó như lập kế hoạch, logistic, và sản xuất các microchip. Thay đổi đi chút ít nó xuất hiện như một bài toán con trong rất nhiều lĩnh vực như việc phân tích gen trong sinh học. Trong những ứng dụng này, khái niệm thành phố có thể thay đổi thành khách hàng, các điểm hàn trên bảng mạch, các mảnh DNA trong gen, và khái niệm khoảng cách có thể biểu diễn bởi thời gian du lịch hay giá thành, hay giống như sự so sánh giữa các mảnh DNA với nhau. Trong nhiều ứng dụng, các hạn chế truyền thống như giới hạn tài nguyên hay giới hạn thời gian thậm chí còn làm cho bài toán trở nên khó hơn.
Trong lý thuyết của độ phức tạp tính toán, phiên bản quyết định của bài toán TSP thuộc lớp NP-đầy đủ. Vì vậy không có giải thuật hiệu quả nào cho việc giải bài toán TSP. Hay nói cách khác, giống như thời gian chạy xấu nhất cho bất ký giải thuật nào cho bài toán TSP tăng theo hàm mũ với số lượng thành phố, vì vậy thậm chí nhiều trường hợp với vài trăm thành phố cũng đã mất vài năm CPU để giải một cách chính xác.
Lịch sử

Nguồn gốc của bài toán người bán hàng vẫn chưa được biết rõ. Một cuốn sổ tay dành cho người bán hàng xuất bản năm 1832 có đề cập đến bài toán này và có ví dụ cho chu trình trong nước Đức và Thụy Sĩ, nhưng không chứa bất kì nội dung toán học nào.
Bài toán người bán hàng được định nghĩa trong thế kỉ 19 bởi nhà toán học Ireland William Rowan Hamilton và nhà toán học Anh Thomas Kirkman. Trò chơi Icosa của Hamilton là một trò chơi giải trí dựa trên việc tìm kiếm chu trình Hamilton. Trường hợp tổng quát của TSP có thể được nghiên cứu lần đầu tiên bởi các nhà toán học ở Vienna và Harvard trong những năm 1930, đặc biệt là Karl Menger, người đã định nghĩa bài toán, xem xét thuật toán hiển nhiên nhất cho bài toán, và phát hiện ra thuật toán láng giềng gần nhất là không tối ưu.
Hassler Whitney ở đại học Princeton đưa ra tên bài toán người bán hàng ngay sau đó.
Trong những năm 1950 và 1960, bài toán trở nên phổ biến trong giới nghiên cứu khoa học ở châu Âu và Mỹ. George Dantzig, Delbert Ray Fulkerson và Selmer M. Johnson ở công ty RAND tại Santa Monica đã có đóng góp quan trọng cho bài toán này, biểu diễn bài toán dưới dạng quy hoạch nguyên và đưa ra phương pháp mặt phẳng cắt để tìm ra lời giải. Với phương pháp mới này, họ đã giải được tối ưu một trường hợp có 49 thành phố bằng cách xây dựng một chu trình và chứng minh rằng không có chu trình nào ngắn hơn. Trong những thập niên tiếp theo, bài toán được nghiên cứu bởi nhiều nhà nghiên cứu trong các lĩnh vực toán học, khoa học máy tính, hóa học, vật lý, và các ngành khác.
Năm 1972, Richard M. Karp chứng minh rằng bài toán chu trình Hamilton là NP-đầy đủ, kéo theo bài toán TSP cũng là NP-đầy đủ. Đây là một lý giải toán học cho sự khó khăn trong việc tìm kiếm chu trình ngắn nhất.
Một bước tiến lớn được thực hiện cuối thập niên 1970 và 1980 khi Grötschel, Padberg, Rinaldi và cộng sự đã giải được những trường hợp lên tới 2392 thành phố, sử dụng phương pháp mặt phẳng cắt và nhánh cận.
Trong thập niên 1990, Applegate, Bixby, Chvátal, và Cook phát triển một chương trình mang tên Concorde giải được nhiều trường hợp có độ lớn kỉ lục hiện nay. Gerhard Reinelt xuất bản một bộ dữ liệu các trường hợp có độ khó khác nhau mang tên TSPLIB năm 1991, và nó đã được sử dụng bởi nhiều nhóm nghiên cứu để so sánh kết quả. Năm 2005, Cook và cộng sự đã giải được một trường hợp có 33810 thành phố, xuất phát từ một bài toán thiết kế vi mạch. Đây là trường hợp lớn nhất đã được giải trong TSPLIB. Trong nhiều trường hợp khác với hàng triệu thành phố, người ta đã tìm được lời giải với sai số không quá 1% so với lời giải tối ưu.
Phát biểu

Có một người giao hàng cần đi giao hàng tại n thành phố. Anh ta xuất phát từ một thành phố nào đó, đi qua các thành phố khác để giao hàng và trở về thành phố ban đầu. Mỗi thành phố chỉ đến một lần, và khoảng cách từ một thành phố đến các thành phố khác đã được biết trước. Hãy tìm một chu trình (một đường đi khép kín thỏa mãn điều kiện trên) sao cho tổng độ dài các cạnh là nhỏ nhất.
Phát biểu > Dưới dạng đồ thị

Bài toán người bán hàng có thể được mô hình hoá như một đồ thị vô hướng có trọng số, trong đó mỗi thành phố là một đỉnh của đồ thị còn đường đi giữa các thành phố là mỗi cạnh. Khoảng cách giữa hai thành phố là độ dài cạnh. Đây là vấn đề cực tiểu hoá với điểm đầu và điểm cuối là cùng một đỉnh sau khi thăm hết các đỉnh còn lại đúng một lần. Mô hình này thường là một đồ thị đầy đủ (giữa mỗi cặp đỉnh đều có cạnh). Nếu không có đường giữa hai thành phố thì có thể thêm một cạnh với độ dài đủ lớn vào đồ thị mà không ảnh hưởng đến kết quả tối ưu sau cùng.
Phát biểu > Đối xứng và bất đối xứng

Trong bài toán TSP đối xứng, khoảng cách giữa hai thành phố là không đổi dù đi theo chiều nào. Như vậy đồ thị trong bài toán này là đồ thị vô hướng. Việc đối xứng này làm giảm đi một nửa số lời giải có thể. Trong khi đó, với bài toán TSP bất đối xứng thì đường đi giữa hai thành phố có thể chỉ một chiều hoặc có độ dài khác nhau giữa mỗi chiều, tạo nên đồ thị có hướng. Các tai nạn giao thông, đường một chiều hay phí hàng không giữa các thành phố với phí điểm xuất phát và điểm đến khác nhau là những ví dụ về sự bất đối xứng.
Tìm kiếm lời giải

Cũng như các bài toán NP-khó khác, có các hướng sau đây để tiếp cận bài toán người bán hàng.
Thiết kế thuật toán tìm kiếm lời giải tối ưu (thường hoạt động hiệu quả cho những trường hợp nhỏ).
Thiết kế thuật toán heuristic để tìm những lời giải tốt nhưng không nhất thiết tối ưu.
Thiết kế thuật toán xấp xỉ để tìm những lời giải không quá lớn so với lời giải tối ưu.
Giải quyết các trường hợp đặc biệt.
Tìm kiếm lời giải > Ví dụ minh họa

Sử dụng thuật toán láng giềng gần nhất (tiếng Anh: nearest neighbour algorithm)

Các bước của thuật toán:
Bước 1: Chọn một đỉnh bắt đầu V.
Bước 2: Từ đỉnh hiện hành chọn cạnh nối có chiều dài nhỏ nhất đến các đỉnh chưa đến. Đánh dấu đã đến đỉnh vừa chọn.
Bước 3: Nếu còn đỉnh chưa đến thì quay lại bước 2.
Bước 4: Quay lại đỉnh V.
Bài toán có năm thành phố với khoảng cách giữa các thành phố được tính bằng km. Sử dụng thuật toán láng giềng gần nhất, bắt đầu lần lượt từ mỗi đỉnh, tìm đường đi thích hợp cho người bán hàng, cửa hàng đặt tại A và cần đi qua tất cả thành phố còn lại.
Từ A, đỉnh gần nhất là C, chiều dài AC = 8
Từ C, đỉnh chưa viếng thăm gần nhất là E, CE = 4
Từ E, đỉnh chưa viếng thăm gần nhất là B, EB = 15
Từ B, đỉnh chưa viếng thăm gần nhất là D, BD = 10
Không còn đỉnh chưa viếng thăm, vì vậy quay về A, DA = 14
Tổng chi phí ACEBDA là 8 + 4 + 15 + 10 + 14 = 51
Lặp lại bắt đầu với những đỉnh khác:
| 0 | 1 | 2 |
| --- | --- | --- |
| Đỉnh bắt đầu | Đường đi | Tổng chiều dài |
| A | ACEBDA | 51 |
| B | BACEDB | 50 |
| C | CEABDC | 45 |
| D | DCEABD | 45 |
| E | ECABDE | 50 |
| E | ECDBAE | 45 |
Có ba đường đi có chiều dài 45 km là giống nhau. Một nhân viên bán hàng có cửa hàng tại A, đường đi tốt nhất tìm ra bởi thuật toán láng giềng gần nhất là ABDCEA = 45 km
Tìm kiếm lời giải > Công thức

Công thức: Bước đầu tiên để giải quyết trường hợp của TSPs lớn phải để tìm một công thức toán học tốt của vấn đề. Trong trường hợp của các vấn đề nhân viên bán hàng đi du lịch, các cấu trúc toán học là một đồ thị, ở mỗi thành phố được biểu thị bằng một điểm (hoặc nút) và dòng được rút ra kết nối hai nút (gọi là vòng cung hoặc cạnh). Liên kết với mỗi dòng là một khoảng cách (hoặc chi phí). Khi nhân viên bán hàng có thể nhận được từ mỗi thành phố để mọi thành phố khác trực tiếp, sau đó đồ thị được cho là hoàn chỉnh. Một chuyến đi vòng quanh những thành phố tương ứng với một số tập hợp con của các dòng, và được gọi là một tour du lịch hoặc một chu trình Hamilton (Đường đi Hamilton) trong lý thuyết đồ thị. Chiều dài của một tour du lịch là tổng độ dài của các đường trong chuyến đi vòng quanh.
Tùy thuộc vào có hay không sự chỉ đạo, trong đó một cạnh của đồ thị là đi qua các vấn đề, ​​một trong những phân biệt đối xứng từ đối xứng đi vấn đề nhân viên bán hàng. Xây dựng các bất đối xứng TSP trên m thành phố, một trong những giới thiệu không-một biến
và do thực tế là tất cả các nút của đồ thị phải có đúng một cạnh chỉ tay về phía nó và một trong những chỉ đi từ nó, có được một vấn đề chuyển nhượng cổ điển. Những khó khăn này một mình là không đủ vì công thức này sẽ cho phép "subtours", có nghĩa là, nó sẽ cho phép các vòng phân chia xảy ra. Vì lý do này, một mô hình thích hợp của các vấn đề đi du lịch nhân viên bán hàng không đối xứng phải loại bỏ những subtours từ xem xét việc bổ sung "subtour loại bỏ" hạn chế. Vấn đề sau đó trở thành
nơi mà K là bất kỳ tập hợp con thích hợp khác rỗng trong những thành phố 1,..., m. Chi phí c ij được phép khác với chi phí c ji. Lưu ý rằng có m (m-1) không-một biến trong công thức này.
Xây dựng các đối xứng đi vấn đề nhân viên bán hàng, người ta ghi nhận rằng hướng đi qua là không đáng kể, do đó c ij = c ji. Từ hướng không quan trọng bây giờ, người ta có thể xem xét các đồ thị, nơi chỉ có một vòng cung (vô hướng) giữa hai nút. Vì vậy, chúng tôi cho x j e { 0,1 } là biến quyết định nơi j chạy qua tất cả các cạnh E của đồ thị vô hướng và c j là chi phí đi cạnh đó. Để tìm một tour du lịch trong biểu đồ này, người ta phải chọn một tập hợp con của các cạnh như vậy mà tất cả các nút được chứa trong hai chính xác của các cạnh được lựa chọn. Như vậy, vấn đề có thể được xây dựng như một vấn đề 2 khớp trong đồ thị G v có m (m-1) / 2 không-một biến, tức là một nửa số lượng các công tác xây dựng trước đó. Như trong trường hợp bất đối xứng, subtours phải được loại bỏ thông qua hạn chế loại bỏ subtour. Vấn đề do đó có thể được xây dựng như:
Tìm kiếm lời giải > Độ phức tạp tính toán

Phiên bản quyết định của bài toán người bán hàng là NP-đầy đủ. Ngay cả khi khoảng cách giữa các thành phố là khoảng cách Euclide, bài toán vẫn là NP-khó.
- Với n thành phố thì có: 1/2 × (n − 1)! đường đi.
+ Giả sử n = 16 =>> 1/2 * 15! = 6.54 ×1011 đường đi =>> Số đường đi quá lớn.
Tìm kiếm lời giải > Độ phức tạp tính toán > Độ phức tạp của tính xấp xỉ

Trong trường hợp tổng quát, bài toán người bán hàng là NPO-đầy đủ. Khi các khoảng cách thỏa mãn bất đẳng thức tam giác và đối xứng, bài toán là APX-đầy đủ và thuật toán Christofides có thể tìm lời giải xấp xỉ không quá 1,5 lần lời giải tối ưu.
Khi các khoảng cách là bất đối xứng nhưng thỏa mãn bất đẳng thức tam giác, thuật toán tốt nhất hiện nay đạt tỉ lệ xấp xỉ  O(\log n/\log \log n).
Tìm kiếm lời giải > Cải thiện ngẫu nhiên

Tối ưu hóa chuỗi Markov thuật toán sử dụng để phát tìm kiếm địa phương phụ các thuật toán có thể tìm thấy một con đường rất gần với các tuyến đường tối ưu cho 700 đến 800 thành phố.
TSP là một chuẩn mực cho nhiều chẩn đoán chung đưa ra để tối ưu hóa tổ hợp như các thuật toán di truyền, tìm kiếm Tabu, kiến thuộc địa tối ưu hóa và các phương pháp entropy chéo.
Tìm kiếm lời giải > Cải thiện ngẫu nhiên > Không gian Euclide

Khi các thành phố là các điểm trong không gian Euclide, bài toán vẫn là NP-đầy đủ. Tuy nhiên, khi số chiều của không gian là hằng số, có thuật toán để tìm lời giải xấp xỉ với độ chính xác bất kì. Cụ thể hơn, với bất kì  \epsilon >0, và  d là số chiều của không gian Euclide, có thuật toán chạy trong thời gian  ({\sqrt {d}}/\epsilon )^{O(d({\sqrt {d}}/\epsilon )^{d-1})}n+O(dn\log n) và tìm ra lời giải không quá  1+\epsilon  lời giải tối ưu.
TSP đối xứng với bốn thành phố
Tổng chi phí ACEBDA là 8+4+15+10+14 = 51