如何解決SML中的旅行推銷員？

Question

有沒有人有標準ML的旅行推銷員問題解決方案，請告訴我。

我試了很多，但沒有成功。

Answer 1

旅行推銷員的蠻力解決方案非常簡單。您填充可能的路徑列表並選擇最小的路徑。

至於在SML中這樣做有無數的方法。它首先取決於你使用什麼數據結構來做到這一點，其次取決於你是否希望使用'懶惰'功能/流​​。

我給你的建議是先編寫一個簡單的路徑查找器，然後將其擴展爲以列表或其他數據結構生成所有路徑。最後，對最小行程長度進行排序。在考慮如何解決這個問題時，請使用wiki上的TSP作爲有用的資源。

我很抱歉，但我並沒有爲他們做別人的家庭作業。

好SML參考，並another

Answer 2

我不知道如何使用SML二維數組。這是一個F＃解決方案：

let salesman2 (g:int array array) = 
    let n = Array.length g 
    let rec salesman' visited last acc = 
     if Set.count visited = n then acc 
     else 
      {0..n-1} 
      |> Seq.filter (fun i->not (Set.contains i visited)) 
      |> Seq.map (fun i->salesman' (Set.add i visited) i (acc + g.[last].[i])) 
      |> Seq.min 
    salesman' Set.empty 0 0 

let g = [|[|0;1;2;4|]; [|1;0;2;2;|]; [|2;2;0;3|]; [|4;2;3;0|] |] 
salesman2 g 

如果您知道SML，那麼將其轉換爲SML應該很簡單。