algorithm - 有效地找到最低总和路径

Question

这是一个很大的问题，但我有点卡住了!

我想知道这个问题是否有名称或类似的名称。

我可能过于复杂地寻找解决方案，但如果没有完整的蛮力穷举搜索(我当前的实现)，我想不出一种方法。这对于所涉及的应用程序是 Not Acceptable 。

我想知道是否有任何方法可以简化这个问题，或者我可以采用的实现策略(语言/工具选择是开放的)。

这里是问题的简要描述:

给定n个长度为k的序列:

a = [0, 1, 1] == [a1, a2, a3]
b = [1, 0, 2] == [b1, b2, b3]
c = [0, 0, 2] == [c1, c2, c3]

像这样通过序列找到长度为 k 的路径(我将给出从 a1 开始的示例，但希望您明白需要从 b1、c1 派生出相同的路径)

a1 -> a2 -> a3
a1 -> b1 -> b2
a1 -> b1 -> a2
a1 -> b1 -> c1
a1 -> c1 -> c2
a1 -> c1 -> a2
a1 -> c1 -> b1

我想知道哪些路径的总和最低:

a1 -> a2 -> a3 == 2
a1 -> b1 -> b2 == 1
a1 -> b1 -> a2 == 2
a1 -> b1 -> c1 == 1
a1 -> c1 -> c2 == 0
a1 -> c1 -> a2 == 1
a1 -> c1 -> b1 == 1

所以在这种情况下，在样本中 a1 -> c1 -> c2 是最低的。

编辑:

不好意思，只是想弄清楚导出路径的规则。例如，如果您还没有用完 b2，并且已经用完了该序列中的前一个节点，则可以从节点 a1 移动到 b2 b1).

Answer 1

使用 Dynamic Programming 的替代解决方案

让我们假设数组以矩阵 A 的形式给出，这样每一行都与原始数组之一相同。您的矩阵大小为 (n+1)x(k+1)，并确保 A[_][0] = 0

现在，用DP来解决:

f(x,y,z) = min  { f(i,y,z-1) | x < i <= n} [union] { f(i+1,0,z) }  + A[x][y]
f(_,_,0) = 0
f(n,k,z) = infinity for each z > 0

想法:在每个步骤中，您可以选择转到以下每一行(同一列)- 或转到下一列，同时减少所需的更多节点数。
移动到下一列是通过虚拟索引 A[_][0] 完成的，没有减少需要移动更多节点的数量，而且没有成本，因为 A[_ ][0] = 0。

复杂性:
这个解决方案基本上是一个蛮力，但是使用内存每个已经探索过的 f(_,_,_) 值，你基本上只需要填充一个大小为 O 的矩阵(n*k^2)，其中每个单元格初看起来需要 O(n) 时间来计算 - 但实际上可以在每步 O(1) 中迭代计算，因为你只需要最小化 ¹ 行中的新元素。这给你 O(n*k^2) - 比蛮力更好。

---

(1) 这是通过 min{x1,x2,x3,...,xk} = min{x_k, min{x1,...,k_k-1}} 完成的，我们已经知道 min{x1,...,k_k-1}