寻找最佳路径(如果存在)

Question

赋予参数ķ和阵列[A ₀,一个₁,一个₂,一个₃,...,A _Ñ ],其中一个_X定义的地形高度,发现需要使地形工作量最少的差强人意.如果两个相邻位置之间的差异小于或等于k,则地形是可通过的.在地形的高度一个_X是可以改变的,需要的工作量是相等的高度,你赚取差价.的高度一个₀和_Ñ不能被改变,并且因此一些地形可能完全unpassable.

我一直在挣扎了一会儿:这是我想通了,至今:当然找到一个解决方案(不采取必要考虑工作的最低量)很简单-让"阶梯"从一₀到一_ñ如图中k = 2(红色点是旧地形的高度,灰色是新的).

(此特定地形的输入将为:k = 2,[0,2,3,2,5,4,5,7])

正如您所看到的,新地形并未考虑旧地形,因此将旧地形转换为此地形所需的工作量可能很大.

确定路径是否存在是微不足道的:k> = | a ₀ -a _n |/n,但我不知道如何找到最佳解决方案.

Answer 1

使用单纯形法求解以下线性规划。

minimize sum_i y_i
subject to
# y_i is notionally |x_i - a_i|
# equality holds in every optimal solution
y_i >= x_i - a_i for all i
y_i >= a_i - x_i for all i
# transformed terrain is passable, i.e., |x_i - x_{i+1}| <= k
x_i - x_{i+1} <= k for all i
x_{i+1} - x_i <= k for all i