Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- let calcUpperBound problem =
- let N = problem.nodeCount
- let findEdge = getEdge problem.graph
- let allNodes = [ 0..problem.nodeCount - 1 ]
- // Nearest neighbor heuristic
- let rec loop tour unvisitedNodes includedEdges =
- match tour with
- | [] -> failwith "Empty list is bad"
- | xs when xs.Length = N -> tour
- | current :: xs ->
- // Try to use one of the included edges first
- let f = List.tryFind (fun f -> f.node1 = current || f.node2 = current) includedEdges
- match f with
- // One of the included edges fit: use it for the tour, remove it from the included
- // edges and recurse
- | Some(edge) ->
- let next =
- if edge.node1 = current then edge.node2
- else edge.node1
- loop (next :: tour) (removeFirst current unvisitedNodes) (removeFirst edge includedEdges)
- // No suitable edge in the included edges
- | None ->
- // find the edge with the lowest weight adjacent to the current node and pick the
- // node it leads to, add it to the tour and recurse
- let next =
- List.map (fun x -> (x, findEdge current x |> edgeWeight)) unvisitedNodes
- |> List.minBy (fun (_, weight) -> weight)
- |> fst
- loop (next :: tour) (removeFirst current unvisitedNodes) includedEdges
- // Does a Nearest neighbor tour starting from node i and caluclates the total weight
- // of the tour.
- let makeTour i =
- let t = loop [ i ] (removeFirst i allNodes) (List.ofSeq problem.includedEdges)
- let tour: Graph.Tour =
- { nodes = t
- totalWeight = tourWeight problem.graph t }
- tour
- let results = List.map makeTour allNodes
- List.minBy (fun (f: Graph.Tour) -> f.totalWeight) results
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement