4.6 Judging a search strategy

What this is and why it exists

Four questions decide whether a search algorithm is any use, and every method in this unit is scored on the same four, which is what makes them comparable at all. This topic also teaches you to read a complexity bound as a statement about real problem sizes rather than as decoration — because the difference between an algorithm that finishes and one that does not is usually visible in the bound, if you convert it into a number of states.

The vocabulary

• Completeness — will it find a solution whenever one exists?
• Optimality — will the solution it finds be the cheapest?
• Time complexity — how many states it generates before finishing.
• Space complexity — how many states it must hold in memory at once.
• Branching factor — how many actions are available from a state, written b.
• Solution depth — how deep the shallowest solution lies, written d.
• Maximum depth — how deep the state space goes, written m, possibly unbounded.
• Fringe — the generated states not yet expanded.

The mental model

The four criteria, stated so they can be applied.

Completeness asks whether the algorithm is guaranteed to find a solution when one exists. It fails in two ways: an algorithm can descend an infinite path forever, or it can revisit states in a cycle and never reach the rest of the space.

Optimality asks whether the solution it returns is the cheapest. Finding a solution and finding the best solution are genuinely different guarantees, and several methods offer only the first. Whether you need the second is a question about your problem, not about the algorithm — for a route, usually yes; for a configuration that merely has to be valid, frequently no, and paying for optimality you do not need is a real cost.

Time complexity counts states generated, not seconds, because seconds depend on hardware and states do not.

Space complexity counts states held at once. This is the criterion that decides practical feasibility far more often than time does, which is the least intuitive thing in the topic and the most useful. An algorithm generating a million states per second exhausts a typical machine's memory in minutes if it must keep them all — the run does not become slow, it stops.

Three letters make the comparison tables readable. b, the branching factor, is how many actions are available from a typical state. d, the solution depth, is how many steps deep the shallowest solution lies. m, the maximum depth, is how deep the space goes, and it may be unbounded where cycles exist. Note that d and m measure different things and the gap between them is where several algorithms live or die: a shallow solution in a very deep space is exactly the case that separates depth-first behaviour from breadth-first behaviour.

Now read a bound. Written O(b^d) and read aloud as "order b to the power d", it says the work grows exponentially with the depth of the solution: each extra level multiplies the number of states by roughly the branching factor. Convert it into a count and it stops being abstract. With ten actions available at each step, a solution three steps away means about a thousand states — instant. Six steps away, a million — a second or two. Nine steps, a billion — you will wait, and memory has probably already failed. Twelve steps, a trillion — not on this machine, this year, or any machine.

The lesson is that an exponential bound is not a warning about large problems; it is a statement that only small ones are reachable. Doubling the hardware buys you a fraction of one extra level of depth. This is why every later idea in this unit — heuristics, admissibility, local search — exists: they are attempts to reduce the effective branching factor or to abandon systematic search altogether, because no amount of engineering defeats an exponent.

Two habits follow. Estimate b and d for your actual problem before choosing a method, because those two numbers decide more than the algorithm does. And notice which quantity sits in the exponent: a bound in terms of the solution depth behaves very differently from one in terms of the maximum depth, and an algorithm that is exponential in a small number can be entirely practical.

Then the point that gives this topic its edge: completeness alone is not a recommendation. An algorithm can be guaranteed to find a solution and be useless, because the guarantee says nothing about when. Breadth-first search is complete and will find any solution eventually; if that solution is fifteen steps down a space with a branching factor of ten, "eventually" is longer than you have, and the memory required exceeds anything you can buy. The algorithm has not failed — it has kept its promise, and the promise was worth less than it sounded.

So read the four criteria together, never one at a time. Complete and optimal but exponential in space is a theoretical result. Incomplete but cheap may be exactly right if you can restart it. Complete, optimal, and exponential in time but linear in space — which is the profile of one particular strategy in the next topic — is frequently the best available combination, and understanding why is the reason the next topic exists.

One last practical note. These bounds describe the worst case. Real problems often behave better, because the structure of the space prunes possibilities that the worst case assumes. That is a reason to measure rather than only to calculate — but it is not a reason to ignore an exponent, because the worst case in search arrives far more often than optimism expects.

What you should now be able to explain or do

Define the four criteria and say what completeness fails on. Distinguish finding a solution from finding the best one, and say when the second is worth paying for. Say why time is counted in states and why space usually decides feasibility. Use b, d and m correctly and explain why d and m differ. Read an exponential bound and convert it into a rough state count at a real problem size. Explain why more hardware barely helps. Argue that completeness alone is not a recommendation, and read the four criteria together.

Check yourself