Is node count a bad measure?

No. It helps explain algorithmic behavior, but its relationship to time depends on the work performed per node.

Can a more expensive search still be worthwhile?

Yes. It may produce enough improvement in the solution or a needed guarantee to justify the added resources.

Does search cost include carrying out the plan?

In the classical distinction used here, no. Execution or path cost is reported separately, though a decision model may consider both.

AI Glossary / Graphs and symbolic AI / Intermediate

Search cost

Definition

Search cost is the resource expenditure involved in finding a solution. In AI problem solving, it commonly refers to computation such as running time, generated or expanded nodes, memory use and the work of evaluating candidates, rather than the cost of executing the resulting solution.

What it means

A route planner spends resources deciding which route to recommend. Traveling that route creates a different cost. A search method can find an excellent route only after substantial computation, or quickly return a more expensive route.

The distinction is useful whenever an AI system must decide how much thinking is worthwhile before acting. Searching longer can improve the result, but the extra work may itself consume time, money or a limited operational opportunity.

“Search cost” needs a stated measurement. A count of expanded nodes is a useful algorithmic indicator, but it is not automatically equivalent to seconds or currency. Different nodes can require very different amounts of computation, especially when evaluating them involves external tools or expensive models.

How it works

Choose the resource measures relevant to the search. Common measures include elapsed time, CPU time, peak memory, candidate evaluations and the number of generated or expanded search nodes. Generated nodes and expanded nodes are not necessarily the same count.

Measure solution quality separately, using the problem's objective. This might be route length, schedule duration or a constraint penalty. Comparing algorithms then involves both the effort spent searching and the quality of the returned result.

A heuristic can reduce the number of nodes examined while adding evaluation work at each node. Preprocessing, loading a model, communicating with services and checking duplicates can also contribute costs that a simple node count omits.

If search and execution costs are combined into one decision measure, express them in compatible units or use an explicit trade-off. Adding 200 milliseconds directly to 10 kilometers produces no meaningful total. A business may instead assign a justified delay penalty or evaluate multiple criteria separately.

Three practical examples

A route service compares computation time with the travel time saved by a more thorough planning method.
A configuration system tracks expensive candidate evaluations when each evaluation requires a detailed simulation.
A scheduling tool reports peak memory and time to its first feasible plan, alongside the final plan's objective value.

Think of it this way

Think of spending time comparing travel options before making a booking. The comparison effort and the eventual journey's cost are different, even though both affect the decision.

The analogy does not supply a universal stopping rule. The value of further comparison depends on the stakes, available information and the consequence of delay. Some searches also need guarantees that cannot be replaced by a casual time estimate.

Worked example

Consider two invented search methods on the same task. Method A expands 20,000 nodes and takes 0.02 milliseconds per expansion, giving 400 milliseconds of expansion work. Method B expands 5,000 nodes but takes 0.10 milliseconds per expansion because its heuristic is more expensive, giving 500 milliseconds.

B examines only one-quarter as many nodes, yet its expansion work takes longer in this simplified calculation. Fewer expansions alone do not establish lower running time. Initialization, memory operations and other overheads have been omitted from both totals.

Now suppose A returns a plan with execution cost 120 units, while B returns one costing 110 units. The better plan saves 10 execution units, but deciding whether its additional search effort is worthwhile requires knowing how those resources are valued and whether a deadline applies.

The example separates three quantities: node count, computation time and solution cost. It does not claim that either method is generally preferable.

Illustrative case study

In a fictional project, Willow Planner reports that a new heuristic reduces node expansions dramatically. During integration, however, each heuristic evaluation calls a slow external service, and users wait longer for a result.

The team adds end-to-end timing and counts external calls separately. It also checks whether caching changes the comparison and whether the returned plans have equivalent quality.

The case illustrates why an internal search statistic cannot substitute for the user's experience or a complete cost model. It provides no measured performance result for a real algorithm.

Common misconceptions and mistakes

Search cost and path cost mean the same thing. One concerns finding a solution; the other concerns the represented solution path.
Fewer expanded nodes always means faster execution. Per-node work and overhead can differ.
A stronger heuristic is free. Computing it can be expensive.
Only CPU time matters. Memory, waiting, service calls and deadlines may also matter.
Costs in incompatible units can simply be added. A meaningful comparison needs an explicit conversion or multiple measures.
More computation always improves the outcome enough to justify itself. Improvement may be small, uncertain or too late to use.

Business use

When assessing an AI planner, report time to the first usable result, quality at the deadline and resource consumption. These measures often tell a clearer story than a single average runtime.

Include preprocessing and external dependencies when they are part of the intended use. If a costly preparation step is reused across many queries, report that assumption rather than hiding or charging it inconsistently.

Operationally, choose a stopping policy that fits the task. An interactive recommendation, an overnight planning run and a time-critical control decision can value computation differently. Maintain a distinction between the best solution found so far and a result whose optimality has been established.

Check your understanding

Method X evaluates 1,000 candidates at two milliseconds each. Method Y evaluates 400 candidates at six milliseconds each. Ignoring overhead, which spends less evaluation time?

Answer: X uses 2,000 milliseconds; Y uses 2,400. Y evaluates fewer candidates but takes more total evaluation time.

Related terms

Computational complexity
Anytime algorithm
Bounded rationality
Stopping rule
Path cost
node expansion
heuristic evaluation
resource allocation

Learn next

Compare two simple search procedures using a table with four columns: generated nodes, expanded nodes, elapsed time and solution quality. Explain any disagreement between the rankings, and state which preparation or external-call costs your measurements include.

Sources

Russell and Norvig's search-strategy evaluation slides: https://aima.cs.berkeley.edu/slides-pdf/chapter03.pdf

Their informed-search slides, discussing heuristic guidance and search effort: https://aima.cs.berkeley.edu/slides-pdf/chapter04a.pdf

Relevant search descriptions were reviewed. The timing calculations and Willow Planner case are original illustrations, not reported benchmark data.

Previous: Search-based software engineering Next: Search engine