SML travelling salesman problem

Question

please anybody having travelling salesman problem solution in Standard ML, plz tell me.

I've tried a lot but am not successfull...

Thx in advance.

Answer 1

Depends. How long are you willing to wait for the program to give a solution? Are you looking for the general algorithm or a specific solution with a specific number of cities?

Answer 2

No waiting to consider. I was told to use brute force. I was given 5 cities.

Answer 3

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

Answer 4

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.