(5th-May-2020)
In iterative best improvement, the neighbor of the current selected node is one that optimizes some evaluation function. In greedy descent, a neighbor is chosen to minimize an evaluation function. This is also called hill climbing or greedy ascent when the aim is to maximize. We only consider minimization; if you want to maximize a quantity, you can minimize its negation.
A local optimum is an assignment such that no neighbor improves the evaluation function. This is also called a local minimum in greedy descent, or a local maximum in greedy ascent.
For example, : Consider the delivery scheduling in Example 4.8. Suppose gradient descent starts with the assignment A=2, B=2, C=3, D=2, E=1. This assignment has an evaluation of 3, because it does not satisfy A ≠B, B≠D, and C<D. Its neighbor with the minimal evaluation has B=4 with an evaluation of 1 because only C<D is unsatisfied. This is now a local minimum. A random walk can then change D to 4, which has an evaluation of 2. It can change A to 4, with an evaluation of 2, and then change B to 2 with an evaluation of zero, and a solution is found.
Comments