开发者

How to solve Traveling Salesman in SML? [closed]

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetoric开发者_运维问答al and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. Closed 10 years ago.

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.

0

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜