旅行推銷員問題多年來存在的歷史是什麼?
Context:旅行銷售員問題的起源尚不清楚. 一本1832年出版的旅遊商人的手冊提到了這個問題,幷包含了德國和瑞士的示例遊覽,但沒有包含數學處理.   威廉·羅恩·漢密爾頓 在19世紀由愛爾蘭數學家威廉·羅恩·漢密爾頓和英國數學家托馬斯·柯克曼數學上提出. 漢密爾頓的Icosian遊戲是一個基於找到漢密爾頓週期的休<unk>拼圖. TSP的一般形式似乎首先由數學家在1930年代在維也納和哈佛研究,特別是由卡爾·門格爾,他定義了這個問題,考慮了明顯的粗暴力演算法,並觀察了最近鄰方啟發式的非最佳性:  我們用信使問題來表示 (因為實際上這個問題應該由每個郵遞員解決,無論如何也由許多旅行者解決) 任務是為有限的許多點找到連線點的最短路線,其對距離是已知的. 當然,這個問題可以通過有限的試驗來解決. 沒有規則可以使試驗數低於給定點的排列數. 從起點到最接近的點,然後到最接近的點等等,一般來說不會產生最短的路線.  它在20世紀30年代由梅里爾·M·弗洛德 (Merrill M. Flood) 首次在數學上考慮,當時他正在尋求解決一項校車路線問題. 普林斯頓大學的哈斯勒·惠特尼對這個問題產生了興趣, 最早使用"旅行銷售員問題"的出版物是朱莉<unk>·羅賓遜在1949年的蘭德公司報告"關於哈密爾頓遊戲 (旅行銷售員問題) ".  在20世紀50年代和60年代,在歐洲和美國的科學界,這個問題越來越受歡迎,因為聖莫尼卡的蘭德公司為解決這個問題的步驟提供了獎勵. 來自蘭德公司的喬治·丹齊格 (George Dantzig),德爾伯特·雷·富爾克森 (Delbert Ray Fulkerson) 和塞爾默·M·約翰遜 (Selmer M. Johnson) 作出了顯著的貢獻,他們將這個問題表達為一個整數線性程式,併為其解決方案開發了切割平面方法. 他們寫了一篇被認為是該主題的開創性論文, 通過使用這些新方法, 他們通過構建一個旅遊, 證明沒有其他旅遊可以更短, 解決了49個城市的例項. 然而,Dantzig,Fulkerson和Johnson推測,如果給出一個接近最佳的解決方案,我們可能能夠通過新增少量額外的不等式 (切斷) 來找到最佳性或證明最佳性. 他們用這個想法來解決他們最初的49個城市問題. 他們發現他們只需要26個削減來解決49個城市的問題. 雖然這篇論文並沒有給出對TSP問題的演算法方法,但它所包含的想法對於後來為TSP建立精確的解決方法是不可或缺的,儘管需要15年才能找到建立這些切割的演算法方法. 除了切割平面的方法外,Dantzig,Fulkerson和Johnson也許是第一次使用分支和繫結演算法.  1959年,吉莉安·比爾德伍德,J.H.哈爾頓和約翰·哈默斯利在劍橋哲學會的期刊上發表了一篇題為"通過許多點的最短路徑"的文章. 貝德伍德<unk>哈爾頓<unk>哈默斯利定理為旅行商人問題提供了一個實際的解決方案. 作者用一個異面公式來確定一個從家裡或辦公室開始的銷售人員最短路線的長度,然後在返回起點之前訪問一定的地點.  在接下來的幾十年裡, 數學,電腦科學,化學,物理和其他科學領域的許多研究人員研究了這個問題. 然而,在20世紀60年代,一種新的方法被創造出來,而不是尋求最佳解決方案,而是產生一個長度被證明是最優長度的倍數所限制的解決方案,這樣做會為問題創造下限;這些下限然後將被用於分支和繫結方法. 一種方法是建立圖形的最小跨度樹,然後將其所有邊緣加倍,從而產生一個最優遊的長度最多是最小跨度樹的兩倍.  在1976年,克里斯托菲德斯和塞爾杜科夫相互獨立地在這個方向上取得了很大的進步:克里斯托菲德斯-塞爾杜科夫演算法產生了一個解決方案,在最壞的情況下,最多是最佳解決方案的1.5倍. 由於演算法簡單快速, 許多人希望它能讓出一個接近最佳的解決方法. 然而,這種改善的希望並沒有立即實現,Christofides-Serdyukov一直是最好的最壞情況的方法,直到2011年,當時一個 (非常) 略微改進的近似演算法被開發為"圖形"TSP的子集. 在2020年,這一微小的改進擴充套件到全方位 (計量) TSP.  1972年,理查德·M·卡普 (Richard M. Karp) 表明,哈密爾頓週期問題是NP完整的,這意味著TSP的NP硬度. 這提供了一個數學解釋, 找出最優的旅程的明顯計算難度.  在20世紀70年代末和80年代取得了很大的進展,當時格羅切爾,帕德伯格,里納爾迪和其他人成功地使用切割平面和分支和繫結精確地解決了多達2,392個城市的例項.  在20世紀90年代,Applegate,Bixby,Chvátal和Cook開發了Concorde程式,該程式已被用於許多最近的記錄解決方案. 格哈德·萊因爾特於1991年出版了TSPLIB,這是一個不同難度的基準例項集合,許多研究小組都使用它來比較結果. 2006年,庫克和其他人通過微晶片佈局問題給出的85,900個城市例項計算了最佳之旅,目前這是最大的TSPLIB例項. 對於數以百萬計的其他城市, 可以找到解決方案,
* 19世紀 - 由愛爾蘭數學家威廉·羅恩·漢密爾頓和英國數學家托馬斯·柯克曼首次數學上提出 * 1930年代 - 首先由維也納和哈佛的數學家研究,最著名的是卡爾·門格爾和梅里爾·M·洪<unk>,他們正在尋求解決校車路線問題. * 1959年 - 吉莉安·比爾德伍德,J.H.哈爾頓和約翰·哈默斯利在劍橋哲學會的期刊上發表了一篇題為"通過許多點的最短路徑"的文章,該文章提供了第一個實際解決方案. * 1960年代 - 建立了新的方法,產生了長度可證明是最佳長度的倍數所限制的解決方案. * 1972年 - 理查德·M·卡普 (Richard M. Karp) 表明,哈密爾頓週期問題是NP完整的,這意味著旅行銷售員問題的NP硬度. * 1976年 - 克里斯托菲德斯和塞爾杜科夫獨立發明了新的演算法,該演算法產生了一個最壞的情況下最多是最優方案的1.5倍. * 1990年代 - - 艾普利蓋特,比克斯比,奇瓦特和庫克開發了康科德程式,該程式已被用於許多最近的記錄解決方案. 1991年 - 格哈德·萊因爾特出版了TSPLIB,這是一個不同難度的基準例項集,許多研究小組使用它來比較結果 * 2006年 - 庫克和其他人通過微晶片佈局問題給出的85,900個城市例項計算了最佳之旅,目前這是最大的TSPLIB例項. * 2011年 - 對"圖形"旅行銷售員問題的子集開發了略有改進的近似演算法. * 2020年 - 為"圖形"子集開發的略有改進的近似演算法被擴充套件到覆蓋整個旅行銷售員問題.