跳至主要內容
Lizely

旅行售貨員求解器

使用最近鄰居法加上確定性 2 改進法，建立穿越 3 至 50 坐標的封閉歐幾裡得旅遊路線。

隱私權：你的檔案不會離開裝置，所有處理均在瀏覽器本機完成。

使用方式

  1. 1.以名稱、x、y 的格式輸入 3–50 的座標，並將希望的起點放在第一行。
  2. 2.構建近似路徑，並比較初始與改善後的距離。
  3. 3.檢視閉合路徑與假設，僅在直線歐幾裡得距離符合任務需求時才複製。

關於旅行售貨員求解器

旅行售貨員求解器會在兩維座標平面上，為命名點構建一條近似閉合路徑。每行輸入一個位置，格式為名稱、x、y。第一行為固定起點。結果會顯示一條路徑，訪問每個點一次、回到起點，並報告總直線距離。同時也會顯示最近鄰點起始距離以及 2-最佳化執行的次數，讓改善過程清晰可見，而非隱藏啟發式邏輯。

旅行銷售員問題要求最短的封閉路線,訪問所有位置. Google OR-Tools 解釋相同的路由目標,並警告實用解決者可以返回非最佳的結果,因為路由問題是計算困難的.本頁面故意使用一個有限的,可檢查的輯,而不是要求任意輸入的正確解決方案.。

路徑構建從第一個輸入點開始。每一步，最近鄰點選擇距離最短的未訪問點，使用歐幾裡得距離，即 sqrt((x2−x1)²+(y2−y1)²)。距離相同時維持輸入順序。當路徑完整後，2-最佳化會檢查兩段路徑邊緣。若將中間段反向連線能嚴格縮短路徑，則進行交換並重新掃描。此過程持續，直到無進一步改善或達到防禦性限制為止。

返回的路徑在兩段邊緣交換下會進行區域性最佳化，但無法保證是全球最短路徑。不同的起點或構建規則可能導致另一個區域性最優解。求解器將第一行固定為起點，以確保多次執行結果可重現。八個小型幾何案例——三角形、正方形、長方形、共線點以及中心點——驗證了正確的周長距離、閉合性、每個點僅訪問一次，以及 2-最佳化從不使初始路徑變長。

座標為抽象的平面值。它們可以是區域性圖紙上的公尺、佈局中的像素，或教室座標中兩軸使用相同比例的無單位值。這些座標並非緯度與經度。直接將度數用歐幾裡得距離計算會扭曲實際地球距離，特別是在大範圍或跨越反向子午線時。若需地理座標，應轉換為適當的區域性投影，或使用專門處理地心距離的路徑服務。

本頁面也忽略道路、單向街、交通、通勤時間、障礙物、約會、車輛容量及多車駕駛等實際因素。兩點之間的直線段不代表車輛能實際通行。真實的路徑規劃需要實際的距離或時間矩陣以及相關限制條件。本工具未呼叫外部地圖 API，因此無需付費請求，也無位置資料離開瀏覽器。

輸入必須為 3 至 50 之間的獨特座標對。重複座標將被拒絕，因為兩個名稱相同但位置完全一致的點會導致路徑顯示模糊。名稱不得包含逗號，座標必須為有限且有界值，且點數限制確保本機搜尋的響應性。複製結果包含完整的閉合名稱序列與計算出的距離。

可使用此工具學習 TSP 啟發式方法、探索空間排序、規劃一個近似巡檢順序，或建立可重現的測試環境。若解的品質重要，可比較多種起點順序。對於派車、導航、成本承諾或安全關鍵路徑，請使用經驗證的求解器，並以實際網路資料為基礎，獨立驗證路徑，而非將此本機近似視為操作依據。

方法與來源

驗證 3–50 的獨特、有界平面點，將第一點設為起點，構建穩定的最近鄰點閉合路徑，然後反覆執行第一個能嚴格改善的 2-最佳化邊緣交換。累加歐幾裡得斜邊距離，包含返回起點的距離；絕不聲稱具有全球最優性。

常見問題

這是否能找出全球最短路徑？
不能。最近鄰點加上 2-最佳化是一種確定性啟發式，可能停在區域性最優解。
我可以輸入緯度和經度嗎？
不建議直接使用，因為無法提供可靠的地理距離。此求解器將座標視為平面上的歐幾裡得幾何。
它會遵循道路或交通狀況嗎？
不會。它使用直線座標距離，且不呼叫任何地圖或路徑 API。
為何第一個位置特別？
它固定了起點，並維持確定性排序行為；路徑最終會回到該位置。

相關工具

計算工具 使用指南

查看全部