双调欧几里得旅行商问题 Bitonic Euclidean Traveling-salesman Problem

Presentation on theme: "双调欧几里得旅行商问题 Bitonic Euclidean Traveling-salesman Problem"— Presentation transcript:

1 双调欧几里得旅行商问题 Bitonic Euclidean Traveling-salesman Problem
路径，从最左边的点开始，每次只能走横坐标严格递增的点最后到达最右边 的点，再沿横坐标严格递减的顺序走回最左边的点。要求每个点只能且必须 经过一次，且路径不能交叉。

2 欧几里得旅行商问题 给平面上n个点，要求找出最短的闭合回路，经过每个点有且仅有一次。
（旅行商问题：给一个图，每条边有边权，找一条最短路径经过每个点有且仅有 一次）

3 欧几里得旅行商问题是NP-hard 但是存在PTAS(Polynomial-time approximation scheme 双调欧几里得旅行商问题简化了很多

4 问题实际上是把点分成上下两份 *横坐标互不相同，先 按横坐标排一个全序， 然后再来做dp

5 所以我们有了一个O(2^n)的算法 枚举每一个点是在上方还是在下方 显然搜索空间有重复计算，下面考虑dp

6 假设已经确定其为下方的点 待确定的边 ？ ？？？

7 看起来是个O(1)的转移，O(n^2)的状态数，总复杂度O(n^2) 想想怎么转移
dp[i][j]表示从最左边的起点开始，走下面的路到第i个点，走上面的路到第j个点， 且经过min(i,j)之前的点有且只有一次需要的最短路径长度（且规定i和j之间的点已 经被走过）。 看起来是个O(1)的转移，O(n^2)的状态数，总复杂度O(n^2) 想想怎么转移 j i 如果i和j是相邻的两个点，则转移非常简单 考虑前一个点是选为上方的点还是下方的点，利用dp[i-1][j]和dp[i][i-1] dp[i][j]=min(dp[i-1][j]+d[i-1][i]，dp[i][i-1]+d[i-1][j])

8 不妨设i和j中较小（左）的点为i,，显然中间这些点不可能是和j同色的，只有可能 是和i同色的 i-1可以是上方的点吗？
需要判断两个点的连线会不会将中间的点分成两块 可以预处理，judge[i][j]表示i和j的连线会不会将i和j之间的点分成两块

9 对于每一个j，从右往左枚举i，记录i到j的斜率，更新到目前为止斜率的最大值和 最小值。
如果当前的i和j的连线被夹在前面枚举过的最大值和最小值之间，那么说明i和j将 中间的点分成了两块。 O(n^2)的预处理

10 总结 1、给n个点按横坐标从小到大排序，编号为1….n。O(n^2)处理任意两个点距离 d[i][j]。
2、预处理judge数组O(n^2)，通过两重循环，judge[i][j]表示第i个点和第j个点的连 线会不会将i+1,…,j-1这些点切成两边。 3、递归（或递推）求解dp。dp[i][j]表示从最左边的点1走两条不相交，横坐标严 格递增的路径，下面一条到达i，上面一条到达j且经过1…i…j中所有点有且仅有一 次的最短路径。则可写出转移方程（不妨设i<j，i>1且j>1） dp[i][j]=min( dp[i-1][j]+d[i-1][i] ，judge[i-1][j] ? dp[i][i-1]+d[i-1][j] : inf） 初始状态dp[1][i]=dp[i][1]=sum_{k=1….i-1}d[k][k+1]。 转移时间复杂度O(1)，状态数O(n^2)，总复杂度O(n^2)。 最后的答案是dp[n][n]。（或者dp[n-1][n]和dp[n][n-1]里面取最大再加d[n-1][n]也行）

11 谢谢！