Must an optimal solution be unique?

No. Different feasible choices can share the best objective value.

Is optimal always the same as shortest?

No. Shortest is one possible objective. Other problems minimize cost, maximize utility, or use another defined criterion.

Can an optimal answer still disappoint users?

Yes. The model's objective or requirements may omit something users care about, or its assumptions may not match the operating situation.

AI Glossary / Graphs and symbolic AI / Beginner

Optimal solution

Definition

An optimal solution is a feasible solution that achieves the best value of the objective defined for a problem. In a minimum-cost search problem, it is a valid route to a goal with no higher cost than any other valid route. The term describes quality relative to a model and criterion, rather than an unrestricted claim that the solution is best in every real-world respect.

What it means

Two questions must be separated: does the candidate satisfy the requirements, and is there any permitted candidate with a better objective value? A feasible solution answers the first. An optimal solution answers both.

There may be several optimal solutions with the same value. Conversely, a problem may have no feasible solution, or may have values that improve indefinitely without attaining a best one. A search program returning a plausible answer does not by itself settle these questions. The status attached to its output should explain what has actually been established.

How it works

Define the permitted choices, the conditions they must satisfy, and the objective used to compare them. For a route problem, this means specifying the start, possible moves, goal, and path costs.

Then use a method suited to the problem. An exhaustive comparison can establish optimality for a small finite set. Larger problems usually need algorithms that organize or exclude candidates without examining every complete possibility.

Keep the candidate solution separate from the evidence supporting its quality. If computation stops early, the best candidate found so far may be useful without being proven optimal. A bound on possible improvement can help describe what remains uncertain. Changing a requirement or cost definition creates a changed optimization problem, so the previous optimality claim may no longer apply.

Three practical examples

Route planning: a shortest-distance route is optimal for distance within the supplied network, but another route might be faster if traffic is represented separately.
Staff allocation: an assignment minimizes a defined workload score while satisfying availability and coverage requirements.
AI deployment: a selection process chooses the lowest-memory model among candidates that pass specified quality checks; its claim covers that candidate set, not every model that could ever be built.

Think of it this way

Think of choosing the lightest suitcase that holds a fixed set of items and fits a stated size limit. The lightest empty bag may fail to hold the items, while the most spacious bag may break the size rule. Optimality concerns the best qualifying choice. The analogy has limits: real optimization spaces can be enormous or continuous, so proving that nothing better exists is often much harder than comparing a few suitcases.

Worked example

Consider a directed route network with exactly these connections:
S to A costs 1; A to G costs 9.
S to B costs 3; B to C costs 2; C to G costs 2.
S to D costs 4; D to G costs 3.

The goal is to reach G from S while minimizing total cost. There are exactly three complete routes in this small network. Through A, the cost is 1 plus 9 = 10. Through B and C, it is 3 plus 2 plus 2 = 7. Through D, it is 4 plus 3 = 7.

The two routes costing seven are both optimal. The route through A is feasible but suboptimal. Choosing the cheapest first move would pick A and miss the lower total cost. Counting steps alone would also be insufficient because the three-step route through B and C ties a two-step optimum.

Now add a requirement forbidding D. The route through B and C remains optimal at seven. Instead, if the objective changes to fewest moves, the two-step routes through A and D tie when D is allowed. The network has not changed, but the meaning of best has.

Illustrative case study

Fictional case: Larch Dispatch tests a route-planning prototype using a fixed delivery network. Its first demonstration presents a route labeled “optimal” because it is the shortest among five routes a heuristic happened to produce.

A reviewer asks whether those five routes exhaust all permitted choices. They do not. The team changes the label to “best found” and adds a separate exact comparison for small test networks.

The revised report distinguishes a candidate's measured distance from the evidence that establishes its optimality. This is an illustrative reporting improvement, not a claim about a real dispatch operation or a measured business saving.

Common misconceptions and mistakes

Do not equate the first solution found with the best one. Search order and objective value are different concepts.

Do not confuse a local optimum, which cannot be improved by the permitted nearby changes, with a global optimum across all feasible choices. A local method may stop before finding the best overall answer.

Avoid calling a candidate optimal merely because it beats an old baseline. Improvement is useful evidence, but another candidate could still do better. Also check whether every stated requirement was represented: a mathematically optimal route through an unavailable location is unusable for the actual task.

Business use

For procurement or project review, ask what the word optimal covers. Request the objective, constraints, candidate space, termination status, and any reported bound or tolerance.

A team can make a practical decision using a good feasible answer even when proving optimality is too expensive. The important reporting distinction is between what was achieved and what was proved. If a solution is accepted because further search costs more than the expected improvement, describe that operational trade-off explicitly rather than overstating the solver's result.

Check your understanding

In the example, is the cost-ten route invalid?

Answer: No. It reaches the goal using permitted connections. It is feasible but not optimal for total cost because two valid routes cost seven.

Related terms

Objective function
Search cost
feasible solution
global optimum
local optimum
path cost
constraints
optimality gap

Learn next

add one new connection to the example and list every resulting route before comparing costs. Then study how uniform-cost search establishes a minimum-cost result under its assumptions, and why a heuristic's first answer may need a different quality label.

Uniform-cost search

Sources

Primary source: Russell and Norvig, Artificial Intelligence: A Modern Approach, “Solving Problems by Searching,” definition and search-quality passages: https://aima.cs.berkeley.edu/4th-ed/pdfs/newchap03.pdf The hosted PDF contains an earlier chapter layout despite its URL. The network, case, and reporting examples are original.

Previous: Optimal policy Next: Optimal transport