Advertisement
Guest User

Untitled

a guest
Jul 8th, 2014
246
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
F# 1.95 KB | None | 0 0
  1. let calcUpperBound problem =
  2.     let N = problem.nodeCount
  3.     let findEdge = getEdge problem.graph
  4.     let allNodes = [ 0..problem.nodeCount - 1 ]
  5.    
  6.     // Nearest neighbor heuristic
  7.     let rec loop tour unvisitedNodes includedEdges =
  8.         match tour with
  9.         | [] -> failwith "Empty list is bad"
  10.         | xs when xs.Length = N -> tour
  11.         | current :: xs ->
  12.             // Try to use one of the included edges first
  13.             let f = List.tryFind (fun f -> f.node1 = current || f.node2 = current) includedEdges
  14.             match f with
  15.             // One of the included edges fit: use it for the tour, remove it from the included
  16.             // edges and recurse
  17.             | Some(edge) ->
  18.                 let next =
  19.                     if edge.node1 = current then edge.node2
  20.                     else edge.node1
  21.                 loop (next :: tour) (removeFirst current unvisitedNodes) (removeFirst edge includedEdges)
  22.             // No suitable edge in the included edges
  23.             | None ->
  24.                 // find the edge with the lowest weight adjacent to the current node and pick the
  25.                 // node it leads to, add it to the tour and recurse
  26.                 let next =
  27.                     List.map (fun x -> (x, findEdge current x |> edgeWeight)) unvisitedNodes
  28.                     |> List.minBy (fun (_, weight) -> weight)
  29.                     |> fst
  30.                 loop (next :: tour) (removeFirst current unvisitedNodes) includedEdges
  31.    
  32.     // Does a Nearest neighbor tour starting from node i and caluclates the total weight
  33.     // of the tour.
  34.     let makeTour i =
  35.         let t = loop [ i ] (removeFirst i allNodes) (List.ofSeq problem.includedEdges)
  36.        
  37.         let tour: Graph.Tour =
  38.             { nodes = t
  39.               totalWeight = tourWeight problem.graph t }
  40.         tour
  41.  
  42.     let results = List.map makeTour allNodes
  43.     List.minBy (fun (f: Graph.Tour) -> f.totalWeight) results
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement