Must the algorithm know the optimal cost?

No. The request is to satisfy an absolute limit, not a relative optimality guarantee.

Does failure to find a solution prove the budget is impossible?

Only if a suitable complete procedure has established that conclusion; a timeout alone does not.

Can an optimal search algorithm solve this problem?

Yes, but proving optimality may do work that the bounded-cost task does not require.

AI Glossary / Graphs and symbolic AI / Intermediate

Bounded cost search

Definition

Bounded cost search is a search problem in which the aim is to find a valid solution whose cost does not exceed a specified absolute limit. The search usually seeks such a solution quickly, without needing to prove that it is the cheapest possible one. The cost limit concerns the solution, not automatically the time spent computing it.

What it means

A planner might need a route using at most 50 energy units or a sequence of actions costing no more than a fixed budget. Any valid solution within that limit can satisfy the request. Searching longer for the globally cheapest solution may be unnecessary when the decision only requires meeting the bound.
This differs from bounded suboptimal search, which limits cost relative to the unknown optimum, such as no more than 1.2 times optimal. Bounded cost search uses an absolute threshold supplied by the task. The distinction matters because a fixed budget can be checked without first knowing the optimal solution cost.

How it works

Represent states, possible actions, a start state, goal conditions, and action costs. Maintain candidate partial paths and their accumulated costs. A search strategy chooses which candidates to explore, guided by estimates of whether they can lead to an acceptable solution.
When a trustworthy lower bound on remaining cost is available, add it to the cost already incurred. If that sum exceeds the permitted total, the candidate cannot satisfy the bound and can be pruned. The algorithm must still handle repeated states, termination, and the relevant assumptions about costs. It returns a goal path only after verifying validity and the required cost condition.

Three practical examples

A robot planner searches for a route within a specified energy allowance, accepting a feasible route without proving minimum energy use.
A scheduling tool finds a valid sequence whose total modeled overtime cost stays within a project limit.
A puzzle-solving service searches for a solution requiring no more than a stated number of moves when every move has unit cost.

Think of it this way

Think of looking for an apartment that meets your requirements and stays within a fixed budget. You may stop once you find a suitable option rather than proving it is the cheapest in the city. The analogy is limited because a formal search guarantee depends on an explicit state space, cost model, and algorithm, whereas real-world listings and costs may be incomplete or changing.

Worked example

Consider a fictional route graph with a cost limit of 10. One candidate route is S to A to G, with edge costs 4 and 7, totaling 11. It is a valid route but fails the budget. Another route is S to B to G, with costs 6 and 3, totaling 9. It satisfies the bounded-cost request.
Suppose a third partial route has already cost 8, and an admissible lower bound says reaching a goal requires at least 4 more. Its best possible total is at least 12, so it can be pruned. If the lower bound were 2, a total of exactly 10 would remain possible under an inclusive limit. This example uses the convention cost less than or equal to the bound; implementations that require strictly less must handle equality differently.

Illustrative case study

At fictional Fir Logistics, a planning assistant needs to produce a usable daily route within a stated distance allowance. The team realizes that its earlier objective demanded an optimal route even when any compliant route would support the operational decision.
It evaluates a bounded-cost formulation and records both solution quality and time to find an acceptable route. If the search times out, the service reports that no qualifying route was found within the available computation, rather than claiming none exists. The case is fictional and does not report a speedup or imply that distance alone captures all routing requirements.

Common misconceptions and mistakes

Do not confuse a bound on solution cost with a bound on search effort. A tight budget can make it difficult to find a solution or prove that none exists. A timeout therefore differs from a proof of infeasibility.
Pruning also requires care. If an estimate can overstate the minimum remaining cost, discarding a path based on that estimate may remove a valid solution. Negative costs, cycles, or changing costs require an appropriate formulation and algorithm. Finally, finding a solution under an absolute limit does not establish a specific percentage gap from optimal unless additional information is available.

Business use

The formulation is useful when operational requirements specify a hard budget or service limit and rapid feasibility matters more than exact optimization. Teams should define what cost includes, whether equality is allowed, and what other constraints must hold. Evaluate success rates, time to acceptable solution, and failure-reporting behavior on realistic instances. A fast answer is useful only if the plan and its cost remain valid in the intended setting.

Check your understanding

A route costs exactly 10 and the requirement is cost at most 10. Should it be rejected because it is not below 10?

Answer: No. It satisfies the inclusive bound. The search and pruning rules must match the stated comparison, especially at equality.

Related terms

Learn next

Write the acceptance condition for a search task in one line. Decide whether it requires the cheapest solution, any feasible solution, an absolute cost bound, or a relative bound from optimal. This choice determines what the algorithm must establish and what it may safely stop searching for.

Sources

Sources: Stern, Puzis, and Felner, Potential Search: A Bounded-Cost Search Algorithm: https://tzin.bgu.ac.il/~sternron/icaps2011-potential.pdf . Thayer and colleagues, Faster Bounded-Cost Search Using Inadmissible Estimates: https://www.cs.unh.edu/~ruml/papers/bees-icaps-12.pdf . Stern and colleagues, Potential-based bounded-cost search and Anytime Non-Parametric A*: https://www.sciencedirect.com/science/article/pii/S0004370214000551 .

Previous: Boundary tones Next: Bounded minimization