给出一张带有正权边的图、一对节点和它们之间的路径,想要找到一种最佳算法,该算法可以告诉我如何修改图的边权重,使得指定的路径尽可能地成为A*算法计算的节点间的最短路径。当然,如果我将最短路径作为输入,输出将是“不做任何更改”。
注意:最小程度指的是对边权进行的总更改。例如,另一个极端情况是将未在指定路径上的所有边的权重更改为无穷大,而沿着路径的权重更改为零。
注意:最小程度指的是对边权进行的总更改。例如,另一个极端情况是将未在指定路径上的所有边的权重更改为无穷大,而沿着路径的权重更改为零。
i = 0
):
i
步的成本,我们称之为c(p_0...p_i)
。c(S)
,以及它的前i
个组件的成本,我们用c(s_0...s_i)
表示。w(p_n)
减少c(p_0...p_i) - c(s_0...s_i) - epsilon
,其中epsilon
是一些接近于零的常数,您希望路径小于c(S)。i
增加1。如果epsilon
为0,则P = S
。否则,你应该不超过理想更新的epsilon * |P|
减少。
c(s_0...s_i+1)
,从c(s_0...s_i)
中推导出来,但是这留给读者自己思考。;-)