视频中定义的旅行商问题 (TSP) 是什么？

适用条件

• 存在一个有限的 $n$ 个城市集合。
• 目标是最小化总路径长度。
• 每个城市必须恰好访问一次。

理解与推导

1. 将该问题识别为经典优化问题。
2. 陈述目标：寻找最短的可能路径。
3. 指定约束：每个城市恰好访问一次。
4. 将问题可视化为连接二维平面上各点的路线。

例子

旁白将 TSP 定义为寻找穿过 n 个城市集合的最短可能路径，使得每个城市恰好访问一次。图表标题为“Traveling Salesman Problem (TSP)”；红点代表城市，绿色线段构成一条巡回路线。

容易误解的地方

• 认为因为 TSP 的陈述很简单，所以它也很容易解决。
• 假设路径不需要返回起始城市（尽管视频侧重于巡回路线方面）。

观看对应讲解

继续追问

• 为什么视频说尽管 TSP 的陈述很简单，但它很难解决？
• 游乐场使用了哪两种机器学习方法来解决 TSP？
• 在遗传算法 TSP 演示中，贪婪交叉做了什么？