A near-optimal solution satisfies the problem’s constraints and achieves an objective value close to the best possible value, without guaranteeing the absolute optimum. This trade-off is useful when a small increase in cost is acceptable in exchange for a solution found within a reasonable time. section 17.2.1
Evaluate a near-optimal approach by checking:
- Whether the application tolerates a measurable gap from the optimum; safety-critical simulations may require the absolute best result. section 17.2.1
- Whether a heuristic can produce an acceptable result within the available runtime; some TSP heuristics guarantee a cost no more than twice the minimum. section 17.2.1
- Whether the search method matches the problem: simulated annealing suits discrete or nondifferentiable spaces, while gradient descent suits suitable differentiable cost functions. section 17.1.6
- Whether the candidate cost is cheap to calculate, because repeated expensive evaluations reduce the number of iterations available. section 17.1.6
Routing ten cities
For a travelling salesman problem with ten cities, the best known route has cost 1,625 miles. A genetic algorithm or simulated annealing can search for a good route faster than exhaustive optimization, but the returned route may remain near-optimal rather than guaranteed best. section 18.2 section 18.1
Figure 18.14 An instance of the traveling salesman problem: the best solution, outlined in this figure, has cost 1625.
Inspect the ten-city TSP diagram to compare a concrete best route with the approximate-search setting. section 18.2
