algorithm - SMLで巡回セールスマンを解決するには?

Question

Standard ML で巡回セールスマンの問題を解決できる人はいますか?教えてください。

私はたくさん試しましたが、成功していません。

Answer 1

巡回セールスマンに対する強引な解決策は非常に簡単です。可能なパスのリストを作成し、最小のものを選択します。

SML でこれを行うには、無数の方法があります。まず、これを行うために使用しているデータ構造に依存し、次に「遅延」関数/ストリームを使用するかどうかに依存します。

最初に単純なパス ファインダーをコーディングし、それを拡張してすべてのパスをリストまたはその他のデータ構造として生成することをお勧めします。最後に、そのリストを最小の移動距離で並べ替えます。この問題を解決する方法を検討する際は、wiki のTSPを役立つリソースとして使用してください。

申し訳ありませんが、私は他の人のために宿題をする仕事をしているわけではありません。

優れたSMLリファレンス、および別の

Answer 2

SML で 2D 配列を使用する方法がわかりません。これは 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 への変換は簡単です。