我正在为一门编程课程解决一个问题，但是我在开发适用于此问题的算法方面遇到了麻烦。问题如下：
你要进行一次长途旅行。你从第0英里标志处开始行驶。沿途有n家旅馆，它们位于里程碑a1 < a2 < ... < an处，其中每个ai都是从起点测量的。你只能在这些旅馆停留，但可以选择在哪些旅馆停留。你必须在最后一个旅馆（距离为an）停留，那是你的目的地。你希望一天能行驶200英里，但这可能无法实现（取决于旅馆之间的间隔）。如果你在一天内行驶了x英里，那么这一天的惩罚为（200-x）^2。你想规划自己的旅程，以便最小化总罚款，即所有旅行日的日罚款之和。请给出一种有效的算法，确定停留的最佳旅馆序列。
我的直觉告诉我从后面开始检查罚款值，然后以正向方向匹配它们（导致O(n ^ 2)的运行时间，这对于这种情况来说是足够优化的）。
有人看到实现上可能使这个想法起作用的任何可能方法或者有任何关于可能的实现的想法吗？
x 是一个标记号，ax是到达那个标记的里程数，px是到达那个标记的最小惩罚，则可以计算标记n的pn，如果您知道标记n之前的所有标记m的pm。pn，请查找所有标记m的pm + (200 -（an - am））^ 2的最小值，其中am < an并且（200-（an-am））^ 2 小于当前pn的最佳值（最后一部分是优化）。0，a0 = 0和p0 = 0，对于标记1，p1 = (200-a1)^2。有了这些起始信息，您可以计算p2、p3等，直到pn。
编辑：切换为Java代码，使用来自OP评论的示例。请注意，这不具有第二段中描述的优化检查。public static void printPath(int path[], int i) {
if (i == 0) return;
printPath(path, path[i]);
System.out.print(i + " ");
}
public static void main(String args[]) {
int hotelList[] = {0, 200, 400, 600, 601};
int penalties[] = {0, (int)Math.pow(200 - hotelList[1], 2), -1, -1, -1};
int path[] = {0, 0, -1, -1, -1};
for (int i = 2; i <= hotelList.length - 1; i++) {
for(int j = 0; j < i; j++){
int tempPen = (int)(penalties[j] + Math.pow(200 - (hotelList[i] - hotelList[j]), 2));
if(penalties[i] == -1 || tempPen < penalties[i]){
penalties[i] = tempPen;
path[i] = j;
}
}
}
for (int i = 1; i < hotelList.length; i++) {
System.out.print("Hotel: " + hotelList[i] + ", penalty: " + penalties[i] + ", path: ");
printPath(path, i);
System.out.println();
}
}
输出结果为：
Hotel: 200, penalty: 0, path: 1
Hotel: 400, penalty: 0, path: 1 2
Hotel: 600, penalty: 0, path: 1 2 3
Hotel: 601, penalty: 1, path: 1 2 4
E 时，它会看到 pC = 0，并具有潜在的 pE 值为 1 ((200 - 201)^2)，并且会选择它，而不是具有潜在的 pE 值为 (200 - 1)^2 的 pD = 0。 - Andrew Clark看起来你可以使用动态规划解决这个问题。子问题是：
d(i) ：从起点到酒店i时可能的最小罚款。
递推公式如下：
d(0) = 0，其中0是起始位置。
d(i) = min_{j=0, 1, ... , i-1} ( d(j) + (200-(ai-aj))^2)
为了到达酒店i的最小惩罚是通过尝试前一天所有停留地点，加上今天的惩罚，并取其中最小值。
为了找到路径，我们在一个单独的数组（path[]）中存储了我们必须从哪个酒店出发才能达到该特定酒店的最小惩罚。通过从path[n]向后遍历数组，我们获得了路径。
运行时间复杂度为O(n^2)。
这相当于在一个有向无环图中寻找两个节点之间的最短路径。Dijkstra算法的时间复杂度为O(n^2)。
不过，你的直觉更好些。从后往前开始，计算停留在该酒店的最小罚款金额。第一个酒店的罚款金额只是(200-(200-x)^2)^2。然后对于其他酒店（按照倒序），向前扫描以找到罚款金额最低的酒店。一个简单的优化是一旦罚款成本开始增加就停止，因为这意味着你已经超过了全局最小值。
k < l，让一条边在 ak 和 al 之间运行，其权重为 (200-dist(ak,al))^2。如果您以这种方式构建图，则确实是一个最短路径问题。但是，A* 很可能会失败，因为我们的距离度量并不真正是度量，因为它不满足三角不等式。 - biziclop最近我遇到了这个问题，想分享一下我的解决方案，使用了Javascript编写。
和大多数以上的解决方案类似，我采用了动态规划方法。为了计算penalties[i]，我们需要搜索前一天的停留地点，使罚款最小。
penalties(i) = min_{j=0, 1, ... , i-1} ( penalties(j) + (200-(hotelList[i]-hotelList[j]))^2) 这个解决方案不假定第一个罚款是Math.pow(200 - hotelList[1], 2)。我们不知道是否在第一个停留点停留是最优的，所以不应该做出这样的假设。
为了找到最优路径并存储沿途所有的停留点，使用了辅助数组path。最后，倒序遍历数组来计算finalPath。
function calculateOptimalRoute(hotelList) {
const path = [];
const penalties = [];
for (i = 0; i < hotelList.length; i++) {
penalties[i] = Math.pow(200 - hotelList[i], 2)
path[i] = 0
for (j = 0; j < i; j++) {
const temp = penalties[j] + Math.pow((200 - (hotelList[i] - hotelList[j])), 2)
if (temp < penalties[i]) {
penalties[i] = temp;
path[i] = (j + 1);
}
}
}
const finalPath = [];
let index = path.length - 1
while (index >= 0) {
finalPath.unshift(index + 1);
index = path[index] - 1;
}
console.log('min penalty is ', penalties[hotelList.length - 1])
console.log('final path is ', finalPath)
return finalPath;
}
// calculateOptimalRoute([20, 40, 60, 940, 1500])
// Outputs [3, 4, 5]
// calculateOptimalRoute([190, 420, 550, 660, 670])
// Outputs [1, 2, 5]
// calculateOptimalRoute([200, 400, 600, 601])
// Outputs [1, 2, 4]
// calculateOptimalRoute([])
// Outputs []
penalties(i) = min_{j=0, 1, ... , i-1} ( penalties(j) + (200-(hotelList[i]-hotelList[j]))^2) 我想强调的一件事是，与这个问题中得票最高的解决方案相反，我不同意第一个罚款应该被计算为 Math.pow(200 - hotelList[1], 2)。我们不知道在第一个站停留是否最优，所以我认为不应该做出这种假设。 - Maja Kudlickaclc
clear all
% Data
% a = [0;50;180;150;50;40];
% a = [0, 200, 400, 600, 601];
a = [0,10,180,350,450,600];
% a = [0,1,2,3,201,202,203,403];
n = length(a);
opt(1) = 0;
prev(1)= 1;
for i=2:n
opt(i) =Inf;
for j = 1:i-1
if(opt(i)>(opt(j)+ (200-a(i)+a(j))^2))
opt(i)= opt(j)+ (200-a(i)+a(j))^2;
prev(i) = j;
end
end
S(i) = opt(i);
end
k = 1;
i = n;
sol(1) = n;
while(i>1)
k = k+1;
sol(k)=prev(i);
i = prev(i);
end
for i =k:-1:1
stops(i) = sol(i);
end
stops
第一步（共2步）
子问题：
在这种情况下，“C(j)”被认为是到达酒店“ai”时获得的最小罚款的子问题，其中“0<=i<=n”。问题所需的值为“C(n)”。
查找最小总罚款的算法：
如果旅行在位置“aj”停止，则上一个停靠点将是“ai”，并且i的值应小于j。然后，所有“ai”的可能性都如下所示：
C(j) min{C(i)+(200-(aj-ai))^2}，其中0<=i<=j。
将“C(0)”的值初始化为“0”，将“a0”设置为“0”，以找到其余的值。
为了找到最佳路线，增加每次迭代的“j”和“i”的值，并使用此详细信息从“C(n)”中回溯。
这里，“C(n)”指的是最后一个酒店的罚款（即“i”的值介于“0”和“n”之间）。
伪代码：
//函数定义
Procedure min_tot()
//外循环表示j的值从1到n：
//计算每个站点的距离C(j) = (200 - aj)^2
//内循环表示i的值从1到j-1：
//计算总罚款并将最小总罚款分配给"c(j)"
C(j) = min (C(i), C(i) + (200 - (aj - ai))^2}
//返回最后一个旅馆的总罚款值
return C(n)
第2步2
解释： 以上算法用于找到从起点到终点的最小总罚款。
算法的运行时间：
该算法包含“n”个子问题，每个子问题需要“O(n)”时间来解决。
只需计算“O(n)”的最小值。
回溯过程需要“O(n)”次。
算法的总运行时间为nxn = n ^ 2 = O(n ^ 2)。
因此，该算法完全需要“0(n ^ 2)”的时间来解决整个问题。
我认为你不能像sysrqb所说的那样轻松地做到。
顺便说一下，从起点还是终点开始没有任何区别；目标是找到每条路线上最少的停靠点，每个停靠点尽可能接近200米。
问题陈述似乎允许每天超过200米的旅行，而罚款对超出或低于（因为它是平方的）同样有效。这更喜欢每天超过英里数而不是低于，因为罚款是相等的，但目标更接近。
然而，考虑到这个布局
A ----- B----C-------D------N
0 190 210 390 590
这并不总是正确的。最好选择B->D->N，总惩罚只有(200-190)^2 = 100。通过C->D->N前往会导致惩罚为100+400=500。
答案看起来像是一个完整的广度优先搜索，如果您已经有了到达点P的最佳解决方案，则可以进行主动修剪，删除到目前为止的所有解决方案。
sum(penalty-x) > sum(penalty-p) AND distance-to-x <= distance-to-p - 200
这将是一个O(n^2)算法
作为概念证明，这是我的JavaScript解决方案，使用动态规划而没有嵌套循环。
我们从零英里开始。
通过将当前酒店的罚款与上一个酒店的罚款进行比较，保持罚款尽可能低，找到下一个停靠点。
一旦我们有了当前最小值，我们就找到了今天的停靠点。我们将此点分配为下一个起始点。
可选地，我们可以保留罚款总额：
let hotels = [40, 80, 90, 200, 250, 450, 680, 710, 720, 950, 1000, 1080, 1200, 1480]
function findOptimalPath(arr) {
let start = 0
let stops = []
for (let i = 0; i < arr.length; i++) {
if (Math.pow((start + 200) - arr[i-1], 2) < Math.pow((start + 200) - arr[i], 2)) {
stops.push(arr[i-1])
start = arr[i-1]
}
}
console.log(stops)
}
findOptimalPath(hotels)更复杂但是可靠的方法是获取每个Y的倍数最接近的两家酒店；前一家和后一家。这将产生一个X'对的数组，可以在2^X'时间内遍历所有可能的排列。您可以通过将Dijkstra应用于这些对的地图来缩短时间，这将确定每天旅行的最小成本路径，并且大约需要(2X')^2的时间来执行。这可能是保证产生最佳结果的最有效算法。
正如 @rmmh 所提到的，您正在寻找最小距离路径。这里的距离是惩罚 (200-x)^2
因此，您将尝试通过找到最小惩罚来找到停止计划。
假设 D(ai) 给出了 ai 与起点的距离
P(i) = min { P(j) + (200 - (D(ai) - D(dj)) ^2 } where j is : 0 <= j < i
从简单分析来看，它似乎是一个 O(n^2) 算法（= 1 + 2 + 3 + 4 + .... + n）= O(n^2)
{0, 200, 400, 600, 601}。 - greybeard