How to solve Traveling Salesman in SML? [closed]
Does anybody have a traveling salesman problem solution in Standard ML, please tell me.
I've tried a lot but am not successful.
The brute force solution to traveling salesman is very straight forward. You populate a list of possible paths and pick the smallest one.
As for doing this in SML there are a myriad of methods. It will firstly depend on what data structure you are using to do this, and secondly on whether or not you wish to use 'lazy' functions / streams.
My suggestion to you is to code a simple path finder first, then extend it to generating all paths as a list or other data structure. Finally sort that list for the smallest trip length. Use the TSP on wiki as a helpful resource when considering how to go about solving this problem.
I'm sorry, but I'm not in the business of doing others homework for them.
Good SML reference, and another
I don't know how to use 2D arrays in SML. This is an F# solution:
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
Translating it into SML should be straightforward if you know SML.
精彩评论