Feasibleshould 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.
Nextshould return an
Expanderis able to return states that we're interested in reaching from a given state. For a routing problem,
Nextmight attempt to insert a request into an existing set of routes anywhere it could make sense to do so. For the knapsack problem,
Nextmerely considers whether to include or exclude another item.
Valuemethod to tell Hop the value of each state. An example should make this all clear.
Ris 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.
Ris our first feasible solution to the knapsack, so we marks it as the "incumbent solution."
R1correspond to those two options for item 1. Together they form layer 1 of our diagram.
R1have remaining capacity in the knapsack, so they are feasible. We order these by descending value and determine that
R1is a better solution than our current incumbent,
R. We save
R1as our new incumbent and skip
R0as it is worse than
R11improves on the value of our current incumbent,
R1. We save
R11as our new incumbent and skip the other solutions.
R111exceeds our weight limit. Thus, we remove it from consideration as an infeasible state. Of the remaining states,
R101is the best and improves upon our incumbent,
R101as our optimal solution. It provides the most value without exceeding our weight limit.
R111off the graph since it isn't feasible.
Expander. We have two different types of
Eagerwill generate all of its child states at once, but
Lazycan 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.
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.