Uninformed and Informed Search

A search problem describes choices before an algorithm starts making them. Its formulation controls both what a solution means and how many possibilities the algorithm must consider.

Define the problem

There are six parts:

• States describe the possible situations.
• The initial state is where the search begins.
• Actions are the choices available in a state.
• The transition model, $\text{RESULT}(s,a)$, gives the state after action $a$.
• The goal test recognizes an acceptable state.
• The action cost function, $c(s,a,s^{\mathrm{\prime }})$, assigns a cost to each step.

All action costs here are positive. A solution to a path-finding problem is an action sequence leading to a goal. Add its action costs to obtain its path cost. A cost-optimal solution minimizes that sum. Merely naming the destination does not tell an agent how to reach it.

Formulate the 8-puzzle

A board contains eight numbered tiles and a blank. Record all nine positions as the state. The initial state is the supplied layout; the goal is "1 2 3 / 4 5 6 / 7 8 blank". An action moves the blank left, right, up or down when that move stays on the board. The transition swaps the blank with the neighboring tile, and every move costs 1. A corner permits two actions; the center permits four.

A solution is a sequence such as "Left, Up, Right", if those moves are legal and reach the goal. Because each move has the same cost, minimizing cost means minimizing the number of moves.

Choose the state space

Think of states as vertices in a directed graph and actions as cost-labeled edges. A two-way road gives two directed edges. For route finding, a state can be the current place and a step cost can be road distance in kilometers.

Abstraction leaves out irrelevant detail. The music playing in a car need not be part of a route state. An abstract solution must still be possible to carry out. Removing a detail that changes which actions are legal would change the problem, not just simplify its description.

The formulation can save more work than a faster queue. Placing eight queens on any empty squares gives $64\times 63\times \cdots \times 57\approx 1.8\times {10}^{14}$ possible ordered placement sequences. Placing each next queen in the leftmost empty column on an unattacked square leaves 2,057 reachable states. These are different constructions of the same goal condition.

Generate possibilities as needed

The 8-puzzle has $9!\mathrm{/}2=\mathrm{181,440}$ reachable states from a fixed start. The 15-puzzle has $16!\mathrm{/}2\approx 1.05\times {10}^{13}$. A complete 8-queens representation with one queen per column has $8^8=\mathrm{16,777,216}$ states.

Such spaces are usually supplied implicitly: the search receives a start state and procedures for actions and transitions. It generates the relevant portion as it runs. For a path problem, retain the action sequence. For an optimization problem such as queen placement, the final arrangement itself can be the answer.

The state space describes what is possible. The search tree records the paths the algorithm has tried. Several nodes can describe the same state because they arrived there by different paths.

Store a path in a node

A node stores a state, its parent node, the action from that parent and the path cost $g(n)$. Depth may also be stored. The root has no parent and path cost 0. Expanding a node applies every legal action to its state and generates its children.

On a two-way map, paths "S, A" and "S, B, C, A" end in the same state but give different nodes. Even a finite map can generate an infinite search tree: "S, A, S, A, …" keeps producing longer paths.

The frontier, also called the fringe, holds generated nodes awaiting expansion. The reached set records generated states and the best node found for each. It includes states still on the frontier as well as states already expanded. A closed or explored set usually refers only to expanded states.

Run the general best-first procedure

1. Put the root in the frontier and reached table.
2. If the frontier is empty, return failure.
3. Remove the node with the smallest evaluation value $f(n)$.
4. If its state is a goal, return that node.
5. Expand it. Add each new state; for a previously reached state, replace its stored node only when the new path is cheaper.
6. Repeat from step 2.

A cheaper path to an already expanded state may require reopening it. Equal-cost returns add no improvement. With a heap, an old entry can remain physically present; it must be recognized as stale and skipped when removed.

The frontier rule controls the strategy. A FIFO queue selects shallow nodes for BFS. A LIFO stack selects deep nodes for DFS. Priority queues ordered by $g$, $h$ and $g+h$ give uniform-cost, greedy best-first and A* search.

Follow the road-map nodes

Use these two-way roads, with distances in kilometers: S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 and D–G 2. Start at S and seek G. Break ties alphabetically.

Expanding S generates A with cost 2, B with cost 3 and D with cost 9. Each has parent S. The frontier contains A, B and D; the reached table also contains S. Later, C can be reached through A for cost 6 or through B for cost 4. Those are two nodes for one state, and the cheaper one should represent C.

To recover a solution, follow the returned goal node's parent links backward and reverse the actions. Updating the cost without updating the parent would leave a path that disagrees with its reported cost.

Decide what to remember

Graph search remembers reached states to avoid repeated work. Tree-like search has no global reached table; it may only reject cycles on the current path. It saves memory but can generate the same state through many paths.

The general procedure tests goals on removal. BFS can test at generation because generation follows depth order. Cost-based search must wait for removal: the first generated goal can have a more expensive path than a goal found later.

An algorithm can be reliable yet too expensive to run. Judge its guarantees separately from its resource use, then check whether those guarantees match the problem you actually need to solve.

Ask four different questions

Completeness means finding a solution whenever one exists. In a finite reachable space, exhausting all possibilities can also prove failure. An infinite space with no solution may be searched forever, even by a complete algorithm.

Cost optimality means returning a solution with the lowest path cost. It says nothing about how fast the algorithm runs. A method can find a solution reliably while returning an expensive route.

Time complexity counts generated or expanded nodes. State which count is being used when comparing measurements. Space complexity measures the maximum number of nodes held at once, including the frontier and stored search information.

Identify the parameters

For an implicit search space, use:

For an explicit graph already in memory, vertex and edge counts are usually more useful. A traversal bound in $\mathrm{\mid }V\mathrm{\mid }$ and $\mathrm{\mid }E\mathrm{\mid }$ answers a different question from a bound for generating an unseen tree.

See why depth is expensive

A full tree through depth $d$ contains

nodes for $b\mathrm{\ne }1$. With branching factor 10 and depth 5, that is 111,111 nodes including the root. Increasing the depth by one adds a layer with ten times as many nodes as the previous layer.

At one million nodes per second and 1 kilobyte per node, the scale changes quickly:

These are decimal storage units: 1 GB is ${10}^9$ bytes. Memory can rule out a search long before its running time seems unreasonable.

Read guarantees with their conditions

BFS eventually reaches every finite depth when branching is finite. DFS can spend forever on one infinite branch and never try a nearby goal. That difference explains their completeness results.

BFS finds a path with the fewest actions. If a two-step route costs 11 km and a three-step route costs 9 km, the shallower route is not cost-optimal. Equal step costs make depth and cost agree; different costs can separate them.

A worst-case big-O bound does not predict every run. Two methods with the same bound may differ in constants, duplicate handling and the number of useful branches. A heuristic can greatly improve a typical run without removing the exponential worst case.

Breadth-first search explores in layers. Its next expansion is the shallowest node still waiting, so every one-action path is considered before any two-action path is expanded.

Keep the queue in order

The frontier is first in, first out: remove from the front and append children at the back. Record states when they are generated. If a child state has already been reached, skip it; otherwise two different parents could put the same state into the queue.

Test the initial state before searching. For later nodes, BFS can use an early goal test on generation. The first generated goal has minimum depth because the algorithm generates children layer by layer. The order within a layer can choose between equally shallow solutions, but cannot make a deeper solution appear first.

Trace the example map

The two-way roads are S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 and D–G 2 km. Start at S, seek G and generate neighbors alphabetically. In the table, the next node to remove is on the left.

When B is expanded, C and D are already reached. They do not move to new positions in the queue. When D generates G, its parent chain is G–D–S. Reverse it to recover S–D–G, with two roads and total distance $9+2=11$ km.

C has already been generated, but it has not been expanded. Its route to G would have three roads. BFS can stop without exploring it because three roads cannot improve the number of actions in a two-road solution.

Know what the result minimizes

BFS is complete for finite branching, even if the space is infinite: each finite layer is processed before the next. It is cost-optimal when all actions cost the same. In a sliding puzzle with cost 1 per move, a shallowest solution is also a cheapest solution.

On this road map, S–B–C–G costs $3+1+5=9$ km. BFS returns the 11-km route because distance is not its ordering rule. "Shortest path" therefore needs a unit: fewest roads and fewest kilometers are different objectives.

Account for memory

With early goal testing, BFS takes $O(b^d)$ time and space. It may generate nearly every node through the goal depth and retain the frontier plus reached information. If goals are tested only on removal, expanding other nodes at depth $d$ can generate depth $d+1$, giving the usual $O(b^{d+1})$ bound for that version.

With branching factor 10 and 1 kilobyte per node, storing a tree through depth 10 takes about 11 TB. BFS is useful for shallow, equal-cost problems when enough memory is available, such as minimum-hop network paths or fewest-move puzzles. A FIFO queue does not use the numerical edge costs, even when they are written on the graph.

Uniform-cost search orders paths by the cost already paid. It can pass over a nearby but expensive destination while it investigates longer routes made of cheap steps.

Remove the cheapest path

Set $f(n)=g(n)$ and use a priority queue. When an expansion finds a cheaper path to a reached state, update both its cost and its parent. An equal-cost path does not improve the record. UCS is the search form of Dijkstra's algorithm, stopping when it removes a goal.

The late goal test is essential. Generating a goal proves that a route exists. Removing that goal as the cheapest frontier node proves that no unfinished cheaper route can beat it, given positive action costs.

Trace the example map

Use the two-way roads S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 and D–G 2 km. Break cost ties alphabetically. The frontier entries below show state and path cost.

The replacement of C is decisive: $3+1=4$ beats $2+4=6$. G's parent is C, C's parent is B and B's parent is S. The returned route S–B–C–G costs 9 km. D is removed before G only because the tie rule is alphabetical.

If a direct S–G road of 12 km were added, S would generate a goal immediately. An early test would return 12 km before discovering the 9-km route. The priority queue cannot protect optimality if the stopping rule bypasses it.

Explain the guarantee

With finite branching and every action cost at least some $ϵ>0$, only finitely many path steps can fit below any fixed cost bound. UCS therefore eventually removes a goal whenever one exists. Positive costs ensure that extending a path cannot make it cheaper, which supports the optimality proof.

Zero costs need care. Tree-like search can keep circling a zero-cost cycle. Graph search rejects equal-cost returns to the same state, but an infinite chain of distinct states with bounded accumulated cost can still delay a goal forever. Negative step costs break the ordinary UCS optimality argument.

Understand the expense

The standard worst-case time and space bound is $O(b^{1+\lfloor C^{\ast }\mathrm{/}ϵ\rfloor })$. On this map, $C^{\ast }=9$ and $ϵ=1$, giving $O(b^{10})$. This is a loose bound, not the actual number expanded on the six-state map.

Many cheap dead-end paths can force UCS to do substantial work before taking one costly useful action. When all step costs are equal, its late goal test gives the familiar $O(b^{d+1})$ bound. A* with $h=0$ makes exactly the same priority comparisons as UCS.

Depth-first search follows one branch before trying its alternatives. That choice can greatly reduce memory, but it lets an unlucky branch delay every other possibility.

Follow a deep branch

DFS uses a last in, first out stack. In a tree-like version, reject states already on the current path to avoid immediately cycling. Store the current path and the unexpanded siblings along it. To try successors alphabetically with a stack, push them in reverse alphabetical order.

On the two-way map S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 and D–G 2 km, start at S and seek G. Trying neighbors alphabetically and testing goals on removal gives S, A, C, B, D, G. At C, B is the first neighbor not already on the path. The returned route S–A–C–B–D–G costs $2+4+1+6+2=15$ km.

DFS is not cost-optimal. It is complete in a finite space with path cycle checks, but can follow an infinite branch forever. Its worst-case time is $O(b^m)$ and its stored paths and siblings need $O(bm)$ space. Backtracking that generates one child at a time reduces storage to $O(m)$. With branching 10 and maximum depth 12, path-and-sibling storage is about 120 nodes, compared with roughly a trillion for BFS through depth 12. A global reached table would use additional memory.

Bound the depth

Depth-limited search stops expanding at depth $\mathrm{\ell }$. A goal there can still be recognized. It distinguishes three outcomes:

• A solution was found.
• Cutoff: the depth bound prevented a full search.
• Failure: the relevant possibilities were exhausted without a goal or cutoff.

A cutoff does not prove that no solution exists. If the shallowest goal is at depth 7, a limit of 5 cannot reach it. Worst-case time and space are $O(b^{\mathrm{\ell }})$ and $O(b\mathrm{\ell })$.

Increase the limit gradually

Iterative deepening search, or IDS, runs depth-limited searches with limits 0, 1, 2 and so on. It finds a shallowest solution without storing a breadth-first frontier. With finite branching it is complete; with equal action costs it is cost-optimal. Time is $O(b^d)$ and space is $O(bd)$.

Most nodes of a broad tree are in the last layer, so repeating the upper layers is often inexpensive. For $b=10$ and $d=5$, count generated nodes below the root:

BFS generates 111,110 such nodes through depth 5. IDS does about 11% more generation while keeping only depth-first storage. The repeated root visits are excluded from both of these particular counts.

For branching factors greater than 1, the broad-tree overhead approaches the factor $b\mathrm{/}(b-1)$. This advantage is weaker for a narrow chain, where repeated prefixes dominate. IDS is a useful uninformed choice when solution depth is unknown and a full frontier will not fit. In spaces with many routes to the same state, its lack of a global reached set can cause substantial regeneration.

A useful strategy matches the result you need and the resources you have. Uninformed search uses the problem definition without an estimate of the remaining distance. It can still be systematic and carefully ordered.

Compare like with like

Assume finite branching and the positive-cost conditions for UCS. The BFS row uses early goal testing; the DFS row uses path cycle checks and no global reached table.

BFS and IDS also minimize cost when cost is a nondecreasing function of depth alone. The word "alone" matters: all paths of a given depth must have the same cost for this broader condition. Positive edges by themselves do not make BFS cost-optimal.

Search from both ends

Bidirectional search works forward from the start and backward from the goal. If the searches meet near the middle, each reaches roughly depth $d\mathrm{/}2$. The work is then roughly $2b^{d\mathrm{/}2}$ instead of $b^d$. With branching factor 10 and solution depth 6, the leading-layer comparison is about 2,000 nodes versus 1,000,000.

It needs an explicit goal state and a way to generate predecessors. Reversible two-way roads make backward expansion easy. A goal property such as "all queens are safe" may describe too many goal states to provide a convenient reverse starting point.

With breadth-first or cost-based searches, suitable meeting and termination rules can preserve completeness and optimality. On a weighted map, stop only once no cheaper connection remains possible. The first overlap between the two searches need not be the cheapest connection.

Choose by the problem

For the fewest moves in a small sliding puzzle, equal move costs make BFS appropriate if memory is ample. For minimum-distance travel with unequal road lengths and no heuristic, choose UCS. For an enormous equal-cost puzzle of unknown solution depth, IDS avoids an enormous frontier. In a finite space with many deep goals where any solution is acceptable, DFS can be practical. A known start and goal with reversible actions makes bidirectional search worth considering.

Memory use must include what the chosen version stores. DFS with a global reached table no longer has the same storage profile as tree-like DFS. A late-goal BFS trace should not be compared with an early-goal complexity bound as if the versions were identical.

Even the best uninformed choice can face exponential growth. When useful domain knowledge is available, a heuristic can reduce irrelevant exploration. When only a final configuration matters, local search can avoid keeping a search tree.

A heuristic assigns a state an estimate of the cheapest remaining cost to a goal. Write it as $h(n)$ for the state in node $n$. It depends on the state, not the path used to reach it, and is zero at a goal.

Estimate what remains

Straight-line distance estimates remaining road distance. On a grid with horizontal and vertical unit moves, Manhattan distance adds coordinate differences:

From cell (1,1) to (4,5), this gives $3+4=7$ moves. Straight-line distance between the same coordinates is $\sqrt{3^2+4^2}=5$. The estimates answer different relaxed movement questions. A heuristic must match the units of the cost it estimates; kilometers do not directly estimate travel time without a suitable conversion model.

Informed search uses an estimate to guide expansion. The estimate need not tell the algorithm which action to take. It scores the states produced by the legal actions, and the frontier rule decides which pending path to investigate next.

Follow the smallest estimate

Greedy best-first search sets $f(n)=h(n)$. Its priority queue removes the state that looks closest to the goal, ignoring the cost already paid.

Use the two-way roads S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 and D–G 2 km. The heuristic estimates to G are S 8, A 7, B 5, C 4, D 2 and G 0 km.

1. Expand S. The frontier has A with estimate 7, B with 5 and D with 2.
2. Remove D because 2 is smallest. Expanding D generates G with estimate 0. The path cost to G is $9+2=11$ km.
3. Remove G and return S–D–G.

Only S and D were expanded. The 9-km route S–B–C–G was available, but B's estimate of 5 looked worse than D's 2. Greedy search never included the 9 km already spent reaching D in its comparison.

Separate guidance from guarantees

Even a heuristic that never overestimates does not make greedy search cost-optimal. The example estimates are admissible, yet the returned route is too expensive. Greedy search uses only the remaining estimate, so it can pay too much before reaching a promising state.

Graph search is complete on a finite state space when it handles duplicates properly. Tree-like greedy search can loop on appealing repeated states, and an infinite space can keep offering misleading low estimates. Worst-case time and space are $O(b^m)$, although a useful estimate can make an actual run short.

A place can be close to a destination in a straight line but require a long detour around a river. Small heuristic values do not certify good total routes. Computing the heuristic also takes time: reducing expansions helps only if evaluating those estimates does not consume the savings.

A* evaluates the whole proposed journey: the cost already paid plus an estimate of what remains. Its priority is

Use a priority queue, replace more expensive paths and test a goal when it is removed. At a goal, $h=0$, so its priority is its actual path cost.

Trace the cost-plus-estimate rule

The two-way roads are S–A 2, S–B 3, S–D 9, A–C 4, B–C 1, B–D 6, C–G 5 and D–G 2 km. Heuristic estimates to G are S 8, A 7, B 5, C 4, D 2 and G 0. Break ties alphabetically.

A is removed before G because of the tie rule. A* expands four non-goal nodes and never expands D. UCS on the same map expands D too. Setting every heuristic estimate to zero would remove this guidance and reproduce UCS.

Explain why an optimistic estimate works

An admissible heuristic never exceeds the true remaining cost $h^{\ast }(n)$. For A* with reopening, admissibility guarantees cost optimality; tree-like A* has the same guarantee under the positive-cost search conditions.

Suppose a worse goal of cost $C>C^{\ast }$ were about to be removed. Some node on an optimal path must still be pending. For its optimal-path prefix,

The queue must choose that node before the worse goal. This contradicts the proposed stopping point. Reopening matters because a cheaper prefix discovered later must be allowed to continue through a state already expanded.

A consistent heuristic makes $f$ nondecreasing along paths. It ensures that the first expansion of a state uses a cheapest path to it. A* can then permanently close expanded states. With admissibility alone, a permanent closed set can discard an essential improvement.

Understand pruning and its limits

With consistency, A* expands every relevant node whose $f<C^{\ast }$, may expand nodes tied at $C^{\ast }$ and expands none above that value before returning. D's priority 11 exceeds the solution cost 9, so it stays unexpanded. In the class of forward path-building algorithms using the same heuristic information, A* is optimally efficient apart from ties. This is a comparison of necessary expansions, not a claim that its code always runs fastest.

Overestimation can break the argument. Change B's estimate to 9 although its true remaining cost is 6. B now has priority 12. A*, following S, A, C and D, returns S–A–C–G at cost 11 while B still waits.

A* still has an exponential worst case and stores generated search information.

When the frontier no longer fits or an answer arrives too slowly, choose which resource or guarantee to trade. Speed-oriented variants change priorities or discard candidates. Memory-oriented variants regenerate paths they could not keep.

Put more weight on the estimate

Weighted A* uses $f=g+Wh$ with $W>1$. It usually favors progress toward a goal more strongly. With an admissible heuristic and the best-path updates and reopening of the general procedure, its returned cost is at most $W{C}^{\ast }$. That bound permits a worse solution; it does not require one.

On the example road map, use estimates S 8, A 7, B 5, C 4, D 2 and G 0, and weight 2. From S, the priorities are B 13, D 13 and A 16. Alphabetical ties select B. Its child C has $4+2(4)=12$; C then generates G with priority 9. The cost-9 route is returned after three non-goal expansions. The guarantee allows up to 18 km, although this run finds the optimum.

In the same formula, weight 0 gives UCS and weight 1 gives A*. As the weight grows large, the estimate increasingly dominates comparisons, approaching greedy behavior.

Beam search keeps only the best $k$ pending nodes and discards the rest. The retained frontier is bounded, but a discarded candidate can contain the only solution. It therefore gives neither completeness nor an optimality guarantee.

Deepen by an estimated-cost threshold

IDA* performs depth-first search with a cutoff on $f=g+h$. The first cutoff is the root's value. Prune any node above it, recording the smallest exceeded value. That value becomes the next cutoff; it is not necessarily the old cutoff plus 1. Use path cycle checks.

For the example map, the first cutoff is 8. A at 9 and D at 11 are pruned; B and C at 8 are explored, but G at 9 is pruned. The next cutoff is 9. In that iteration, the path through A produces C at 10 and is pruned. The path S–B–C–G stays within 9 and succeeds.

With admissibility, IDA* preserves cost optimality and needs only depth-first path storage. Its repeated passes can be expensive when costs produce many distinct thresholds. Small integer costs often make the number of thresholds more manageable.

Use bounded memory more selectively

Recursive best-first search (RBFS) stores the best alternative priority at each level. It follows the most promising branch until that alternative becomes better, then backs up. It uses linear memory but can regenerate forgotten branches.

SMA* uses the available memory, drops the worst frontier leaf when full and backs its value into its parent. This record allows later regeneration. With an admissible heuristic it is cost-optimal if an optimal solution path fits in memory. Otherwise it may return a worse solution, or fail if no solution path fits.

Choose A* for an optimal answer when storage suffices. Choose IDA* or a suitable memory-bounded variant when optimality matters but the frontier does not fit. Weighted A* offers a numerical quality bound; beam search offers aggressive pruning without that bound.

A heuristic can be optimistic overall yet change too sharply between neighboring states. Admissibility and consistency capture these different checks, and each supports a different version of A*.

Compare estimates with true costs

An admissible heuristic satisfies $0\le h(n)\le h^{\ast }(n)$ at every state. At a goal, the true remaining cost is zero, so its estimate must also be zero. Admissible does not mean accurate: zero everywhere is safe but provides no direction.

On the example road map, the estimates and exact cheapest remaining distances to G are:

Every estimate is at most its true cost. In a large problem, computing these exact costs may be as hard as the original search. A proof from the problem's structure is then more useful than an exhaustive table.

Check every action

Consistency, also called monotonicity, requires $h(n)\le c(n,a,n^{\mathrm{\prime }})+h(n^{\mathrm{\prime }})$ for every action, plus zero at goals. The current estimate cannot exceed one step's cost plus the successor estimate.

On the road map, A→C gives $7\le 4+4$, C→B gives $4\le 1+5$ and D→G gives $2\le 2+0$. Two-way roads require both directions. All 16 directed checks hold for these estimates.

Adding the inequalities down a path to a goal cancels the intermediate estimates. It gives $h(n)\le h^{\ast }(n)$ on an optimal path, so consistency implies admissibility. It also gives

Priorities cannot fall along a path. The first expansion of a state is therefore on a cheapest path, even if its first generation was more expensive.

See why admissibility alone needs reopening

Consider two-way roads S–A 1, A–C 1, S–B 1, B–C 2 and C–G 3. Let the estimates be S 0, A 4, B 1, C 1 and G 0. They do not exceed the true costs S 5, A 4, B 5, C 3 and G 0, so they are admissible. But A→C violates consistency: $4>1+1$.

A* expands S, then B with priority 2, then C reached for cost 3 with priority 4. It then expands A with priority 5 and discovers a cheaper path to C of cost 2. Permanently rejecting C because it is closed leaves a cost-6 goal. Reopening C propagates the improvement and produces the optimum, cost 5.

Match the movement model

Manhattan distance is admissible and consistent for horizontal and vertical unit moves. If diagonal moves also cost 1, traveling from (0,0) to (3,3) takes only three moves, while Manhattan distance says 6. For that movement model, $\max (\mathrm{\mid }\mathrm{\Delta }x\mathrm{\mid },\mathrm{\mid }\mathrm{\Delta }y\mathrm{\mid })$ gives the obstacle-free distance. A heuristic's guarantee belongs to a particular action model.

To design a safe estimate, solve an easier version of the problem. A relaxed problem removes action restrictions, so every original solution remains available. Its cheapest cost cannot exceed the original cheapest cost.

Remove restrictions deliberately

An exact relaxed cost is an admissible heuristic. It is also consistent when original actions remain available with their costs: taking an original step and then an optimal relaxed route is one possible relaxed route, so the relaxed optimum cannot cost more.

In the 8-puzzle, a tile can move to an adjacent square only when that square is blank. Remove the blank requirement and tiles may pass through occupied squares. Each numbered tile then needs at least its horizontal plus vertical distance to its target. Summing gives Manhattan distance, $h_2$.

Remove adjacency as well and each misplaced tile can jump straight to its target in one move. The resulting cost is the misplaced-tile count, $h_1$. Both are easy to calculate without searching the original puzzle.

Work out both estimates

For goal "1 2 3 / 4 5 6 / 7 8 blank", consider "5 1 3 / 4 blank 2 / 7 8 6". Number rows and columns from 1.

The other numbered tiles are already correct. Four are misplaced, so $h_1=4$. Their distances total $2+1+2+1=6$, so $h_2=6$. The optimal solution takes 12 moves; the relaxations ignore interactions that create extra work.

Do not count the blank. One move from the goal, a numbered tile and the blank are both displaced. Counting both would give 2 when the true cost is 1. The blank enables moves; it is not an additional tile to charge for.

Store solved subproblems

A pattern database records exact costs for a selected subproblem, such as placing tiles 1 through 4 correctly while treating other tiles as interchangeable. Build the table once by backward search from the goal. During a new search, use a lookup instead of solving the subproblem again.

The subproblem needs no more work than the full problem, giving a lower bound. However, adding two ordinary pattern costs can charge the same real move twice. Addition is safe for disjoint patterns when each database counts only moves of its own tiles. Disjoint tile names alone do not establish that cost accounting rule.

Combine safe estimates

The maximum of admissible estimates is admissible:

Every candidate stays below the true remaining cost, so their maximum does too. It is at least as informative as each individual estimate. A plain sum lacks this protection.

A heuristic learned from solved examples may predict remaining cost well on average. Average accuracy does not establish a lower bound on every state. It retains A*'s admissible-heuristic guarantee only when its estimates are shown never to overestimate.

A closer estimate can reduce exploration, but a costly estimate can still make search slower. Compare both the information supplied and the total computation required.

Establish dominance over every state

An admissible heuristic $h_2$ dominates admissible $h_1$ if $h_2(n)\ge h_1(n)$ everywhere. One favorable board is not enough to prove this relationship.

Manhattan distance dominates misplaced-tile count in the 8-puzzle. Each misplaced tile must travel at least one square, so its Manhattan contribution is at least the 1 counted by the weaker heuristic. A correctly placed tile contributes zero to both.

With consistent estimates, A* must expand paths with $g+h<C^{\ast }$. Raising a safe estimate removes some paths from this mandatory region. A dominating consistent heuristic expands no more nodes apart from differences at ties. An inadmissible estimate can be larger still, but it loses the optimality guarantee and does not qualify for this dominance comparison.

Summarize search effort

The effective branching factor, $b^{\ast }$, describes the breadth of an equivalent uniform tree. Count $N$ generated nodes below the root and let the solution depth be $d$. Solve

The extra 1 accounts for the root. Consistent counting matters: if a measurement already includes the root, do not add it twice.

For 52 generated nodes below the root and solution depth 5, the total is 53 and $b^{\ast }\approx 1.92$. For 1,000 generated nodes and depth 8, $b^{\ast }\approx 2.20$. Find these values numerically by increasing or decreasing a trial value until its geometric sum matches the node total.

A value near 1 indicates a narrow search. Compare results across representative instances, with the same counting rule and comparable solution depths. Effective branching factor can help estimate scaling, but an unusually easy instance is not a reliable forecast for an entire problem family.

Time the whole computation

Suppose a node takes 10 microseconds, including 1 microsecond to evaluate the old heuristic. A replacement halves the node count but takes 100 microseconds per evaluation. Non-heuristic work still costs 9 microseconds, so the new per-node total is 109. The overall time ratio is

The search is about 5.5 times slower despite visiting fewer nodes. If the new evaluation takes only 2 microseconds, the node total becomes 11 and the time ratio is $0.5\times 11\mathrm{/}10=0.55$. That is about 1.8 times faster.

A pattern database also has a construction cost. Many searches with the same goal can share that investment; one small search may not repay it. Measure preprocessing, lookup time, generated nodes and memory separately so that fewer expansions are not mistaken for an automatic speed improvement.

Local search repeatedly changes a complete candidate answer. It suits tasks where the final configuration matters and the sequence used to find it can be discarded.

Represent a full candidate

For 8-queens, place one queen in each column. Represent the state by the eight row numbers, reading columns from left to right. Every state has all eight queens, including states with conflicts. A neighbor moves one queen to another row in its own column.

There are $8^8=\mathrm{16,777,216}$ states and $8\times 7=56$ neighbors per state. A fixed number of current states replaces the large frontier and parent records of path search. Storage still depends on the size of a state; retaining one eight-entry tuple is smaller than retaining one huge timetable.

Timetabling, chip layout and choosing a complete tour through cities have the same broad pattern: each state is a full proposal. A tour is itself a candidate arrangement, even though its content describes travel. Local search need not preserve the sequence of edits used to improve that tour.

Define what better means

An objective function gives each state a score to maximize. Equivalently, define a cost to minimize. For n-queens, let $h$ count pairs of queens attacking each other. Count each pair once, including attacks along rows or diagonals even when another queen lies between them. A solution has $h=0$.

For four columns, the tuple (1,2,3,4) puts all queens on one diagonal. Its $\left(\genfrac{}{}{0px}{}{4}{2}\right)=6$ pairs all attack. The tuple (2,1,3,4) has two attacking pairs, while (2,4,1,3) has none. Here lower values are better; the letter $h$ is an objective cost, not a remaining path-cost estimate used by A*.

Read the landscape

Imagine state quality as height. For maximization:

• A global maximum has the best value anywhere in the space.
• A local maximum is better than its neighbors but can be worse than a distant state.
• A plateau is a connected flat region. It may be a flat local maximum with no uphill exit, or a shoulder from which sideways moves can reach an uphill exit.
• A ridge can rise in a direction that the available single moves cannot follow. Every immediate choice may look worse.

For cost minimization, reverse height: search seeks minima and valleys. A local minimum is not proof that no lower-cost state exists elsewhere. The neighborhood determines which states can be compared in one step, so changing the allowed edit can change where search gets stuck.

Check that the path can be ignored

A route-finding agent must return legal actions from its actual start. A good destination alone is insufficient. Local search generally returns only the candidate state, without a parent chain back through all earlier edits.

A complete local-search method would find a goal whenever one exists; an optimal one would find the global best. Basic local methods give neither general guarantee. Their appeal is that they can reach good candidates quickly when storing a systematic search tree is impractical.

Hill climbing makes the best immediate improvement it can find. For a score to maximize, steepest ascent chooses the highest-scoring neighbor. For a cost to minimize, it chooses the lowest-cost neighbor. It stops when no strict improvement exists.

Follow a four-queen run

Let a state list the queen's row in each column and let $h$ count attacking pairs. Begin with (1,2,3,4), whose cost is 6.

1. Evaluate the one-queen moves. A best neighbor is (2,2,3,4), with cost 4.
2. From there, a best neighbor is (2,1,3,4), with cost 2.
3. No one-queen neighbor has cost below 2. Strict hill climbing stops.

The cost-zero arrangement (2,4,1,3) exists, but it cannot be reached by an immediately improving move from the stopped state. This is a consequence of the local rule, not evidence that the program miscounted conflicts.

Allow useful sideways movement

A sideways move keeps the same score. It can cross a shoulder to an improving exit, but it can also wander on a flat local optimum. Limit consecutive sideways moves to avoid endless cycling.

In Russell and Norvig's reported 8-queens experiment, steepest ascent from random starts succeeds about 14% of the time, taking about 4 steps on success and 3 when stuck. Allowing up to 100 consecutive sideways moves raises reported success to about 94%, with about 21 steps per success and 64 per failure. These are results for that experiment, not universal success rates for hill climbing.

Change how a neighbor is chosen

Stochastic hill climbing randomly selects an improving neighbor, possibly favoring larger improvements. First-choice hill climbing samples neighbors one at a time and takes the first improvement. It avoids evaluating an enormous neighborhood before every move. Both still refuse worse moves.

Random-restart hill climbing begins a fresh run from a newly sampled state after a failed run. With independent runs of success probability $p$, the expected number of runs through the first success is $1\mathrm{/}p$. For $p=0.14$, that is about 7 runs. Using the reported step counts, expected total steps are

The failed runs contribute work too. With positive success probability and independent restarts, the probability of eventually succeeding approaches 1 as the number of runs grows.

Let several candidates share discoveries

Local beam search keeps $k$ states, generates their neighbors together and retains the best $k$ from that pooled set. A promising parent may contribute several survivors while another contributes none. This sharing distinguishes it from independent restarts.

Pooling can also make all candidates cluster in one region. Stochastic beam search samples survivors with probability increasing with quality to preserve more variety. The choice between sideways moves, restarts and population diversity depends on why progress is failing: a nearby equal-value bridge, a bad starting region or too many candidates exploring the same area.

Some landscapes require a temporary loss before a better state becomes reachable. Simulated annealing allows such moves with a controlled probability. Genetic algorithms instead explore by selecting and combining complete candidates.

Accept a worse move sometimes

Simulated annealing samples one random neighbor. Accept an improving move. For a maximized objective, write its change as $\mathrm{\Delta }E$. If $\mathrm{\Delta }E<0$, accept the worse move with probability

For cost minimization, let $\mathrm{\Delta }$ be the increase in cost. A worse move then has $\mathrm{\Delta }>0$ and acceptance probability $e^{-\mathrm{\Delta }\mathrm{/}T}$. Equal-value moves have probability 1 under either formula. Temperature and objective changes must use a compatible numerical scale.

A score drop of 2 is accepted with probability about 0.819 at temperature 10, 0.135 at temperature 1 and 0.018 at temperature 0.5. At temperature 10, a larger drop of 5 has probability about 0.607. Thus temperature controls tolerance, while the size of the loss still matters at the same temperature.

Lower the temperature

A cooling schedule sets temperature over time. Geometric cooling uses $T_{k+1}=\alpha T_k$ with a factor close to 1, such as 0.95. At high temperature, many worse moves are accepted and exploration resembles a random walk. Near zero, worse moves become rare and behavior resembles hill climbing.

Cooling too fast can trap the search before it escapes a poor region. Cooling very slowly increases computation. The asymptotic global-optimum result needs sufficiently slow cooling and the usual ability to reach states through the neighborhood; an ordinary finite geometric run is not a certainty of global success. Used for chip layout and scheduling since the 1980s, the method takes its name from heating and slowly cooling metal so that it settles into a lower-energy structure.

Build a new population

A genetic algorithm represents candidates as strings. Each generation scores their fitness, selects parents with preference for higher fitness, creates children by crossover and applies occasional mutations.

For 8-queens, eight row digits describe one queen per column. Fitness can count non-attacking pairs, with 28 as the maximum. Cut parent strings "64751517" and "64278273" after the fourth digit. Combining opposite halves gives "64758273" and "64271517".

The parents have fitness 23 and 24; the children have fitness 27 and 21. One child improves on both parents while the other is worse. Crossover offers new combinations, not a guarantee of improvement. It is useful when good blocks tend to retain value when combined. Mutation occasionally changes a position and helps introduce variety beyond those combinations.

Selection, crossover and mutation play different roles: selection favors useful candidates, crossover recombines them and mutation changes individual positions. Like stochastic beam search, the method maintains a population, but new candidates can draw material from two parents. Neither a high-fitness parent nor a low final temperature alone proves that the global optimum has been found.