algorithm - 如何解决 SML 中的旅行推销员？

Question

有没有人在标准 ML 中有旅行商问题的解决方案，请告诉我。

我已经尝试了很多但没有成功。

Answer 1

旅行推销员的蛮力解决方案非常简单。您填充可能路径的列表并选择最小的路径。

至于在 SML 中执行此操作，有无数种方法。它首先取决于您使用什么数据结构来执行此操作，其次取决于您是否希望使用“惰性”函数/流。

我对您的建议是先编写一个简单的路径查找器，然后将其扩展为将所有路径生成为列表或其他数据结构。最后对该列表进行排序以获得最小的行程长度。在考虑如何解决这个问题时，使用 wiki 上的TSP作为有用的资源。

对不起，我不负责为别人做作业。

良好的SML参考和另一个

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 应该很简单。