如何解决SML中的旅行商问题？

Question

有人有标准机器学习中的旅行推销员问题解决方案吗，请告诉我。

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

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