Feasible
and Next
. Feasible
should return true if a state is actionable, meaning it can be implemented in the real world. What this means depends on the model. For example, in a routing problem, feasibility may imply that each of a set of customer requests has been planned for. In the knapsack problem discussed below, it means that the knapsack's capacity is not exceeded.Next
should return an Expander
. An Expander
is able to return states that we're interested in reaching from a given state. For a routing problem, Next
might attempt to insert a request into an existing set of routes anywhere it could make sense to do so. For the knapsack problem, Next
merely considers whether to include or exclude another item.Value
method to tell Hop the value of each state. An example should make this all clear.R
is an empty set of items. Its weight and value are both 0. We also call this the root "layer" and say it has a depth of 0. It is a feasible knapsack because we haven't exceeded the capacity, but it isn't a very useful one either.R
R
. R
is our first feasible solution to the knapsack, so we marks it as the "incumbent solution."R0
and R1
correspond to those two options for item 1. Together they form layer 1 of our diagram.R0
R1
R0
and R1
have remaining capacity in the knapsack, so they are feasible. We order these by descending value and determine that R1
is a better solution than our current incumbent, R
. We save R1
as our new incumbent and skip R0
as it is worse than R1
.R00
R01
R10
R11
R11
improves on the value of our current incumbent, R1
. We save R11
as our new incumbent and skip the other solutions.R000
R001
R010
R011
R100
R101
R110
R111
R111
exceeds our weight limit. Thus, we remove it from consideration as an infeasible state. Of the remaining states, R101
is the best and improves upon our incumbent, R11
.R101
as our optimal solution. It provides the most value without exceeding our weight limit.R111
off the graph since it isn't feasible.Next
returns an Expander
. We have two different types of Expanders
: Eager
and Lazy
.Eager
will generate all of its child states at once, but Lazy
can be configured to merely generate a subset of them up to our expansion limit. We defer states that could potentially generate more child states than the limit allowed so they can later be used to generate even more states until they are exhausted. If our expansion limit is set to 2, that means that even if a node could generate 10 child nodes, we will only consider the first 2 child nodes and defer the rest for a subsequent pass.R
, R1
, R11
, and R101
. Each improves on the last solution. We then continue searching the rest of the state space. If we find a better feasible state, we'll use that as a new incumbent.Next
method.