双调旅行商有关问题 Bitonic Traveling Salesman Problem

双调旅行商问题 Bitonic Traveling Salesman Problem

题目: 现有p1, p2, p3...pn一系列城市。假设每两个城市之间的距离都是标准欧几里得距离。并没任意两点的x或者y坐标都是唯一的。一个双调的旅行既从最西边的城市开始严格向东旅行达到最东边的城市后又严格向西旅行回到出发点。需要走遍每一个城市。请给出一个复杂度为O（n^2）的算法来找出这个双调旅行。

思路分析：首先将给出的点根据x坐标排序，从左至右依次编号1，2，3，…，n。排序复杂度为O（nlogn）。

定义dist(i, j )：结点i到结点j之间的距离。

定义OPT(i, j)：表示从i连到1，再从1连到j的优化距离（注意：i>j，且i，j之间并未相连）

对于任意一个点i来说，有两种连接方法：i与i-1相连或者i与i-1不相连。

因此我们依次计算所有OPT(i, j)： 

当j<i-1, OPT(i, j) = OPT(i-1, j) + dist(i, i-1)

因为i点左边的邻点一定是i-1点

当j=i-1, OPT(i, j) = OPT(i, i-1) = min{OPT(k, i-1)  + dist(i, k)}, 其中1<=k<=j 

因为与i点左相邻的点可能是1到i-1点之间的任何一点。因此需要递归找到最小路径

那么所求的双调旅程即OPT(n, n) = OPT(n, n-1) + dist(n-1, n)