Does unbounded-cost search ignore all costs internally?

Not necessarily. It can use cost information without guaranteeing a bound on the returned solution.

Is speedy search the only example?

No. It is one approach within a wider class of search methods that can seek any solution.

Must it return a poor solution?

No. It may return an excellent or optimal solution, but that outcome alone does not establish an optimality guarantee.

AI Glossary / Graphs and symbolic AI / Intermediate

Unbounded cost search

Definition

Unbounded-cost search seeks a valid solution without requiring its cost to fall below a specified threshold or within a specified factor of the best possible cost. The emphasis is often on finding a solution quickly. The term describes an acceptance criterion rather than one unique algorithm.

What it means

Search has at least two different costs: the resources used to find a solution and the cost of carrying out that solution. A planner may spend seconds computing a route that would take hours to travel. Reducing computation time does not necessarily reduce travel time.

In unbounded-cost search, the solution must still reach a goal and satisfy the problem's rules. What is absent is an agreed cost-quality bound. This differs from bounded-cost search, which requires a solution below an absolute limit, and bounded-suboptimal search, which requires a guarantee relative to the optimum.

Unbounded does not mean that every returned solution has infinite cost. It means the search method is not required to provide the specified kind of cost bound.

How it works

A search procedure maintains candidate states or paths, chooses one to explore and generates successors until it finds an acceptable goal or reaches another stopping condition. Different unbounded-cost methods use different priorities.

Greedy best-first search prioritizes an estimate of remaining cost. Speedy search instead uses an estimate of the number of actions remaining, ignoring their different costs in that priority. A short sequence of expensive actions can therefore look more attractive than a long sequence of cheap actions.

These choices aim to reduce search effort, but they do not universally guarantee the fastest computation. Heuristic errors, local minima, repeated states and implementation details matter. A runtime or memory limit can still be imposed. The word unbounded concerns solution-cost quality, not permission for the program to run without resource controls.

Three practical examples

A puzzle application seeks any legal solution before its response deadline, without promising the fewest moves.
A planning prototype finds a feasible workflow first so a reviewer can inspect whether the model represents the task correctly.
A configuration system finds any arrangement satisfying its requirements when there is no requirement to minimize the arrangement's separate cost measure.

Think of it this way

Think of asking someone to find any open route to a venue promptly, without requiring the cheapest fare. A route still has to reach the venue, and the directions still have to be valid.

The analogy does not imply that costs are unimportant to every traveler. If a maximum fare is part of the actual requirement, an unrestricted-cost solution is no longer sufficient for that request.

Worked example

Two paths, different acceptance rules

Consider an invented graph with exactly two routes from S to goal G. Route S - A - G has two edges costing 50 each, for a total of 100. Route S - B - C - D - G has four edges costing 2 each, for a total of 8.

After expanding S, suppose the speedy-search heuristic correctly estimates one remaining action from A and three from B. It selects A, then the goal reached through A, returning the route costing 100. That is a valid answer to the request for any solution, despite costing 12.5 times the optimum of 8.

For a bounded-cost request with a limit of 20, the same route is unacceptable. For a two-times-optimal guarantee, the permitted cost is at most 16, so it is also unacceptable. The example shows different quality requirements on one graph. It does not establish a universal runtime comparison between algorithms.

Illustrative case study

The fictional CedarPlanner team initially asks its system to produce any feasible equipment-movement plan. This helps staff identify missing action preconditions. Later, they notice that some valid plans use an expensive external transfer service unnecessarily.

The team adds a cost requirement rather than describing every feasible plan as good enough. It compares a bounded-cost method with the original first-solution baseline, recording both computation time and execution cost.

The case illustrates a change in requirements, not a failure of the original mathematical definition. The unrestricted method answered the earlier request; the revised business request needs stronger acceptance criteria. No actual savings are claimed.

Common misconceptions and mistakes

Unbounded-cost search has no time limit. Solution-cost bounds and computation budgets are different concepts.
It can return an illegal or incomplete plan. Validity remains necessary; only the stated cost-quality guarantee is absent.
A heuristic based on fewer actions always finds an answer faster. Search difficulty depends on more than remaining path length.

Business use

This search category can be useful when obtaining a feasible answer promptly is more valuable than proving its cost quality, or when feasibility is the immediate question in model development.

Before adopting it, specify what counts as a valid solution and which costs affect acceptance. Measure execution cost alongside response time so a quick answer does not hide an unsuitable plan. If the task requires a spending ceiling or a bounded gap from the optimum, select and verify a method that supports that requirement. Returning a first solution and subsequently improving it is a separate design choice, commonly associated with anytime search.

Check your understanding

A method returns a valid plan costing 90 when a plan costing 10 exists. Has it necessarily failed an unbounded-cost search request?

Answer: No. Without an additional cost requirement, validity can be sufficient. It would fail a request requiring cost at most 20.

Related terms

Learn next

Read greedy best-first search and bounded-suboptimal search. For one small graph, write separate acceptance rules for any solution, an absolute cost ceiling and a factor-of-optimum guarantee.

Sources

Christopher Wilt and Wheeler Ruml, Speedy versus Greedy Search, 2014: https://www.cs.unh.edu/~ruml/papers/d-vs-h-socs-14.pdf

Daniel Gilon, Ariel Felner and Roni Stern, Dynamic Potential Search—A New Bounded Suboptimal Search Algorithm, Section 2.1: https://tzin.bgu.ac.il/~felner/2016/dps.pdf

Relevant primary text on distance-based search and the any-solution category was reviewed. The second paper's returned indexed text was accessible, but direct opening failed. The two-route calculation is original and does not reproduce a benchmark.

Previous: Unbiased estimator Next: UNCANNY VALLEY