Exhaustion
暴力法
Brute force method
旅行商问题
Traveling Salesperson Problem, TSP
在给定一组城市和它们之间的距离或成本时，找到一条最短路径，使得旅行商能够恰好访问每个城市一次，最后返回出发点。
For example, in the following figure, a minimum-cost tour is 𝑢, 𝑤, 𝑣, 𝑥, 𝑢 , with cost 1+2+1+3=7
步骤
- 绘制并列出所有可能的路径。
- 计算每条路径的距离。
- 选择最短路径作为最优解。
回溯算法
Backtracking Algorithms: a clever implementation of exhaustive search
从一个起始状态开始，不断地尝试各种可能的选择，当发现选择导致无法得到有效解时，就回退到上一步，尝试其他的选择。
高速公路重建问题
Turnpike Reconstruction Problem
- NP-hard
给定一个子集距离集合 D，其中 ，di 表示两个点之间的距离。
要求找到一组点 ，pi 表示高速公路上的点，使得对于所有的 i ≠ j，都有 |pi - pj| ∈ D。即对于任意两个不同的点 pi 和 pj，它们之间的距离必须在子集距离集合 D 中。