Hill Climbing / Random Restart

Why Hill Climbing / Random Restart Matters

Suppose a candidate timetable, placement, or configuration has a numerical quality score. You can make small legal changes and evaluate their effects, but enumerating every complete candidate is impractical. Hill climbing keeps one current state and repeatedly replaces it with a better neighbor. It can improve a candidate quickly without storing a large search frontier.

The limitation is local information. A state can beat every immediately available alternative while a much better state lies beyond a valley or a flat shoulder. Random restart starts fresh from another feasible state and keeps the best result found across all attempts. A restart is a new initialization, so its current score can fall even though every accepted local move is uphill.

This lesson implements deterministic steepest-ascent hill climbing with strict improvement and reproducible random restarts. A small integer-indexed landscape makes every score, neighbor comparison, and restart visible. The general pattern applies to implicit configuration spaces with a suitable neighborhood and evaluator; it does not promise a global optimum after a fixed number of attempts.

Core Concepts and Terminology

We maximize an objective $f:S\to\mathbb{R}$ over feasible states $S$. A neighborhood $N(x)$ specifies the legal small changes from $x$. “Local” is defined by this neighborhood: changing the move set can change which states count as local maxima. For minimization, reverse the comparisons or maximize a safely computed negative cost.

At a current state $x$, steepest ascent evaluates every candidate in $N(x)$ and chooses a neighbor $y$ with maximum score. It commits the move only if $f(y)\gt f(x)$. With strict improvement, equal-valued candidates do not move the state. A completed unsuccessful scan establishes a weak local maximum:

$$f(x)\ge f(y)\qquad\text{for every }y\in N(x).$$

That includes a plateau point with an equal-valued neighbor; it does not establish an isolated peak or global optimality. A basin of attraction is the set of starting states that lead to the same stopping state under a fixed neighborhood, tie policy, and completed hill-climbing rule.

The runnable adapter uses $S=\{0,1,\ldots,n-1\}$, a table-valued objective, and neighbors $x-1$ and $x+1$ when in range. Local step size is one integer index. In the worked landscape, local peaks at $2$, $6$, and $10$ have scores $5$, $8$, and $10$. Starting at $0$ reaches only the first peak. The saved incumbent is the best valid state evaluated anywhere, which need not be the current state or even a committed path state after an interrupted scan.

How Hill Climbing / Random Restart Works, Step by Step

1. Define feasible states, scores, and neighbor order. The example scans the left neighbor before the right. Candidate selection starts with the current state and its cached score. A strictly higher neighbor replaces the candidate; tied better neighbors keep the first examined one, while equality with the current state leaves it in place.
2. Initialize the persistent incumbent and one random generator. An explicit has_best flag handles all-negative scores and zero evaluations. Seed the generator once per whole search, not once per restart. The first run uses the supplied starting state; the requested number of extra restarts follows it.
3. Evaluate a run's starting state. Check the shared evaluation budget before the call. Record a valid start in its path and update the incumbent if this is the first observation or a strict improvement. Reset only this run's accepted-move count.
4. Check the per-run move cap before scanning. If it is reached, finish that run as MOVE_LIMIT. Do not label the endpoint local merely because the run was stopped. With a zero move cap, only the starting state is evaluated.
5. Scan the complete neighborhood. Evaluate neighbors in order, recording each query. Update the incumbent on every valid observation. Select the best strictly improving candidate, but do not move the current state while the scan is incomplete. If the global evaluation budget blocks a query, record the partial scan, commit no move, and end the whole search with EVAL_LIMIT.
6. Commit or stop locally. After a complete scan, count it. If no better candidate was found, finish the run as LOCAL. Otherwise assign the selected state and reuse its already evaluated score, increment the move counters, append the new state/score to the path, and scan again.
7. Restart while attempts remain. Draw another feasible starting index, even if a previous restart chose the same one. Keep the incumbent and global evaluation count. If all scheduled runs finish as LOCAL or MOVE_LIMIT, report FINISHED; this status describes the schedule, not a proof of global optimality.

Portable restart draws. All three programs use integer state $z$ and recurrence

$$z\leftarrow48271z\bmod2147483647,\qquad1\le z\le2147483646.$$

Let $M=2147483646$ and $L=M-(M\bmod n)$. Form $v=z-1$. Accept $v$ only if $v\lt L$, then return $v\bmod n$; otherwise draw again. The accepted range has a multiple of $n$ elements, so every index has the same number of preimages if raw draws are independent and uniform. This removes the unequal-residue mapping of naive modulo conversion. It does not turn a deterministic pseudorandom sequence into independent random draws. C++ and Java use 64-bit arithmetic for the multiplication.

The single generator advances across all runs. Its draw counter includes rejected raw values; the first user-specified start consumes no draw. A selected restart is recorded even if no evaluation budget remains to evaluate it. This makes the exact stopping point and final generator state reproducible.

flowchart TD
    A["Validate input; initialize incumbent and one RNG"] --> B["Choose supplied start or next restart"]
    B --> C{"Start evaluation fits global budget?"}
    C -->|No| D["Return EVAL_LIMIT and best observation"]
    C -->|Yes| E["Evaluate start; update incumbent; reset move count"]
    E --> F{"Per-run move cap reached?"}
    F -->|Yes| G["End run as MOVE_LIMIT"]
    F -->|No| H["Candidate is current; begin ordered neighbor scan"]
    H --> I{"Unscanned neighbor left?"}
    I -->|Yes| J{"Evaluation fits global budget?"}
    J -->|No| K["Record partial scan; commit no move"]
    K --> D
    J -->|Yes| L["Evaluate neighbor; update incumbent and best candidate"]
    L --> I
    I -->|No| M["Count complete scan"]
    M --> N{"Candidate strictly improves current?"}
    N -->|Yes| O["Commit candidate and cached score; count move"]
    O --> F
    N -->|No| P["End run as LOCAL"]
    G --> Q{"Another restart scheduled?"}
    P --> Q
    Q -->|Yes| B
    Q -->|No| R["Return FINISHED and persistent incumbent"]

Worked Example with a Full Trace

Use the ordered score table

$$[f(0),\ldots,f(11)]=[0,2,5,3,1,4,8,6,2,5,10,7].$$

Start at $0$, request $3$ extra restarts, use seed $13$, allow at most $256$ accepted moves per run, and share an evaluation budget of $1{,}000{,}000$. There are $4$ total scheduled runs. These bounds allow every run to finish locally in this example. The first start is fixed and consumes no random draw.

For $n=12$, the acceptance threshold is $L=2147483640$. The generated raw states below all pass rejection sampling:

The following table records every starting evaluation and complete neighborhood scan. A probe x:value means that state was queried at that point, including repeated queries. Candidate selection begins at the current state, so only a strictly higher value causes a move. Counts are global and cumulative; start rows do not count as scans.

All accepted paths and scores are therefore: run $0$, $0:0\to1:2\to2:5$; run $1$, $6:8$; run $2$, $10:10$; run $3$, $4:1\to5:4\to6:8$. In the final run, the current score resets to $1$, then climbs to $8$, while the saved best remains $10$. At the last scan, state $6$ has neighbor scores $4$ and $6$, both below $8$, and is correctly marked local.

The complete result is FINISHED, best evaluated state $10$ with score $10$, $19$ objective evaluations, $8$ completed scans, and $4$ accepted moves. There are $3$ raw restart draws, no rejections, and final generator state $1755747989$. A separate full scan of the supplied table confirms that score $10$ is globally maximal; the hill-climbing stopping rules themselves did not establish that fact.

Implementation in Python, C++, and Java

Each complete program runs the same strict steepest-ascent policy, with the same neighbor order and seeded restart mapping. The objective is scores[x] on integer indices; the local neighborhood contains only in-range adjacent indices. Current objective values are reused after accepted moves, but neighbor observations are deliberately re-evaluated on later scans. There is no memoization across different scans or restarts.

Input contract. The non-null score collection has $1\le n\le256$ integer entries, each in $[-10^9,10^9]$. The first start is an integer in $[0,n-1]$, extra restarts in $[0,32]$, seed in $[1,2147483646]$, accepted-move cap per run in $[0,256]$, and total objective-evaluation budget in $[0,10^6]$. Invalid sizes, score ranges, and numeric search parameters are rejected. Scores are copied, the caller's collection is unchanged, and each call creates a fresh generator and search state.

The result includes status, has_best, best evaluated index and value, statistics [evaluations,scans,moves,rng_draws], final generator state, and run histories. Each run records its planned start, committed path with corresponding scores, all scan records, its reason, and evaluations spent in that run. Each scan stores its original state/value, queried neighbors in order, committed next state/value, completion flag, and global evaluation count. A partial scan records the original state as its next state because no move was committed.

LOCAL is issued only after a complete scan with no strictly better neighbor; it is a weak local-maximum certificate for this neighborhood. MOVE_LIMIT issues no such certificate. Global FINISHED means the requested schedule finished, including runs stopped by their move caps. Global EVAL_LIMIT means a required query was refused. If has_best is false, best index $-1$ and value $0$ are dummy fields; otherwise, even a negative best value is meaningful.

An evaluation is counted only when performed. Exactly consuming the budget does not cancel a move whose entire scan already completed, nor an empty-neighborhood local certificate. However, a later scheduled start or a missing neighbor query can then trigger EVAL_LIMIT. The move cap is checked before starting a new scan; therefore a state reached on the last allowed move is not automatically classified local. Zero evaluation budget returns no incumbent, while zero move cap still allows each available starting evaluation.

The incumbent includes every evaluated state, including candidates from an interrupted scan. Tied best scores retain the earliest observation; it is not a smallest-index rule. Because state IDs and scores are immutable scalars, keeping the incumbent is a safe value copy. A mutable configuration adapter must instead copy or otherwise preserve the best configuration before modifying the current one.

This explicit table is a teaching adapter: simply scanning all entries is the best way to obtain its exact global maximum in $O(n)$ time. Hill climbing is useful when states and neighbors are implicit and expensive to enumerate globally. The displayed evaluation count measures logical search queries, while input validation and copying also read the supplied table. Run with Python 3, C++14 or newer, or Java 17 or newer; save Java as Main.java.

from dataclasses import dataclass, field

P, A = 2_147_483_647, 48_271


class RandomStarts:
    def __init__(self, seed):
        self.state, self.draws = seed, 0

    def bounded(self, n):
        size = P - 1
        limit = size - size % n
        while True:
            self.state = A * self.state % P
            self.draws += 1
            value = self.state - 1
            if value < limit:
                return value % n


@dataclass
class Scan:
    state: int
    value: int
    probes: list
    next_state: int
    next_value: int
    complete: bool
    evaluations: int


@dataclass
class Run:
    start: int
    path: list = field(default_factory=list)
    values: list = field(default_factory=list)
    scans: list = field(default_factory=list)
    reason: str = ""
    evaluations: int = 0


@dataclass
class Result:
    status: str
    has_best: bool
    best_state: int
    best_value: int
    stats: list
    rng_state: int
    runs: list


def climb(scores, start, extra_restarts, seed, max_moves=256, budget=1_000_000):
    if (not 1 <= len(scores) <= 256 or
            any(type(v) is not int or not -1_000_000_000 <= v <= 1_000_000_000 for v in scores) or
            type(start) is not int or not 0 <= start < len(scores) or
            type(extra_restarts) is not int or not 0 <= extra_restarts <= 32 or
            type(seed) is not int or not 1 <= seed < P or
            type(max_moves) is not int or not 0 <= max_moves <= 256 or
            type(budget) is not int or not 0 <= budget <= 1_000_000):
        raise ValueError("invalid search parameters")
    values = list(scores)
    rng = RandomStarts(seed)
    evaluations = completed_scans = moves = 0
    has_best, best_state, best_value = False, -1, 0
    runs = []

    def evaluate(state):
        nonlocal evaluations, has_best, best_state, best_value
        if evaluations >= budget:
            return None
        evaluations += 1
        value = values[state]
        if not has_best or value > best_value:
            has_best, best_state, best_value = True, state, value
        return value

    def finish(status):
        return Result(status, has_best, best_state, best_value,
                      [evaluations, completed_scans, moves, rng.draws], rng.state, runs)

    for run_index in range(extra_restarts + 1):
        state = start if run_index == 0 else rng.bounded(len(values))
        run = Run(state)
        runs.append(run)
        before = evaluations
        value = evaluate(state)
        if value is None:
            run.reason = "EVAL_LIMIT"
            return finish("EVAL_LIMIT")
        run.path.append(state)
        run.values.append(value)
        accepted = 0
        while True:
            if accepted >= max_moves:
                run.reason = "MOVE_LIMIT"
                break
            candidate, candidate_value = state, value
            probes = []
            neighbors = ([state - 1] if state > 0 else []) + ([state + 1] if state + 1 < len(values) else [])
            for neighbor in neighbors:
                trial = evaluate(neighbor)
                if trial is None:
                    run.scans.append(Scan(state, value, probes, state, value, False, evaluations))
                    run.reason, run.evaluations = "EVAL_LIMIT", evaluations - before
                    return finish("EVAL_LIMIT")
                probes.append((neighbor, trial))
                if trial > candidate_value:
                    candidate, candidate_value = neighbor, trial
            completed_scans += 1
            run.scans.append(Scan(state, value, probes, candidate, candidate_value, True, evaluations))
            if candidate == state:
                run.reason = "LOCAL"
                break
            state, value = candidate, candidate_value  # Reuse the evaluated score.
            accepted += 1
            moves += 1
            run.path.append(state)
            run.values.append(value)
        run.evaluations = evaluations - before
    return finish("FINISHED")


def show(name, scores, start, restarts, seed, max_moves=256, budget=1_000_000):
    result = climb(scores, start, restarts, seed, max_moves, budget)
    best = f"{result.best_state}:{result.best_value}" if result.has_best else "NONE"
    print(f"{name}: {result.status}, best={best}")
    labels = ("evaluations", "scans", "moves", "rng_draws")
    print(", ".join(f"{k}={v}" for k, v in zip(labels, result.stats)) + f", rng_state={result.rng_state}")
    for index, run in enumerate(result.runs):
        print(f"run={index}, start={run.start}, end={run.reason}, evaluations={run.evaluations}")
        for i, (state, value) in enumerate(zip(run.path, run.values)):
            print(f"i={i}, x={state}, f={value}")


def main():
    landscape = [0, 2, 5, 3, 1, 4, 8, 6, 2, 5, 10, 7]
    show("worked", landscape, 0, 3, 13)
    show("no restart", landscape, 0, 0, 13)
    show("plateau", [0, 3, 3, 3, 7], 1, 0, 13)
    show("valley", [5, 1, 9], 0, 0, 13)
    show("negative scores", [-8, -2, -5], 0, 0, 13)
    show("move cap", landscape, 0, 0, 13, max_moves=1)
    show("partial scan", landscape, 4, 0, 13, budget=2)
    show("singleton", [7], 0, 2, 13)
    show("zero budget", landscape, 0, 3, 13, budget=0)
    print("checks = PASS")


if __name__ == "__main__":
    main()

#include <iostream>
#include <stdexcept>
#include <string>
#include <utility>
#include <vector>
using namespace std;
const long long P=2147483647,A=48271;
struct RandomStarts {
    long long state,draws=0;
    explicit RandomStarts(long long seed):state(seed) {}
    int bounded(int n) {
        long long size=P-1,limit=size-size%n;
        while(true) {
            state=A*state%P; ++draws;
            long long value=state-1;
            if(value<limit) return static_cast<int>(value%n);
        }
    }
};
struct Scan {
    int state; long long value;
    vector<pair<int,long long>> probes;
    int next_state; long long next_value;
    bool complete; long long evaluations;
};
struct Run {
    int start;
    vector<int> path;
    vector<long long> values;
    vector<Scan> scans;
    string reason;
    long long evaluations=0;
    explicit Run(int state):start(state) {}
};
struct Result {
    string status; bool has_best; int best_state; long long best_value;
    vector<long long> stats;
    long long rng_state;
    vector<Run> runs;
};
class Runner {
public:
    vector<long long> values;
    int start,extra_restarts,max_moves;
    long long budget,evaluations=0,completed_scans=0,moves=0;
    RandomStarts rng;
    bool has_best=false; int best_state=-1; long long best_value=0;
    vector<Run> runs;
    Runner(const vector<long long>& scores,int start,int restarts,long long seed,int limit,long long budget)
        :values(scores),start(start),extra_restarts(restarts),max_moves(limit),budget(budget),rng(seed) {
        if(values.empty() || values.size()>256 || start<0 || start>=static_cast<int>(values.size()) ||
           restarts<0 || restarts>32 || seed<1 || seed>=P || limit<0 || limit>256 || budget<0 || budget>1000000)
            throw invalid_argument("invalid search parameters");
        for(long long value:values) if(value < -1000000000 || value>1000000000) throw invalid_argument("invalid score");
    }
    bool evaluate(int state,long long& value) {
        if(evaluations>=budget) return false;
        ++evaluations; value=values[state];
        if(!has_best || value>best_value) { has_best=true; best_state=state; best_value=value; }
        return true;
    }
    Result finish(const string& status) const {
        return {status,has_best,best_state,best_value,{evaluations,completed_scans,moves,rng.draws},rng.state,runs};
    }
    Result run() {
        for(int run_index=0;run_index<=extra_restarts;++run_index) {
            int state=run_index==0 ? start : rng.bounded(static_cast<int>(values.size()));
            runs.emplace_back(state); Run& run=runs.back();
            long long before=evaluations,value=0;
            if(!evaluate(state,value)) { run.reason="EVAL_LIMIT"; return finish("EVAL_LIMIT"); }
            run.path.push_back(state); run.values.push_back(value);
            int accepted=0;
            while(true) {
                if(accepted>=max_moves) { run.reason="MOVE_LIMIT"; break; }
                int candidate=state; long long candidate_value=value;
                vector<pair<int,long long>> probes;
                vector<int> neighbors;
                if(state>0) neighbors.push_back(state-1);
                if(state+1<static_cast<int>(values.size())) neighbors.push_back(state+1);
                for(int neighbor:neighbors) {
                    long long trial=0;
                    if(!evaluate(neighbor,trial)) {
                        run.scans.push_back({state,value,probes,state,value,false,evaluations});
                        run.reason="EVAL_LIMIT"; run.evaluations=evaluations-before;
                        return finish("EVAL_LIMIT");
                    }
                    probes.push_back({neighbor,trial});
                    if(trial>candidate_value) { candidate=neighbor; candidate_value=trial; }
                }
                ++completed_scans;
                run.scans.push_back({state,value,probes,candidate,candidate_value,true,evaluations});
                if(candidate==state) { run.reason="LOCAL"; break; }
                state=candidate; value=candidate_value; // Reuse the evaluated score.
                ++accepted; ++moves;
                run.path.push_back(state); run.values.push_back(value);
            }
            run.evaluations=evaluations-before;
        }
        return finish("FINISHED");
    }
};
Result climb(const vector<long long>& scores,int start,int restarts,long long seed,int max_moves=256,long long budget=1000000) {
    Runner runner(scores,start,restarts,seed,max_moves,budget);
    return runner.run();
}
void show(const string& name,const vector<long long>& scores,int start,int restarts,long long seed,int max_moves=256,long long budget=1000000) {
    Result r=climb(scores,start,restarts,seed,max_moves,budget);
    cout<<name<<": "<<r.status<<", best=";
    if(r.has_best) cout<<r.best_state<<':'<<r.best_value; else cout<<"NONE";
    cout<<'\n';
    vector<string> labels={"evaluations","scans","moves","rng_draws"};
    for(size_t i=0;i<labels.size();++i) { if(i) cout<<", "; cout<<labels[i]<<'='<<r.stats[i]; }
    cout<<", rng_state="<<r.rng_state<<'\n';
    for(size_t index=0;index<r.runs.size();++index) {
        const Run& run=r.runs[index];
        cout<<"run="<<index<<", start="<<run.start<<", end="<<run.reason<<", evaluations="<<run.evaluations<<'\n';
        for(size_t i=0;i<run.path.size();++i) cout<<"i="<<i<<", x="<<run.path[i]<<", f="<<run.values[i]<<'\n';
    }
}
int main() {
    vector<long long> landscape={0,2,5,3,1,4,8,6,2,5,10,7};
    show("worked",landscape,0,3,13);
    show("no restart",landscape,0,0,13);
    show("plateau",{0,3,3,3,7},1,0,13);
    show("valley",{5,1,9},0,0,13);
    show("negative scores",{-8,-2,-5},0,0,13);
    show("move cap",landscape,0,0,13,1);
    show("partial scan",landscape,4,0,13,256,2);
    show("singleton",{7},0,2,13);
    show("zero budget",landscape,0,3,13,256,0);
    cout<<"checks = PASS\n";
}

import java.util.ArrayList;
import java.util.List;

public class Main {
    static final long P=2_147_483_647L,A=48_271L;
    static final class RandomStarts {
        long state,draws=0;
        RandomStarts(long seed) { state=seed; }
        int bounded(int n) {
            long size=P-1,limit=size-size%n;
            while(true) {
                state=A*state%P; ++draws;
                long value=state-1;
                if(value<limit) return (int)(value%n);
            }
        }
    }
    static final class Probe {
        final int state; final long value;
        Probe(int state,long value) { this.state=state; this.value=value; }
    }
    static final class Scan {
        final int state,nextState; final long value,nextValue,evaluations;
        final List<Probe> probes; final boolean complete;
        Scan(int state,long value,List<Probe> probes,int nextState,long nextValue,boolean complete,long evaluations) {
            this.state=state; this.value=value; this.probes=new ArrayList<>(probes); this.nextState=nextState;
            this.nextValue=nextValue; this.complete=complete; this.evaluations=evaluations;
        }
    }
    static final class Run {
        final int start;
        final List<Integer> path=new ArrayList<>(); final List<Long> values=new ArrayList<>();
        final List<Scan> scans=new ArrayList<>(); String reason=""; long evaluations=0;
        Run(int start) { this.start=start; }
    }
    static final class Result {
        final String status; final boolean hasBest; final int bestState; final long bestValue;
        final long[] stats; final long rngState; final List<Run> runs;
        Result(String status,boolean hasBest,int bestState,long bestValue,long[] stats,long rngState,List<Run> runs) {
            this.status=status; this.hasBest=hasBest; this.bestState=bestState; this.bestValue=bestValue;
            this.stats=stats.clone(); this.rngState=rngState; this.runs=new ArrayList<>(runs);
        }
    }
    static final class Runner {
        final long[] values; final int start,restarts,maxMoves; final long budget;
        final RandomStarts rng; long evaluations=0,completedScans=0,moves=0;
        boolean hasBest=false; int bestState=-1; long bestValue=0;
        final List<Run> runs=new ArrayList<>();
        Runner(long[] scores,int start,int restarts,long seed,int maxMoves,long budget) {
            if(scores.length<1 || scores.length>256 || start<0 || start>=scores.length || restarts<0 || restarts>32 ||
               seed<1 || seed>=P || maxMoves<0 || maxMoves>256 || budget<0 || budget>1_000_000)
                throw new IllegalArgumentException("invalid search parameters");
            for(long value:scores) if(value < -1_000_000_000L || value>1_000_000_000L) throw new IllegalArgumentException("invalid score");
            values=scores.clone(); this.start=start; this.restarts=restarts; this.maxMoves=maxMoves; this.budget=budget; rng=new RandomStarts(seed);
        }
        Long evaluate(int state) {
            if(evaluations>=budget) return null;
            ++evaluations; long value=values[state];
            if(!hasBest || value>bestValue) { hasBest=true; bestState=state; bestValue=value; }
            return value;
        }
        Result finish(String status) {
            return new Result(status,hasBest,bestState,bestValue,new long[]{evaluations,completedScans,moves,rng.draws},rng.state,runs);
        }
        Result run() {
            for(int index=0;index<=restarts;++index) {
                int state=index==0 ? start : rng.bounded(values.length);
                Run run=new Run(state); runs.add(run); long before=evaluations;
                Long first=evaluate(state);
                if(first==null) { run.reason="EVAL_LIMIT"; return finish("EVAL_LIMIT"); }
                long value=first; run.path.add(state); run.values.add(value); int accepted=0;
                while(true) {
                    if(accepted>=maxMoves) { run.reason="MOVE_LIMIT"; break; }
                    int candidate=state; long candidateValue=value;
                    List<Probe> probes=new ArrayList<>(); List<Integer> neighbors=new ArrayList<>();
                    if(state>0) neighbors.add(state-1);
                    if(state+1<values.length) neighbors.add(state+1);
                    for(int neighbor:neighbors) {
                        Long trial=evaluate(neighbor);
                        if(trial==null) {
                            run.scans.add(new Scan(state,value,probes,state,value,false,evaluations));
                            run.reason="EVAL_LIMIT"; run.evaluations=evaluations-before; return finish("EVAL_LIMIT");
                        }
                        probes.add(new Probe(neighbor,trial));
                        if(trial>candidateValue) { candidate=neighbor; candidateValue=trial; }
                    }
                    ++completedScans;
                    run.scans.add(new Scan(state,value,probes,candidate,candidateValue,true,evaluations));
                    if(candidate==state) { run.reason="LOCAL"; break; }
                    state=candidate; value=candidateValue; ++accepted; ++moves;
                    run.path.add(state); run.values.add(value);
                }
                run.evaluations=evaluations-before;
            }
            return finish("FINISHED");
        }
    }
    static Result climb(long[] scores,int start,int restarts,long seed,int maxMoves,long budget) {
        return new Runner(scores,start,restarts,seed,maxMoves,budget).run();
    }
    static void show(String name,long[] scores,int start,int restarts,long seed,int maxMoves,long budget) {
        Result r=climb(scores,start,restarts,seed,maxMoves,budget);
        System.out.println(name+": "+r.status+", best="+(r.hasBest ? r.bestState+":"+r.bestValue : "NONE"));
        String[] labels={"evaluations","scans","moves","rng_draws"}; StringBuilder out=new StringBuilder();
        for(int i=0;i<labels.length;++i) { if(i>0) out.append(", "); out.append(labels[i]).append('=').append(r.stats[i]); }
        System.out.println(out.append(", rng_state=").append(r.rngState));
        for(int index=0;index<r.runs.size();++index) {
            Run run=r.runs.get(index);
            System.out.println("run="+index+", start="+run.start+", end="+run.reason+", evaluations="+run.evaluations);
            for(int i=0;i<run.path.size();++i) System.out.println("i="+i+", x="+run.path.get(i)+", f="+run.values.get(i));
        }
    }
    public static void main(String[] args) {
        long[] landscape={0,2,5,3,1,4,8,6,2,5,10,7};
        show("worked",landscape,0,3,13,256,1_000_000);
        show("no restart",landscape,0,0,13,256,1_000_000);
        show("plateau",new long[]{0,3,3,3,7},1,0,13,256,1_000_000);
        show("valley",new long[]{5,1,9},0,0,13,256,1_000_000);
        show("negative scores",new long[]{-8,-2,-5},0,0,13,256,1_000_000);
        show("move cap",landscape,0,0,13,1,1_000_000);
        show("partial scan",landscape,4,0,13,256,2);
        show("singleton",new long[]{7},0,2,13,256,1_000_000);
        show("zero budget",landscape,0,3,13,256,0);
        System.out.println("checks = PASS");
    }
}

Expected standard output, identical in all three languages:

• worked: FINISHED, best=10:10
• evaluations=19, scans=8, moves=4, rng_draws=3, rng_state=1755747989
• run=0, start=0, end=LOCAL, evaluations=6
• i=0, x=0, f=0
• i=1, x=1, f=2
• i=2, x=2, f=5
• run=1, start=6, end=LOCAL, evaluations=3
• i=0, x=6, f=8
• run=2, start=10, end=LOCAL, evaluations=3
• i=0, x=10, f=10
• run=3, start=4, end=LOCAL, evaluations=7
• i=0, x=4, f=1
• i=1, x=5, f=4
• i=2, x=6, f=8
• no restart: FINISHED, best=2:5
• evaluations=6, scans=3, moves=2, rng_draws=0, rng_state=13
• run=0, start=0, end=LOCAL, evaluations=6
• i=0, x=0, f=0
• i=1, x=1, f=2
• i=2, x=2, f=5
• plateau: FINISHED, best=1:3
• evaluations=3, scans=1, moves=0, rng_draws=0, rng_state=13
• run=0, start=1, end=LOCAL, evaluations=3
• i=0, x=1, f=3
• valley: FINISHED, best=0:5
• evaluations=2, scans=1, moves=0, rng_draws=0, rng_state=13
• run=0, start=0, end=LOCAL, evaluations=2
• i=0, x=0, f=5
• negative scores: FINISHED, best=1:-2
• evaluations=4, scans=2, moves=1, rng_draws=0, rng_state=13
• run=0, start=0, end=LOCAL, evaluations=4
• i=0, x=0, f=-8
• i=1, x=1, f=-2
• move cap: FINISHED, best=1:2
• evaluations=2, scans=1, moves=1, rng_draws=0, rng_state=13
• run=0, start=0, end=MOVE_LIMIT, evaluations=2
• i=0, x=0, f=0
• i=1, x=1, f=2
• partial scan: EVAL_LIMIT, best=3:3
• evaluations=2, scans=0, moves=0, rng_draws=0, rng_state=13
• run=0, start=4, end=EVAL_LIMIT, evaluations=2
• i=0, x=4, f=1
• singleton: FINISHED, best=0:7
• evaluations=3, scans=3, moves=0, rng_draws=2, rng_state=226391675
• run=0, start=0, end=LOCAL, evaluations=1
• i=0, x=0, f=7
• run=1, start=0, end=LOCAL, evaluations=1
• i=0, x=0, f=7
• run=2, start=0, end=LOCAL, evaluations=1
• i=0, x=0, f=7
• zero budget: EVAL_LIMIT, best=NONE
• evaluations=0, scans=0, moves=0, rng_draws=0, rng_state=13
• run=0, start=0, end=EVAL_LIMIT, evaluations=0
• checks = PASS

Complexity, Correctness, and Invariants

Let $N$ be the number of feasible states in a finite search space, $B$ the maximum neighborhood size, $K=R+1$ total scheduled starts, $M$ the per-run accepted-move cap, and $C_f$ an upper bound on objective-evaluation cost. Every accepted move strictly increases the objective. A run cannot revisit a state, so it accepts at most $N-1$ moves; a completed no-improvement scan may add one final scan. A conservative bound on scans per run is $\min(M+1,N)$, with fewer scans when the cap is zero or the run stops early.

Ignoring interruption, the evaluation bound is

$$E\le K\left(1+B\min(M+1,N)\right).$$

This counts one starting evaluation plus all neighbor queries. A global evaluation cap can reduce work but does not establish any optimum. With $G$ raw generator draws, generic search work is bounded by $O(K(1+B\min(M+1,N))(C_f+1)+G)$, also charging neighbor-generation work when it is not constant per neighbor.

For these programs, $B\le2$ and table lookups cost constant time. Let $S$ count completed scans and any final partial scan, and $A_{\mathrm{move}}$ accepted moves. Construction and execution take $O(n+K+E+S+G)$ time. Actual additional space is $O(n+K+S+A_{\mathrm{move}})=O(n+K+S)$ because the copied score table, every run, every path, and every at-most-two-probe scan are retained. Without the histories, the local-search core needs only constant scalar state for this one-dimensional adapter, in addition to the objective representation. A generic state or materialized neighborhood can require much more memory.

Best, average, worst. A zero-budget request performs no search evaluations but still validates/copies $O(n)$ input. With positive caps, an already local start needs one starting query and a neighborhood scan; the routine still processes later scheduled restarts. Long increasing chains can require $\Theta(N)$ accepted states and scans per unrestricted run. There is no landscape-independent average run length or global-success guarantee: both depend on the neighborhood, scores, tie policy, initialization distribution, and truncation caps.

Correctness of the local result. Current score equals the cached objective of the current feasible state. A complete scan selects the highest-scoring candidate among the current state and all neighbors under the specified tie policy. A committed move is therefore legal and strictly improving; failure to improve after a full scan establishes the weak local inequality. Finite strict ascent proves termination of an unrestricted discrete run, but not global optimality. The incumbent invariant is separate: after every observation, it equals the best evaluated score so far and never decreases, including during restarts and interrupted scans.

What random restarts can promise under an ideal model. Suppose each completed random-start run independently reaches a desired set with the same probability $p\gt0$. For $q$ such random runs,

$$\Pr(\text{at least one success})=1-(1-p)^q,\qquad\mathbb{E}[\text{runs until first success}]=\frac1p.$$

Here $q$ counts random runs; the code's first user-specified run is fixed. Its $R$ extra starts provide $R$ random opportunities in that idealized model. For $0\lt p\lt1$ and desired failure probability $\delta\in(0,1)$, it suffices to choose

$$q\ge\left\lceil\frac{\log\delta}{\log(1-p)}\right\rceil.$$

This requires knowing or justifying $p$ and independence. The formula does not apply unchanged to correlated starts, reseeding with the same seed, changing policies, or budget-truncated runs. A fixed pseudorandom seed makes this implementation deterministic; it is not evidence for an independence assumption. The implementation always processes its schedule unless the evaluation budget blocks it; it does not know when the true global optimum has been found.

For the worked landscape, full deterministic climbs produce basins $\{0,1,2,3\}\to2$, $\{4,5,6,7,8\}\to6$, and $\{9,10,11\}\to10$. An ideal independent uniform start reaches the global peak with probability $p=3/12=1/4$. The fixed initial start $0$ fails; three ideal random starts succeed with probability $1-(3/4)^3=37/64\approx0.578125$. Our particular seed happens to choose a successful start, which is one reproducible outcome rather than a probability estimate.

On a finite space, independent uniform starts give a global maximizer positive probability even by selecting it directly, so success probability tends to one as the number of completed attempts grows. A finite schedule still offers no certainty. In continuous spaces, an isolated exact optimum can have zero sampling probability; approximation regions and additional convergence assumptions must replace that finite-state argument.

Variants, Pitfalls, and Optimizations

Plateaus and valleys are different obstacles. In $[0,3,3,3,7]$, strict ascent from state $1$ stops at score $3$ even though equal-valued moves through $2$ and $3$ could reach $4$ with score $7$. Allowing a bounded number of sideways moves can cross such a shoulder, but unlimited equal-score moves can cycle on a flat region. In $[5,1,9]$, leaving state $0$ requires an actual downhill move before climbing; sideways moves alone do not help.

The neighborhood determines the trap. On a bounded integer grid, consider $f(x,y)=-(x-y)^2+(x+y)/4$. At $(0,0)$, each unit axis move has negative change, while diagonal move $(1,1)$ gains $1/2$. Axis-only hill climbing is stuck on a ridge relative to its move set; adding an appropriate diagonal move changes the neighborhood and the conclusion. More neighbors can improve exploration while making each steepest-ascent scan more expensive.

Keep restart diversity and the incumbent. Seeding the generator identically inside each restart can repeat one starting sequence, invalidating the intended diversification. Repeated starting states can still occur normally under sampling with replacement; the code does not force distinct starts. Keep the best score across all observations instead of returning the last run's endpoint. In the worked trace, the last run ends at score $8$ after an earlier run already found $10$.

Separate observation from commitment. A partial neighborhood scan cannot establish the steepest move or a local maximum. The implementation records any useful observed candidate in the incumbent but leaves the current path unchanged when a query is blocked. A first-improvement algorithm could commit earlier by design, but that is a different policy. Do not confuse the shared evaluation budget with the move cap that resets per run, and do not label FINISHED or MOVE_LIMIT as global convergence.

Use the right variant for the objective. Stochastic hill climbing randomly chooses among uphill moves; first-improvement stops its scan early; random restart changes initialization. Simulated annealing can accept downhill moves, and tabu search or perturb-and-reclimb methods use other mechanisms to leave a basin. These are distinct choices, not interchangeable names. For real-valued states, choose meaningful step sizes, bounds, progress tolerances, and stopping criteria: strict numerical improvement alone need not terminate an infinite sequence approaching a limit.

Preserve feasible states and trustworthy scores. Generate legal neighbors and feasible restart states, or define and validate a repair procedure. A soft penalty does not automatically make the highest-scoring observed state feasible. For noisy simulations, a single favorable observation can misrank candidates or the incumbent; repeated estimates and an explicit uncertainty policy are needed. For mutable states, a saved reference is not a preserved best configuration if later moves modify the same object. The sample avoids those issues with exact integer scores, immutable state IDs, and copied input.

Practice Problems and Real-World Use

First verify a single trajectory by hand, then derive an independent transition map for every state: choose the highest score among the current state and its neighbors, preferring the current state on an equal score. Sorting states by descending score lets a separate oracle compute the final local endpoint of every strict-ascent basin. This checks hill-climbing behavior without running another online neighbor-comparison loop.

The programs were validated on 9,794 inputs per language, comprising $9{,}780$ valid cases and $14$ invalid inputs. The corpus includes $6{,}015$ exhaustive cases covering all score arrays over $\{-1,0,1\}$ of lengths $1$ through $6$ from every possible first start, plus randomized landscapes, long monotone chains, plateaus, negative scores, limits, and boundary sizes. Fifty-one seeded cases deliberately force a rejected raw restart draw. An independent transition/basin oracle and jump-ahead modular RNG oracle checked complete results, every query and path, tie rules, counters, and final generator state. There were $93{,}466$ strict-move checks, $121{,}655$ scan-history checks, and $27{,}740$ local-endpoint checks; $26$ cases retained a best observed state that was never committed to a path. Python, C++, and Java matched exactly on the full corpus and repeated runs, preserved input collections, and the C++ corpus passed address/undefined-behavior instrumentation.

For primary background, see the AIMA authors' chapter on informed and local search and Carnegie Mellon's local-search course notes. The exact score table, tie policy, portable restart mapping, incumbent semantics, budget contract, and full trace here are specified directly in this lesson.