reset password
Author Message
smoon2
Posts: 9
Posted 22:28 Sep 27, 2019 |

1. Since branch and bound isn't bottom-up (I think), there isn't a 2D array that stores progressive answers, is that correct?

2. Is BBSolver.__call__ called here, line 33 of solver.py?

  (value, taken_items_sorted_by_density) = solver(

      items_count, capacity, items_sorted_density, verbose_tracking)

rabbott
Posts: 1649
Posted 23:16 Sep 27, 2019 |

Branch-and-Bound is bottom-up--even though the video makes it look top-down. It runs through the elements one at a time, either taking or not taking each one. (Each such decision doubles the number of partial potential solutions one has. That's what's stored on the queue.)

 

One of the arguments to apply_solver is solver. 

apply_solver is called from the following list comprehension in solve_a_dataset.

results = [apply_solver(solver, items_count, capacity, sorted_items, verbose_outline, verbose_tracking)  for solver in solvers]

solvers is an iterable collection of solver functions. 

solvers = (greedy_by_density, bb_solver, dynamic_prog)

So the line you are referring tp calls the functions in solvers one at a time. Each solver is given the opportunity to solve the given dataset.

When solver is bb_solver, that function in the file bb_solver is called. In turn in calls 

BBSolver(items_count, capacity, items_sorted_density, verbose_tracking)()

That line instantiates BBSolver and then calls its __call__ method. So you were right, but not as directly as the question suggests.