旅行推銷員問題的歷史是什麼?
Context:這種問題的根源尚不清楚. 這項問題在1832年出版的一本旅遊商人的手冊中提到,   威廉·羅恩·漢密爾頓 這項數學概念由愛爾蘭數學家威廉·羅恩·哈密爾頓和英國數學家託馬斯·柯克曼在19世紀提出. 哈密爾頓的遊戲是以尋找哈密爾頓週期為基礎的遊戲. 似乎是數學家在 1930 年代的維也納和哈佛大學首次研究了 TSP 的一般形式,  我們以信使問題來表示 (因為實際上這個問題應該由每位郵差, 也由許多旅行者來解決) 找到最短的路線, 這項問題可以通過數量有限的試驗來解決. 沒有任何規則可以使試驗次數低於所謂點的排列次數. 這樣的規則通常不會導致最短的路線.  這項問題在1930年代由梅里爾·M·弗洛德 (Merrill M. Flood) 首次在數學上提出, 普林斯頓大學的哈斯勒·惠特尼對這個問題產生了興趣, 這項問題在1949年由蘭德公司 (RAND Corporation) 發表的"哈密爾頓遊戲 (一個旅行的銷售員問題) ".  在1950年代和1960年代, 在聖塔莫尼卡的蘭德公司為解決問題的步<unk>提供獎勵後, 這個問題在歐洲和美國的科學圈子中變得越來越受歡迎. 這項問題由蘭德公司的George Dantzig,Delbert Ray Fulkerson和Selmer M. Johnson做出了顯著的貢獻, 他們寫了這篇被認為是這項主題的開創性論文, 但丹齊格,富爾克森和約翰遜推論, 給予一個接近最佳的解決方案, 他們使用這個想法來解決他們最初的49個城市問題, 他們發現他們只需要26個裁員才能解決49個城市的問題. 儘管這篇文章並沒有提供對TSP問題的演算法方法, 但它所包含的想法是不可或缺的, 這可能是首次使用分支和連結演算法.  1959年, 吉莉安·比爾伍德,J.H.哈爾頓和約翰·哈默斯利在"劍橋哲學學會"雜誌上發表了一篇名為"通過許多點的最短路徑"的文章. 這項資料是用來解答一個問題. 推薦他們使用一條不對稱的公式來決定一個從家或辦公室開始,  這項問題在接下來的幾十年裡, 在1960年代, 然而, 建立了一種新的方法, 而不是尋求最佳解決方案會產生一個長度可被證明為最佳長度的倍數的解決方案, 這樣做會為問題創造下限; 這些下限會用於分支和受限方法. 這樣做的一種方法是建立圖形的最小跨度樹,然後將其所有邊緣加倍,  在1976年, 克里斯托菲德斯和塞爾德尤科夫獨立地在這個方向上取得了很大的進步:克里斯托菲德斯-塞爾德尤科夫演算法產生了一個最糟糕的情況下, 許多人希望它能讓近乎最佳的解決方法. 但這項改善的希望並沒有立即實現,Christofides-Serdyukov仍然是最好的最壞情景的方法,直到2011年, 這項微小改進在2020年被擴充套件到全 (計量) TSP.  哈密爾頓週期問題是NP完整的, 這意味著TSP的NP硬度. 這提供了一種數學解釋,  在1970年代末和1980年代取得了很大的進步, 當格羅斯切爾,帕德伯格,裡納爾迪和其他人成功地用切割平面和分支和連結, 精確解決了多達2,392個城市的例項.  在1990年代,Applegate,Bixby,Chvátal和Cook開發了Concorde程式, 這項研究的成果已被許多研究團隊使用來比較結果. 2006 年, 庫克和其他人計算出由微晶片佈局問題所給出的 85,900 座城市例項的最佳遊覽, 目前是最大的 TSPLIB 例項. 在許多其他數以百萬計城市的情況下,
* 19 世紀 - 由愛爾蘭數學家威廉·羅恩·哈密爾頓和英國數學家託馬斯·柯克曼首次數學上提出 首先由維也納和哈佛的數學家研究, 1959年 - 吉莉安·比爾伍德,J.H.哈爾頓和約翰·哈默斯利在劍橋哲學學會的雜誌上發表了一篇題為"通過許多點的最短路徑", 該方法的長度可靠地以最佳長度的倍數為邊界. 1972 年 - 理查德·卡普 (Richard M. Karp) 顯示哈密爾頓週期問題是NP完整的, 這意味著旅行商人問題的NP硬度. 1976 年 - 克里斯托菲德斯和塞爾德尤科夫獨立發明瞭新的演算法, 在1990年代, Applegate,Bixby,Chvátal和Cook開發了Concorde程式, 1991 年 - Gerhard Reinelt 發表了 TSPLIB, 這是一系列不同難度的基準案例, * 2006年 - 庫克和其他人計算出由微晶片佈局問題所給出的85,900個城市例項的最佳巡遊,目前這是最大的TSPLIB例項. 2011 年 - 對於"圖形"旅行推銷員問題的子集開發了稍微改進的近似演算法. 2020 年 - 為"圖形"子集開發的略有改進的近似演算法被擴充套件到覆蓋完整的旅行銷售員問題.