三七二十一
LUCKY !

问题

给定城市和距离,寻找最短路线恰好访问每个城市一次并返回。最著名的 NP-难问题之一。

Shortest route visiting all cities once. NP-hard.

为什么重要

物流配送、电路板钻孔、DNA测序。解决 TSP 意味着 P=NP。启发式算法(模拟退火、遗传算法、蚁群算法)找近似解。

最大精确解

2006年 Concorde TSP Solver 精确求解了含85900个城市的实例。

返回