So we’ve come a long way and can now bring it all together. The final code includes everything we’ve done and allows the branch and bound method to be applied to 0-1 knapsack, MAX-SAT and TSP. We could readily add other NP-hard types as well to our general framework. The generalized solution was built up starting from the special case of 0-1 knapsack. Could we have done a top-down approach instead? Yes, but the approach taken here was to show an incremental learning process to tackle a non-trivial problem. With the experience gained, one could probably start at the end state we have here and then develop the problem specific code.
We’ve seen how powerful first-class functions and partial function application can be, particularly as we defined the f
and g
functions for each problem instance. We were able to ‘build in’ data particular to a problem instance into these functions allowing the generalized BandB
function to basically follow the uncluttered, pseudo-code version of the method. We did that by making the type used in the search tree the last argument and leveraging currying 1, 2. Could we even build the search tree elements into f
and g
? Well, not easily as we need to keep track of the best solution along with upperbound estimates for nodes in the search tree in the course of executing BandB
.
Next we look more closely at the type for both the BandBminimize
or BandBmaximize
functions. Remember that we have changed it since the image shown on page 4.
Problem | ‘a | ‘b |
---|---|---|
0-1 knapsack | KnapDiscreteVar array |
float |
MAX-SAT | MaxSatDiscreateVar array |
int |
TSP | TSPstate |
float |
So we read the type signature for the first argument f
of BandB
, for example, as a function that takes an 'a
and produces a 'b
, where 'a
and ‘b
‘ vary depending on which invocation we applied (see table). The 'a
‘s are the types that appear as the nodes in the search tree, and the 'b
‘s are the value type to be optimized.
Don’t be afraid of generic types in function signatures, as named 'a
, 'b
, etc. they just mean that the function is more flexible, not being constrained to a particular type. On the otherhand, when you have problems with types examine all the code to see what is forcing a type that maybe you aren’t expecting or don’t want. This reference has some useful tips. As reference, in C++ or C# you would have to create this function using a template
(auto
function arguments ala F# are being considered for C++17) but in F# generic types are used automatically, unless there is something constraining them.
Final tweaks
Another thought I had was to remove the initial value setting (initLowestValue
which since we are minimizing too now would be better named just initValue but I will leave it) needed for BandBminimize
or BandBmaximize
functions. For our cases, this is typed as either an int or a float, so we could set the initial value to either the minimum or maximum possible value for these depending if we are maximizing or mininizing. F# does allow a generic zero and generic one value that can be either an int, float or big int (as far as I see), but there isn’t a similar generic for max or min values of the respective type. We have the same issue as brought up here, and it looks like we could use the Bounded
package for this purpose. We could also think about using Double.MaxValue
or MinValue
and converting int result types (as for Max-Sat) to doubles; there is also a Double.PositiveInfinity
and Double.NegativeInfinity
value provided, which could be used assuming this conversion. But in principle, any sortable value (that is one that is subject to (<)
and (>)
operations) would be a valid candidiate for the BandB
function. But then perhaps any of these types could always be converted double and then we would restrict the type of the 'b
type to double.
But instead, its an opportunity to think about the option feature of F#. Basically an option type just means that the variable might be None
meaning it doesn’t exist. I was thinking of changing the BandB
code to:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: |
let BandB maximize f g branch unFinished state = let compareFunc x y = if maximize then x > y else x < y let bestUtility = ref None let mutable bestNode = None // best var settings found, nothing so far. let mutable queue = [ (g state, state) ] // these are only informational, not needed in the routine let mutable numberOfQueues = 1 // we just queued the start, so 1 let mutable numberOfEvals = 0 // number of times we evaluated the function with all vars set while not queue.IsEmpty do match queue with | (gNode,curNode) :: restOfQueue -> if unFinished curNode then // guard against search nodes that are already ruled out ... if not (compareFunc gNode !bestUtility) then do queue <- restOfQueue // this node can't be better than what we have, toss it else do // update: apply `g` here instead, simplifying branch, and allows sorting the queue let toQueueAll = branch curNode let toQueueAugmented = toQueueAll |> List.map (fun elem -> ((g elem), elem)) let toQueue = toQueueAugmented |> List.filter (fun elem -> compareFunc (fst elem) !bestUtility) // sort only using the first tuple value (g) so the curNode type doesn't need compare match !bestUtility with | None -> queue <- (toQueue @ restOfQueue) // no sorting, just descend to get a first DFS | Some(v) -> if maximize then do queue <- (toQueue @ restOfQueue) |> List.reverseSortBy (fun elem -> (fst elem)) else queue <- (toQueue @ restOfQueue) |> List.sortBy (fun elem -> (fst elem)) numberOfQueues <- numberOfQueues + toQueue.Length else let util = f curNode numberOfEvals <- numberOfEvals + 1 if compareFunc util !bestUtility then bestUtility := util bestNode <- curNode queue <- restOfQueue // we've processed curNode, take it off the queue | _ -> () // queue isempty, do nothing printfn "\nBandB: total settings queued = %d, total number of evals: %d" numberOfQueues numberOfEvals (!bestUtility, bestNode) |
??? What is the best suggestion for this, using generic min/value values or option types?
which is OK, but this then cascaded into many changes to all the problem domain functions since now many of their return types would have to be an option type as well (since, for example, bestNode
is an option type). I will have to think about this more.
But to wrap up this section, I also added a function to create randomized MAX-SAT instances:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: |
// new function to generate a random MAX SAT case let genMaxSat nVars nClauses = // embedded function let getRandom = let rnd = System.Random(100) // use a seed so that everytime we run we get the same values fun maxNum -> let e = rnd.Next(1, maxNum+1) let s = rnd.Next(0,2) if s = 0 then e else -e // return Plus or Minus the int let vars = Array.init nVars (fun index -> {Name = (sprintf "v%i" (index+1)); Setting = Unset }) // generate random 3-clause let clauses = Array.init nClauses (fun _ -> [| getRandom nVars; getRandom nVars; getRandom nVars |] ) (vars, clauses) |
The complete final BandB
code is:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: |
namespace BandBapplication (* This is a type extension that extends the standard List type to include a reverse sort *) module List = let reverseSort x = x |> List.sort |> List.rev // List now has a reverseSort method! let reverseSortBy f x = x |> List.sortBy f |> List.rev // List now has a reverseSortBy method! module BandB = let BandB maximize f g branch unFinished node initLowestValue = let compareFunc x y = if maximize then x > y else x < y let bestUtility = ref initLowestValue; // update: queue elements are now a 2-tuple (pair) of g-upperbound estimate and node let mutable queue = [ (g node, node) ] let mutable bestNode = node // best var settings found, nothing so far. // these are only informational, not needed in the routine let mutable numberOfQueues = 1 // we just queued the start, so 1 let mutable numberOfEvals = 0 // number of times we evaluated the function with all vars set while not queue.IsEmpty do match queue with | (gNode,curNode) :: restOfQueue -> if unFinished curNode then // guard against search nodes that are already ruled out ... if not (compareFunc gNode !bestUtility) then do queue <- restOfQueue // this node can't be better than what we have, toss it else do // update: apply `g` here instead, simplifying branch, and allows sorting the queue let toQueueAll = branch curNode let toQueueAugmented = toQueueAll |> List.map (fun elem -> ((g elem), elem)) let toQueue = toQueueAugmented |> List.filter (fun elem -> compareFunc (fst elem) !bestUtility) // sort only using the first tuple value (g) so the curNode type doesn't need compare if !bestUtility = initLowestValue then do queue <- (toQueue @ restOfQueue) // no sorting, just descend to get a first DFS else if maximize then do queue <- (toQueue @ restOfQueue) |> List.reverseSortBy (fun elem -> (fst elem)) else queue <- (toQueue @ restOfQueue) |> List.sortBy (fun elem -> (fst elem)) numberOfQueues <- numberOfQueues + toQueue.Length else let util = f curNode numberOfEvals <- numberOfEvals + 1 if compareFunc util !bestUtility then bestUtility := util bestNode <- curNode queue <- restOfQueue // we've processed curNode, take it off the queue | _ -> () // queue isempty, do nothing printfn "\nBandB: total settings queued = %d, total number of evals: %d" numberOfQueues numberOfEvals (!bestUtility, bestNode) let BandBmaximize f g branch unFinished node initLowestValue = BandB true f g branch unFinished node initLowestValue let BandBminimize f g branch unFinished node initHighestValue = BandB false f g branch unFinished node initHighestValue |
On lines 42-43 code was added to ensure that the queue does not get sorted until after at least 1 full solution is found. The idea of this is that this would establish an early bound for better search pruning. We will see mixed results later on from this.
We added a random 15 variable, 120 clause problem for Max-Sat to create a larger problem size as well sp that finally, here is the full main code:
1: 2: 3: 4: 5: 6: 7: 8: 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23: 24: 25: 26: 27: 28: 29: 30: 31: 32: 33: 34: 35: 36: 37: 38: 39: 40: 41: 42: 43: 44: 45: 46: 47: 48: 49: 50: 51: 52: 53: 54: 55: 56: 57: 58: 59: 60: 61: 62: 63: 64: 65: 66: 67: 68: 69: 70: 71: 72: 73: 74: 75: 76: 77: 78: 79: 80: 81: 82: 83: 84: 85: 86: 87: 88: 89: 90: 91: 92: 93: 94: 95: 96: 97: 98: 99: 100: 101: 102: 103: 104: 105: 106: 107: 108: 109: 110: 111: 112: 113: 114: 115: 116: 117: 118: 119: 120: 121: 122: 123: 124: 125: 126: 127: 128: 129: 130: 131: 132: 133: 134: 135: 136: 137: 138: 139: 140: 141: 142: 143: 144: 145: 146: 147: 148: 149: 150: 151: |
namespace BandBapplication (* Part II page 6 *) open Knapsack01 open MaxSat open TSP open BandB module Main = [<EntryPoint>] let main argv = (* *************************************************************************************** *) (* KNAPSACK EXAMPLE 1 *) let vars1 = [|{Name = "food"; Setting = ZeroOneVarSetting.Unset; Weight = 5.0; Utility = 8.0}; {Name = "tent"; Setting = ZeroOneVarSetting.Unset; Weight = 14.5; Utility = 5.0}; {Name = "gps"; Setting = ZeroOneVarSetting.Unset; Weight = 1.0; Utility = 3.0}; {Name = "map"; Setting = ZeroOneVarSetting.Unset; Weight = 0.5; Utility = 3.0} |] let weightLimit1 = 16.0 let vars1Sorted = (Array.sortBy (fun elem -> -elem.Utility / elem.Weight) vars1) // still have this let gknap1 = knapestimator weightLimit1 let knapAnyUnset = Array.exists (fun (elem:KnapDiscreteVar) -> ZeroOneVarSetting.isUnset elem.Setting) let branchKnap1 = branchknap weightLimit1 (* Invoke *) let (solutionUtility, solutionVars) = BandBmaximize knapmultiplySumUtility gknap1 branchKnap1 knapAnyUnset vars1Sorted -1.0 printfn "Best Utility = %f" solutionUtility for var in solutionVars do printfn "%14s -> %s [weighs = %f]" var.Name (match var.Setting with | One -> "take " | _ -> "leave") var.Weight (* *************************************************************************************** *) (* MAXSAT EXAMPLE 1 *) let vars2 = [| {Name = "v1"; Setting = Unset}; {Name = "v2"; Setting = Unset}; {Name = "v3"; Setting = Unset}; {Name = "v4"; Setting = Unset}; {Name = "v5"; Setting = Unset}; {Name = "v6"; Setting = Unset} |] let clauses2 = [| [|-1; 2; -4|]; // positive = var at that index; negative means not var at index [|-1; 3; 4|]; [|-2; 3; 4|]; [|-2; -4; -5|]; [| 2; 3; 6|]; [| 3; 5; -6|]; [|-4; -5; 6|]; [|-2; 5; -6|]; [| 3; -5; 6|]; |] let f2 = clausefulleval clauses2 // partial func application let g2 = clauseNumFalseFunc clauses2 let maxsatAnyUnset = Array.exists (fun elem -> elem.Setting = ZeroOneVarSetting.Unset) let (bestValue2, solution2) = BandBmaximize f2 g2 maxsat_branch maxsatAnyUnset vars2 -1 printfn "Solution 2:" printfn "# clauses satisfied = %d out of %d" bestValue2 clauses2.Length solution2 |> Array.iter (fun elem -> printfn "%s = %s" elem.Name (match elem.Setting with | ZeroOneVarSetting.Unset -> "<ERR:UNSET>" | ZeroOneVarSetting.Zero -> "false" | _ -> "true")) // Max Sat random let vars2_rand,clauses2_rand = genMaxSat 15 120 let f2_rand = clausefulleval clauses2_rand // partial func application let g2_rand = clauseNumFalseFunc clauses2_rand let (bestValue2_rand, solution2_rand) = BandBmaximize f2_rand g2_rand maxsat_branch maxsatAnyUnset vars2_rand -1 printfn "Solution 2_rand:" printfn "# clauses satisfied = %d out of %d" bestValue2_rand clauses2_rand.Length solution2_rand |> Array.iter (fun elem -> printfn "%s = %s" elem.Name (match elem.Setting with | ZeroOneVarSetting.Unset -> "<ERR:UNSET>" | ZeroOneVarSetting.Zero -> "false" | _ -> "true")) (* *************************************************************************************** *) (* TSP EXAMPLE 1 *) (* data format EdgeValue wher: row is from index, column is to index. *) let matrix3_aa = [| [| NoEdge; EdgeValue(20.0); EdgeValue(30.0); EdgeValue(10.0); EdgeValue(11.0) |]; [| EdgeValue(15.0); NoEdge; EdgeValue(16.0); EdgeValue(4.0); EdgeValue(2.0) |]; [| EdgeValue(3.0); EdgeValue(5.0); NoEdge; EdgeValue(2.0); EdgeValue(4.0) |]; [| EdgeValue(19.0); EdgeValue(6.0); EdgeValue(18.0); NoEdge;EdgeValue(3.0) |]; [| EdgeValue(16.0); EdgeValue(4.0); EdgeValue(7.0); EdgeValue(16.0); NoEdge |]; |] let matrix3 = Array2D.init 5 5 (fun i j -> matrix3_aa.[i].[j]) // create as Array2D // TSP node let start3 = TSPcreateStartState matrix3 let tspCost3 = TSPcost matrix3 // bake in the matrix let (bestValue3, solution3) = BandBminimize tspCost3 TSPg branchTSP TSPmoreToDo start3 System.Double.PositiveInfinity printfn "Solution 3:" printfn "tour cost = %f" (bestValue3) printfn "%A" solution3.EdgeList (* data format EdgeValue wher: row is from index, column is to index. *) (* from https://parallel-tsp.googlecode.com/files/teamDharmaPresentation.pdf *) let matrix4_aa = [| [| NoEdge; EdgeValue(755.0); EdgeValue(687.0); EdgeValue(936.0); EdgeValue(721.0) |]; [| EdgeValue(755.0); NoEdge; EdgeValue(310.0); EdgeValue( 43.0); EdgeValue(729.0) |]; [| EdgeValue(687.0); EdgeValue(310.0); NoEdge; EdgeValue(390.0); EdgeValue(478.0) |]; [| EdgeValue(936.0); EdgeValue( 43.0); EdgeValue(390.0); NoEdge; EdgeValue(643.0) |]; [| EdgeValue(721.0); EdgeValue(729.0); EdgeValue(478.0); EdgeValue(643.0); NoEdge |]; |] let matrix4 = Array2D.init 5 5 (fun i j -> matrix4_aa.[i].[j]) // create as Array2D // TSP node let start4 = TSPcreateStartState matrix4 let tspCost4 = TSPcost matrix4 let (bestValue4, solution4) = BandBminimize tspCost4 TSPg branchTSP TSPmoreToDo start4 System.Double.PositiveInfinity printfn "Solution 4:" printfn "tour cost = %f" (bestValue4) printfn "%A" solution4.EdgeList let matrix4_15_aa = [| [| NoEdge; EdgeValue(29.0); EdgeValue(82.0); EdgeValue(46.0); EdgeValue(68.0); EdgeValue(52.0); EdgeValue(72.0); EdgeValue(42.0); EdgeValue(51.0); EdgeValue(55.0); EdgeValue(29.0); EdgeValue(74.0); EdgeValue(23.0); EdgeValue(72.0); EdgeValue(46.0) |]; [| EdgeValue(29.0); NoEdge; EdgeValue(55.0); EdgeValue(46.0); EdgeValue(42.0); EdgeValue(43.0); EdgeValue(43.0); EdgeValue(23.0); EdgeValue(23.0); EdgeValue(31.0); EdgeValue(41.0); EdgeValue(51.0); EdgeValue(11.0); EdgeValue(52.0); EdgeValue(21.0) |]; [| EdgeValue(82.0); EdgeValue(55.0); NoEdge; EdgeValue(68.0); EdgeValue(46.0); EdgeValue(55.0); EdgeValue(23.0); EdgeValue(43.0); EdgeValue(41.0); EdgeValue(29.0); EdgeValue(79.0); EdgeValue(21.0); EdgeValue(64.0); EdgeValue(31.0); EdgeValue(51.0) |]; [| EdgeValue(46.0); EdgeValue(46.0); EdgeValue(68.0); NoEdge; EdgeValue(82.0); EdgeValue(15.0); EdgeValue(72.0); EdgeValue(31.0); EdgeValue(62.0); EdgeValue(42.0); EdgeValue(21.0); EdgeValue(51.0); EdgeValue(51.0); EdgeValue(43.0); EdgeValue(64.0) |]; [| EdgeValue(68.0); EdgeValue(42.0); EdgeValue(46.0); EdgeValue(82.0); NoEdge; EdgeValue(74.0); EdgeValue(23.0); EdgeValue(52.0); EdgeValue(21.0); EdgeValue(46.0); EdgeValue(82.0); EdgeValue(58.0); EdgeValue(46.0); EdgeValue(65.0); EdgeValue(23.0) |]; [| EdgeValue(52.0); EdgeValue(43.0); EdgeValue(55.0); EdgeValue(15.0); EdgeValue(74.0); NoEdge; EdgeValue(61.0); EdgeValue(23.0); EdgeValue(55.0); EdgeValue(31.0); EdgeValue(33.0); EdgeValue(37.0); EdgeValue(51.0); EdgeValue(29.0); EdgeValue(59.0) |]; [| EdgeValue(72.0); EdgeValue(43.0); EdgeValue(23.0); EdgeValue(72.0); EdgeValue(23.0); EdgeValue(61.0); NoEdge; EdgeValue(42.0); EdgeValue(23.0); EdgeValue(31.0); EdgeValue(77.0); EdgeValue(37.0); EdgeValue(51.0); EdgeValue(46.0); EdgeValue(33.0) |]; [| EdgeValue(42.0); EdgeValue(23.0); EdgeValue(43.0); EdgeValue(31.0); EdgeValue(52.0); EdgeValue(23.0); EdgeValue(42.0); NoEdge; EdgeValue(33.0); EdgeValue(15.0); EdgeValue(37.0); EdgeValue(33.0); EdgeValue(33.0); EdgeValue(31.0); EdgeValue(37.0) |]; [| EdgeValue(51.0); EdgeValue(23.0); EdgeValue(41.0); EdgeValue(62.0); EdgeValue(21.0); EdgeValue(55.0); EdgeValue(23.0); EdgeValue(33.0); NoEdge; EdgeValue(29.0); EdgeValue(62.0); EdgeValue(46.0); EdgeValue(29.0); EdgeValue(51.0); EdgeValue(11.0) |]; [| EdgeValue(55.0); EdgeValue(31.0); EdgeValue(29.0); EdgeValue(42.0); EdgeValue(46.0); EdgeValue(31.0); EdgeValue(31.0); EdgeValue(15.0); EdgeValue(29.0); NoEdge; EdgeValue(51.0); EdgeValue(21.0); EdgeValue(41.0); EdgeValue(23.0); EdgeValue(37.0) |]; [| EdgeValue(29.0); EdgeValue(41.0); EdgeValue(79.0); EdgeValue(21.0); EdgeValue(82.0); EdgeValue(33.0); EdgeValue(77.0); EdgeValue(37.0); EdgeValue(62.0); EdgeValue(51.0); NoEdge; EdgeValue(65.0); EdgeValue(42.0); EdgeValue(59.0); EdgeValue(61.0) |]; [| EdgeValue(74.0); EdgeValue(51.0); EdgeValue(21.0); EdgeValue(51.0); EdgeValue(58.0); EdgeValue(37.0); EdgeValue(37.0); EdgeValue(33.0); EdgeValue(46.0); EdgeValue(21.0); EdgeValue(65.0); NoEdge; EdgeValue(61.0); EdgeValue(11.0); EdgeValue(55.0) |]; [| EdgeValue(23.0); EdgeValue(11.0); EdgeValue(64.0); EdgeValue(51.0); EdgeValue(46.0); EdgeValue(51.0); EdgeValue(51.0); EdgeValue(33.0); EdgeValue(29.0); EdgeValue(41.0); EdgeValue(42.0); EdgeValue(61.0); NoEdge; EdgeValue(62.0); EdgeValue(23.0) |]; [| EdgeValue(72.0); EdgeValue(52.0); EdgeValue(31.0); EdgeValue(43.0); EdgeValue(65.0); EdgeValue(29.0); EdgeValue(46.0); EdgeValue(31.0); EdgeValue(51.0); EdgeValue(23.0); EdgeValue(59.0); EdgeValue(11.0); EdgeValue(62.0); NoEdge; EdgeValue(59.0) |]; [| EdgeValue(46.0); EdgeValue(21.0); EdgeValue(51.0); EdgeValue(64.0); EdgeValue(23.0); EdgeValue(59.0); EdgeValue(33.0); EdgeValue(37.0); EdgeValue(11.0); EdgeValue(37.0); EdgeValue(61.0); EdgeValue(55.0); EdgeValue(23.0); EdgeValue(59.0); NoEdge |] |] let matrix4_15 = Array2D.init 15 15 (fun i j -> matrix4_15_aa.[i].[j]) // create as Array2D // TSP node let start4_15 = TSPcreateStartState matrix4_15 let tspCost4_15 = TSPcost matrix4_15 let (bestValue4_15, solution4_15) = BandBminimize tspCost4_15 TSPg branchTSP TSPmoreToDo start4_15 System.Double.PositiveInfinity printfn "Solution 4_15:" printfn "tour cost = %f" (bestValue4_15) printfn "%A" solution4_15.EdgeList printfn "\nDONE" System.Console.ReadKey() |> ignore // don't close the output window until a key is hit 0 |
Running all of these examples with and without the ‘DFS” (depth first search) option (lines 42-43 of BandB
) results in:
Name of solution | Without DFS | With DFS | |||
---|---|---|---|---|---|
Problem | in code | Queue Size | Num Evals | Queue Size | Num Evals |
0-1 knapsack | solutionVars | 19 | 4 | 13 | 1 |
MaxSat 6 | solution2 | 23 | 4 | 16 | 3 |
MaxSat 15 | solution2_rand | 6105 | 70 | 5954 | 69 |
TSP 3 | solution3 | 12 | 1 | 20 | 2 |
TSP 5 | solution4 | 24 | 5 | 27 | 6 |
TSP 15 | solution4_15 | 1184 | 2 | 1265 | 3 |
As can be seen the DFS option doesn’t always help. The MaxSat 15 problem has 15 (binary) varaibles, so there are 215 = 32,768 possible combinations and 216 – 1 = 65,535 nodes in the search tree, however the branch and bound method found the solution with a fraction of these numbers. The savings for TSP are more impressive. As TSP is basically a weighted Hamiltonian cycle, so we can consider this number of possible cycles as the number of possible TSP solutions. We know there are (n-1)!/2 Hamilitonian cycles in a complete graph of n nodes (vertices) [see this]. For TSP 15, which is a complete graph of 15 nodes, this is 653,837,184,000 but again we solved this evaluating and searching much more effectively.
There are other things that could be done with the core method but we will leave it here. But one additional observation is that if the sorting option is used, then there should be better ways to insert the new items (toQueue
) into it. Right now the new items are added to the front of the queue (which simply a list) and then a sort (or reverseSort) is employed, but an available heap/priority queue could be used to get better average performance. As queue sizes are not excessive, this is also left for another time.
Well we now have a generalized branch and bound routine that can either minimize of maximize. It can be used for any problem as long as one can define the f
, g
, branch
and unFinished
functions for the domain. We encountered uses for many of F#’s features along the way but there are some things in F# we didn’t cover:
- option types (mentioned breifly)
- units of measure
- Sequences and lazy evaluation
- Annotations and reflection
- Code quotations
- Exceptions
- Code documentation
-
some things not covered yet, but will be by the end
- Testing
- Performance analysis
- Mailboxes (in Part IV)
- Object-oriented programming and classes
- Coupling to the .NET libraries
Download final Part II code
In this final version, I changed some variable and types names as alluded to before that were not necessarily shown here, but the important changes have been discussed.
We’ve created a lot of code and it looks like it works, but we need to test it … on to Part III