correct (and have: 2
k − f(k) > 2
k 3
4
for large k).
In summary, cost-based search on the single-decision tree
"only explores left". Hence the trap: There is no reason
to suppose that one direction is much worse than another in very large, weighted, graphs just because the first step is
quite expensive.
3.2 Branching Trap
In the counter problem the trap is not even *combinatorial*;
the search problem consists of a single decision at the root,
and the trap is just an exponentially deep path. Then it
is abundantly clear that appending Towers of Hanoi to a
planning benchmark, setting its actions at ε-cost, will kill
cost-based search - even given the perfect heuristic for the
puzzle! Besides Hanoi, though, exponentially deep paths
are not typical of planning benchmarks. So in this section
we demonstrate that exponentially large subtrees on ε-cost
edges are also traps.
Consider x > 1 high cost actions and y > 1 low
cost actions in a uniform branching tree model of search
space. (A typical model for analysis, appropriate up to
the point where duplicate state checking becomes significant. See (Pearl 1984) for similar analysis on more complex models of search.) Suppose the solution of interest
costs C, in normalized units, so the solution lies at depth
C or greater. Then cost-based search faces a grave situation:
O((x + y
1
ε )
C ) possibilities will be explored before considering all potential solutions of cost C.
A size-based search only ever considers at most O((x +
y)
d) = O(b
d) possibilities before consideration of all potential solutions of size d; of course the more interesting question is how long it takes to find solutions of fixed cost rather
than fixed depth—note C
ε ≥ d ≥ C. Assuming the high cost
actions are relevant, that is, some number of them are needed
by solutions, then we have that solutions are not actually hidden as deep as C
ε
. Suppose, for example, that solutions tend
to be a mix of high and low cost actions in equal proportion.
Then the depth of those solutions with cost C is d = 2 C
1+ε
(
d
2
· 1 + d
2
· ε = C). At such depths the size-based approach
is the clear winner: $O((x+y)^{1+\varepsilon})\ll O((x+y^{\frac{\varepsilon}{\varepsilon}})^{\circ})$ (normally). Consider, say, $y=\frac{b}{2}$, then:  $$b^{\frac{2C}{1+\varepsilon}}/\left(x+y^{\frac{1}{\varepsilon}}\right)^{C}<b^{\frac{2C}{1+\varepsilon}}/y^{\frac{C}{\varepsilon}},$$ $$<2^{\frac{C}{\varepsilon}}/b^{\frac{C}{\varepsilon}}\frac{1-\varepsilon}{1+\varepsilon},$$ $$<\frac{2}{b^{\frac{1-\varepsilon}{1+\varepsilon}}}\,$$  and, provided $\varepsilon<\frac{1-\log_{b}2}{1+\log_{b}2}$ (for $b=4$, $\varepsilon<\frac{1}{3}$), the last is 
2C
1 always less than 1 and, for that matter, goes, quickly, to 0 as C increases and/or b increases and/or ε decreases.

Generalizing, the size-based approach is faster at finding solutions of any given cost, as long as (1) high-cost actions constitute at least some constant fraction of the solutions considered, (2) the ratio between high-cost and low-cost is sufficiently large,(3) the effective search graph (post additional inference) is reasonably well modeled by an infinite uniform branching tree (i.e., huge), and (4) the search is systematic.

## 4 Search Effort As Flooding Topological Surfaces Of Evaluation Functions

We view evaluation functions (f) as topological surfaces over search nodes, so that generated nodes are visited in, roughly, order of f-altitude. With non-monotone evaluation functions, the set of nodes visited before a given node is all those contained within some basin of the appropriate depth
- picture water flowing from the initial state: if there are dams then such a flood could temporarily visit high altitude nodes before low altitude nodes. (With very inconsistent heuristics - large heuristic weights - the metaphor loses explanatory power, as there is nowhere to go but downhill. See (Dechter and Pearl 1985) for comprehensive details.)
If we take a single point inside such a basin (but not one defining the brim) and alter its altitude over the entire range of that basin's depth, we will not have changed the set of states inundated prior to the brim. If there were no solutions prior to the brim, then we will not have altered any externally visible behavior of the search: Whenever best-first search finally finds a solution it will no longer have mattered how all the prior nodes were ordered. To illustrate, IDA∗deserves its name, despite exploring the space in an entirely different order from A∗in any given iteration.

In particular, controlling the behavior of search by altering the evaluation function is a very different proposition in the two contexts of local search and best-first search. For the latter, preventing exploration of some choice requires raising its altitude (or that of a cut-set) to past that of a solution of interest, actually, past the altitude of every cut-set separating that solution from the initial vertex (the altitude of a set is the minimum over its elements), i.e., past the rim of the deepest basin preventing inundation of the solution. For the former, mitigating exploration is merely a matter of making the choice worse than its best sibling; the ideal amount of penalization depends on the nature of randomization applied.1 Formally, but with narrower context: Consider an hc that is derived by optimally solving relaxed problems, or just directly suppose that hc is guaranteed to be admissible and consistent (Pearl 1984). Consider the altitude (f
∗
c
(i)) of the cost-optimal solution in fc. All lower-altitude nodes comprise the *cost-optimal footprint*. Exhausting the footprint is a proof, relative to hc being admissible, of the purported optimality of the known solution (with hc consistent, exhaustion is moreover necessary for proof by search). As the order of doing so does not affect correctness of the proof, there is significant freedom/futility (depending on your perspective) in the choice of evaluation function: Every systematic search is equivalent (does the same amount of total work) if hc and f
∗
c
(i) are given. When re-expansion is a significant possibility, then the appropriate statement is that the same set of states are expanded, some, hopefully few, more than once. It follows that performing two levels of search, the outer search taking guesses at f
∗
c
(i), is a powerful idea (as in IDA∗, or in the standard treatment of optimization problems as decision problems).

That is, it is futile to attempt to expand less than A∗, but, one is free to expand that set in any order. For example, with an oracular guess of f
∗
c
(i), it is possible to terminate 1The second best sibling could be second most likely to be chosen, but it could also be the least likely to be chosen.