Search by changing a candidate
Suppose a timetable is already feasible, but its score could improve. A local search algorithm changes one candidate at a time instead of constructing a full path from an initial state to a goal. Its effectiveness depends on the moves we allow: exchanging two assignments may reveal an improvement that changing just one assignment cannot. The score, the representation and the neighborhood are all parts of the algorithm.
Definition 19.1.1
(Neighborhood and local maxima)
Let be a nonempty finite set of feasible states, a score to maximize, and the neighbors permitted from . The neighborhood need not be symmetric. A strict local maximum has for every ; a weak local maximum has for every neighbor. If is empty, both conditions hold vacuously. A global maximum compares to all of . A weak local maximum need not be global, nor must a global maximum be a strict local maximum when equal scores occur.
Definition 19.1.2
(Hill-climbing variants)
A strict-improvement hill climber repeatedly replaces by any neighbor with ; if none exists, it stops. Steepest ascent chooses a neighbor with largest score, using a specified tie rule if several are best. A first-improvement method instead takes the first improving neighbor in a specified enumeration. Different choices may lead to different endpoints. Feasibility is guaranteed here because each is a subset of ; a real implementation must check that its move generator satisfies this contract.
Theorem 19.1.3
(Termination and what stopping proves)
On finite , every strict-improvement run stops after at most moves, regardless of how improving neighbors are chosen. Its endpoint is a weak local maximum for the stated neighborhood. It need not maximize over .
Proof and limits
Proof
(No state is visited twice)
Scores increase strictly at each move. Thus no state can be visited twice: a repeated state would have the same score as before, contradicting strict increase along the intervening moves. A run has at most distinct states and therefore at most moves. At the endpoint there is no neighbor of strictly greater score, which is exactly the weak local-maximum condition. This proof gives neither a small running time when is exponentially large nor a global-optimality certificate. Evaluating neighbors can itself be expensive.
Proof X-ray
The role of finiteness and strictness
Finiteness bounds the number of distinct states, while strict improvement rules out revisiting one. Removing either assumption breaks this argument. For example, on the nonnegative integers with neighbors and score , strict improvement never stops.
A complete basin calculation
Worked example 19.1.4
(Steepest ascent on a five-state chain)
Consider states with undirected edges –, –, –, – and respective scores . Steepest ascent from or stops at . From , the neighbor has score , which is better than 's score , so the path continues through to . The full mapping is , , , , . The endpoint is a strict local maximum of score , while is the unique global maximum of score . The attraction basins for this deterministic algorithm are and . A different move rule could give different basins on another graph; a basin belongs to an algorithm, not just a score function.
Counterexample mode
Local optimality is a neighborhood statement
At neither adjacent state improves the score, although has a higher score. Adding the permitted edge – changes the neighborhood and lets steepest ascent escape immediately. Changing the allowed moves changes the problem being solved, even if every candidate keeps the same score.
Equal scores and sideways moves
Strict improvement stops on a plateau even if a path of equal-score moves leads to a better state. A sideways move goes to a neighbor of equal score, and we allow it only when no neighbor improves the score.
Proposition 19.1.5
(A sideways-move limit restores termination)
Let be finite, and suppose a run makes strict improvements whenever one exists and otherwise a sideways move, with at most consecutive sideways moves, the count resetting at each strict move. Then the run makes at most strict moves and at most sideways moves, so it stops after at most moves.
Proof
(Counting strict and sideways moves)
Strict moves strictly raise the score, and sideways moves keep it unchanged, so the score never decreases along a run. A state cannot be revisited after a strict move, since the score would have to come back down. Hence the strict moves visit distinct scores in increasing order and there are at most of them. Before the first strict move, between consecutive strict moves and before stopping there are at most stretches of sideways moves, each of length at most . This gives at most sideways moves, and the total follows by addition.
Worked example 19.1.6
(A plateau that hides an exit, and one that does not)
Let –– be a chain with scores . Starting at , the strict rule stops immediately because ties and no neighbor improves. With , a sideways move from to is allowed, and then has the strictly better neighbor , so the run reaches with one sideways and one strict move.
Now take a two-state plateau – with equal scores. An unrestricted sideways rule may alternate forever. With the run goes from to , has used its one allowed consecutive sideways move, and stops at . The endpoint after the limit may have an untried equal-score exit; it is not evidence that the entire plateau was explored.
One alternative is to systematically search the connected equal-score region for an improving exit. That requires storing visited states and can consume far more memory than retaining only a current candidate. Directed neighborhoods require directed reachability: an equal-score edge usable from to need not be usable backwards.
Independent restarts and their cost
Fix a possibly randomized single-run procedure, including its stopping and success test. A run succeeds when it returns a global maximizer, and let its probability be under a specified initial-state distribution and all random choices within the run.
Theorem 19.1.7
(Success under independent restarts)
If runs are independent and identically distributed, the probability of at least one success in runs is
If , this tends to one as grows, and the number of runs up to and including the first success has mean . If , restarting never succeeds, and if no finite gives certainty.
Proof
(Complement rule and a geometric series)
All failures have probability by independence, and the complement of "all fail" is "at least one success". This is not justified merely by naming a procedure “random restart”: reusing dependent random choices or changing the starting distribution may invalidate the formula.
For the mean, for , since the first runs must fail. Summing these tail probabilities gives the geometric series . This counts runs, not neighbor evaluations; runs can have different costs.
Worked example 19.1.8
(Restarts on the five-state chain)
For the five-state example with a uniformly random start and deterministic steepest ascent, a run succeeds exactly when it starts in , so . Three independent starts succeed at least once with probability , and the expected number of runs to the first success is . The extreme cases are consistent with the theorem: if the start were always , then and no number of restarts helps; if it were always , then and a single run suffices.
Concept lensStructural
Optimizing a score versus reaching a goal
A local maximum certifies absence of a permitted improving move, not absence of a better state. A restart probability quantifies repeated runs under a fixed distribution; it does not certify that any particular output is globally optimal. Both statements depend on the exact move and success definitions.
Common mistakes
Common mistake
(Expecting earlier failures to raise the next success probability)
Two independent failures still leave the third run with success probability in the five-state example; past failures do not increase it. The probability of at least one success rises with only because more independent chances are given, not because the runs "owe" a success.
Common mistake
(Measuring by checking whether the endpoint is globally optimal)
In a real problem the global optimum may be unknown, so one cannot generally measure by checking whether an endpoint is globally optimal. A known target score supplies a different observable success event, whose probability must be defined afresh.
Exercises
Exercise 19.1.9
(On a chain ––– with scores , list the endpoints of strict steepest ascent from each state. Distinguish weak and strict local maxima.)
Core
Solution(3)
- 1
Trace strict steepest ascent from each state
From the only neighbor has score , so it moves to . At the neighbors have scores and , and neither is strictly larger than , so it stops. From the neighbor has score , so it moves to , where it stops. The endpoints are , , , .
- 2
Classify the local maxima
Key step
has scores and among its neighbors, so and hold: it is weak but not strict, because ties it. The state has the neighbor with , so it is not a local maximum. The state beats its only neighbor, so it is strict.
Because: A weak local maximum needs for every neighbor; a strict one needs .
- 3
State the conclusion
The weak local maxima are and , and the strict local maximum is alone. The better state is unreachable from by strict improvement, even though the plateau has an exit.
Exercise 19.1.10
(In the same chain, add the rule that from a state with no improving neighbor one may make one sideways move, then resume strict ascent; at most one consecutive sideways move is allowed. Starting from , trace one valid run and explain why the tie policy matters at .)
Core
Solution(2)
- 1
Trace the run
is a strict move. At no neighbor improves, so the sideways rule applies and the only equal-score neighbor is taken. From the neighbor improves, so is strict. The run is .
- 2
Explain the tie policy
In this chain has a single equal-score neighbor, , but the rule still has to state whether it takes that neighbor or stops. On a larger plateau, which tie is selected can determine the outcome. The cap prevents indefinite consecutive sideways moves but does not guarantee that all exits are found.
Because: The rule must say whether the sideways move is taken and which equal-score neighbor is chosen.
Exercise 19.1.11
(A single run succeeds with probability . For four independent runs find the probability of at least one success and the expected number of runs to the first success. Would the same formula be justified if all starts were the same single random draw?)
Core
Solution(2)
- 1
Apply the restart formula
The probability of at least one success is . The mean waiting time is runs.
- 2
Examine reuse of one random draw
With a single reused random start the outcomes can be perfectly dependent. If the deterministic procedure succeeds exactly on the same quarter of the starting states, all four runs succeed together or fail together, so the probability of at least one success stays and the formula does not apply.
Because: The formula needs the runs to be independent.
Exercise 19.1.12
(A finite directed graph has scores , , and edges , , . Give the strict-ascent endpoint from and explain why it does not contradict the termination theorem.)
Foundation
Solution(2)
- 1
Trace the run from
From the only outgoing neighbor is with , so the run moves to . The only outgoing neighbor of is with score , so no improving move exists and the run stops at .
- 2
Compare with the theorem
The higher-scoring is not an outgoing neighbor of , so it cannot be reached. Finiteness and strict increase still guarantee termination, and is a weak local maximum for the directed neighborhood. The theorem never claimed global optimality or symmetric edges.