第一次见,mark

首先是旅行商问题(Travelling salesman problem),算导描述:平面上n个点,确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的。要求每个点都仅经历一次。

如图,考虑bitonic tour来简化TSP,即从leftmost开始严格从左至右再从右至左,跟POJ 2677一样,即双调。

- 阅读剩余部分 -