Near-optimal solution

As explained in Classic Computer Science Problems in Swift: Essential techniques for practicing programmers

A near-optimal solution is a feasible solution whose objective value is close to the best possible value without necessarily being optimal.

A near-optimal solution is a feasible answer whose objective value lies close to the best possible value, without requiring perfect optimality. It becomes useful when exhaustive search grows too expensive, as in the traveling salesman problem. section 8.2

Approximate approaches can:

• Target a solution within a small known band of the perfect answer, such as no more than 5% less efficient. section 8.2
• Replace factorial permutation search for large traveling-salesman instances. section 8.2
• Use dynamic programming or genetic algorithms as possible strategies. section 8.2

Tour planning

For five Vermont cities, exhaustive permutation search can find a shortest 318-mile tour. With many more cities, approximation instead seeks a route close to that ideal while avoiding the rapidly expanding search space. section 8.2

Figure 8.2. Five cities in Vermont and the driving distances between them

Use the city map and distance table to compare a concrete optimal tour with the larger-instance motivation for near-optimal methods. section 8.2

How Classic Computer Science Problems in Swift: Essential techniques for practicing programmers covers it

How deep it goes

Defines bounded closeness and names techniques, but stops short of explaining their approximation procedures or guarantees.

Examples

Uses Vermont city distances, exhaustive tours, and a 318-mile shortest route to motivate approximation.

What you can do after

Evaluate approximation as a practical alternative when exhaustive traveling-salesman search becomes infeasible.

How it connects

Connects near-optimal solutions with the traveling salesman problem, dynamic programming, and genetic algorithms.

liveBookmanning.com

Read Classic Computer Science Problems in Swift: Essential techniques for practicing programmers on liveBook Get the book at manning.com

Also explained in

• 

  liveBookmanning.com
  Advanced Algorithms and Data StructuresA near-optimal solution is a feasible solution whose objective value is close to the best possible value without necessarily being optimal.

Compare how 2 books explain near-optimal solution →

Related concepts

• optimizationproduced by · Optimization is the systematic selection or adjustment of values, actions, or system designs to improve a specified objective, often subject to constraints.
• simulated annealingproduced by · Simulated annealing is a stochastic optimization method that gradually reduces the probability of accepting worse solutions to escape local optima.
• heuristicproduced by · A heuristic is a practical rule or approximate method for guiding judgment, search, or problem solving without guaranteeing an exact or optimal result.
• optimal solutioncontrasts with · An optimal solution is a feasible solution that achieves the best objective value among the alternatives considered.

This explainer was generated by Manning's knowledge graph from the text of Classic Computer Science Problems in Swift: Essential techniques for practicing programmers. The section links point to the parts of the book it draws on.