Lecture 8. 暴力

优点是

• 穷举，所以如果有解，一定能找到解。
• 好写。

缺点是

• 慢。
• 没有体现算法的创造性。

旅行商问题 Travelling Salesman Problem

是 NP 完全的

在具有 $n$ 个节点的完全图上，一个推销员，希望访问每个节点（城市）恰好一次，然后回到起点。每条边都有一个边权 $c(i,j)$，表示从 $i$ 到 $j$ 的代价。

这个推销员希望最小化总代价。

这个问题很难解决，但是可以暴力，即列出 ${V} - S$ 的所有 $(V-1)!$ 个排列，然后再把起点 $S$ 加入路径序列，依次检查。

对于每个排列，$\Theta(V)$ 地走一遍计算路径。故总时间复杂度是 $\Theta(V \times (V-1)!) = \Theta(V!)$。