受约束的 TSP：找到一个在 s 开始（和结束）的最小长度旅行，并保留子集城市的相对顺序
A Constrained TSP: Find a minimum length tour which starts (and ends) at s and preserves the relative ordering of to sub set cities
我正在尝试解决动态问题。我熟悉经典的 TSP，但这里是一个受约束的 TSP，其中有两组城市并且必须保留城市的相对顺序。这是棘手的部分。
给定，
起始城市 s
n个城市的序列A=〈a_1,a_2,…,a_n〉
n个城市的另一个序列B=〈b_1,b_2,…,b_n〉
距离函数 D(x,y) 取任意一对城市，returns 是它们之间的最短距离。
从技术上讲，我们可以说 L={s,a_1,a_2,…,a_n,b_1,…,b_n} 并且 D 是一个函数
Objective是寻找一个从s开始（到s结束）的所有2n+1个城市的最短行程，满足以下条件：
必须保留A中城市的相对顺序。
并且必须保留B中城市的相对顺序。
换句话说：
对于所有 i:1 ≤ i < n，城市 a_i 必须在城市 a_(i+1),a_(i+2),…,a_n
之前访问
对于所有 i:1 ≤ i < n，城市 b_i 必须在城市 b_(i+1),b_(i+2),…,b_n
之前访问
示例：
A=〈a_1,a_2,a_3〉
B=〈b_1,b_2,b_3〉
合法旅行（隐含return到s）：
s a_1 a_2 b_1 a_3 b_2 b_3
s b_1 a_1 a_2 b_2 b_3 a_3
非法旅行：
s a_1 b_2 a_2 b_1 a_3 b_3 （b_2 在 b_1 之前访问过）.
我无法在 O(n^2) 时间内找到子问题。谁能帮帮我。
动态规划的成本取决于描述子问题需要保持多少状态。
在这里你可以用一系列数字对 (i, j, k) 描述一个解决方案，其中 i 是 A 数组的索引，表示你访问了 A 的多少个点，j 是一个类似的索引B 数组，k 有点说明你目前所在的位置。所以(1,0,0) (2,0,0) (2,1,1)...表示前两步是到A数组中的点，下一步是到B数组中的点.
描述部分解需要存储的状态就是 (i,j,k)。对于每个 (i,j,k)，您需要计算到该点的最佳成本，例如如果 k=0 那么你正在计算到 A 点的最佳成本，你可以通过查看 (i-1, j, 0) (i-1, j, 1) 的最佳成本和 A[ i-1] 和 A[i] 以及 B[j-1] 和 A[i] 之间.
像往常一样，当您计算出（所有 A，所有 B，0）和（所有 A，所有 B，1）的最佳成本并添加距离时，请保留足够的簿记回到起点，您可以从其中最小的一个开始回溯以恢复游览。
我正在尝试解决动态问题。我熟悉经典的 TSP，但这里是一个受约束的 TSP，其中有两组城市并且必须保留城市的相对顺序。这是棘手的部分。
给定，
起始城市 s
n个城市的序列A=〈a_1,a_2,…,a_n〉
n个城市的另一个序列B=〈b_1,b_2,…,b_n〉
距离函数 D(x,y) 取任意一对城市，returns 是它们之间的最短距离。
从技术上讲，我们可以说 L={s,a_1,a_2,…,a_n,b_1,…,b_n} 并且 D 是一个函数
Objective是寻找一个从s开始（到s结束）的所有2n+1个城市的最短行程，满足以下条件：
必须保留A中城市的相对顺序。
并且必须保留B中城市的相对顺序。
换句话说：
对于所有 i:1 ≤ i < n，城市 a_i 必须在城市 a_(i+1),a_(i+2),…,a_n
之前访问
对于所有 i:1 ≤ i < n，城市 b_i 必须在城市 b_(i+1),b_(i+2),…,b_n
之前访问
示例：
A=〈a_1,a_2,a_3〉
B=〈b_1,b_2,b_3〉
合法旅行（隐含return到s）：
s a_1 a_2 b_1 a_3 b_2 b_3
s b_1 a_1 a_2 b_2 b_3 a_3
非法旅行：
s a_1 b_2 a_2 b_1 a_3 b_3 （b_2 在 b_1 之前访问过）.
我无法在 O(n^2) 时间内找到子问题。谁能帮帮我。
动态规划的成本取决于描述子问题需要保持多少状态。
在这里你可以用一系列数字对 (i, j, k) 描述一个解决方案，其中 i 是 A 数组的索引，表示你访问了 A 的多少个点，j 是一个类似的索引B 数组，k 有点说明你目前所在的位置。所以(1,0,0) (2,0,0) (2,1,1)...表示前两步是到A数组中的点，下一步是到B数组中的点.
描述部分解需要存储的状态就是 (i,j,k)。对于每个 (i,j,k)，您需要计算到该点的最佳成本，例如如果 k=0 那么你正在计算到 A 点的最佳成本，你可以通过查看 (i-1, j, 0) (i-1, j, 1) 的最佳成本和 A[ i-1] 和 A[i] 以及 B[j-1] 和 A[i] 之间.
像往常一样，当您计算出（所有 A，所有 B，0）和（所有 A，所有 B，1）的最佳成本并添加距离时，请保留足够的簿记回到起点，您可以从其中最小的一个开始回溯以恢复游览。