嘗試計算訪問大量城市的最短路線是否毫無希望？ 不僅僅是一條好的路線，而是有保證的最短路線。 這項任務是長期存在的挑戰，被稱為旅行推銷員問題，或簡稱 TSP。
找到一種可以快速解決 TSP 每個例項的方法將是數學上的一個驚人突破。 使用複雜性理論，這種方法將使我們能夠有效地解決任何可以輕鬆驗證答案的計算問題。 大多數數學家都認為這是不可能的。
但是，假設您獲得了 100,000 個城市的位置。 找到最短路線真的不可能嗎？ 我們不是要求解決 TSP 的每個例項，只是想找到繞這些特定位置的最快方法。
關於支援科學新聞報道
如果您喜歡這篇文章，請考慮透過以下方式支援我們屢獲殊榮的新聞報道 訂閱。 透過購買訂閱，您正在幫助確保有關塑造我們當今世界的發現和想法的具有影響力的故事的未來。
為了迎接挑戰，您最好的選擇是聽從瑜伽大師貝拉的建議：“當你走到岔路口時，就走過去。” 一種名為線性規劃的工具允許我們透過為連線城市對的道路分配分數，而不是立即決定是否使用某條道路來做到這一點。 在這個模型中，讓一半的推銷員沿著岔路的兩個分支走是完全可以的。 該過程從對每個城市的要求開始，即分配給到達和離開道路的分數之和均為 1。 然後，逐步新增更多限制，每個限制都涉及分配給道路的分數之和。 線性規劃最終會為我們指出每條道路的最佳決策，從而指出最短的可能路線。
我應該補充一點，100,000 個城市並非假設性的挑戰。 當前的計算正逼近奧柏林學院的羅伯特·博世建立的一組漂亮的 100,000 個點的解決方案，其中巡迴路線描繪出了蒙娜麗莎的畫像。 我們可能無法解決 TSP 的每個示例，但新的想法可以推動可解性的前沿。
這就是大局：複雜性理論表明，科學和其他領域的通用計算技術的能力存在侷限性。 這些侷限性是什麼？它們在多大程度上限制了我們對知識的追求？ 這就是對 TSP 進行研究的全部意義。
本文以“旅行推銷員案例”為標題在印刷版上發表。