algorithm - 在图中找到精确长度和成本的所有路径

Question

我目前正处于优化问题的中间。我正在使用动态规划，在完成计算后，我得到了 N x N 矩阵，上面写着:如果你采用 mat[i][j] 那么值(value)就是成本从 i 到 j == 邻接矩阵。

我还可以访问两个变量 K 和 C，它们可以分别解释为路径长度和路径成本。

那么有没有一种算法可以找到所有长度为 K 且成本为 C 的路径？

编辑:

这是邻接矩阵的示例。路径从 0 -> 8，成本为 48，长度为 3。

因此，例如，一条有效路径为:0->3 (15)、3->6 (15 + 13)、6->8 (15 + 13 + 20 = 48)。另一个可能是:0->4 (20)、4->6 (20 + 8)、6 -> 8 (20 + 8 + 20 = 48)。

无效路径可能包括:0->1(8), 1->2(8 + 4), 2->3(8 + 4 + 3), 3->4 (8 + 4 + 3 +5), ..., 但长度大于 3，所以这是无效的，同样的东西 0->8 的成本是 48，但长度是 1。

    1   2   3   4   5   6   7   8
---------------------------------
0:  8  12  15  20  26  28  37  48
1:----  4   7  12  18  20  29  40
2:--------  3   8  14  16  25  36
3:------------  5  11  13  22  33
4:----------------  6   8  17  28
5:--------------------  2  11  22
6:------------------------  9  20
7:---------------------------- 11

实际上，现在看来，我发现我必须重新表述我的问题。顶点的数量是在用户输入期间确定的，长度和成本也是如此。你总是从第一个顶点到最后一个顶点。无论您采取什么路径(现在忽略长度)，从第一个顶点到最后一个顶点的成本总是 C，唯一变化的是长度。

所以新的(更好的)问题是，如何找到从第一个顶点到最后一个顶点的所有路径，长度为 K？

Answer 1

OP 说:你总是从第一个顶点到最后一个顶点。所以:

• for any i->j, the index j must be greater than i.

并且作为示例(根据 OP 的解释)，边的成本是线性累加。这意味着:

• mat[i][k] + mat[k][j] = mat[i][j]

所以:

• C(i->j) == C当且仅当 mat[i][j] == C.

假设存在mat[i][j] == C和 j-i<=K ，问题可以简化为选择K-1来自 i+1 的节点至 j-1 , 并列出所有的组合。你可以简单地通过 Algorithm to return all combinations of k elements from n 来做到这一点.

---

我在这里写了一个代码来解决你的例子在python中进行测试:

N = 9
mat = [None] * (N-1)
mat [0] =[None,    8,   12,   15,   20,   26,   28,   37,   48]
mat [1] =[None, None,    4,    7,   12,   18,   20,   29,   40]
mat [2] =[None, None, None,    3,    8,   14,   16,   25,   36]
mat [3] =[None, None, None, None,    5,   11,   13,   22,   33]
mat [4] =[None, None, None, None, None,    6,    8,   17,   28]
mat [5] =[None, None, None, None, None, None,    2,   11,   22]
mat [6] =[None, None, None, None, None, None, None,    9,   20]
mat [7] =[None, None, None, None, None, None, None, None,   11]

def xcombination(seq,length):
    if not length:
        yield []
    else
        for i in xrange(len(seq)):
            for result in xcombination(seq[i+1:],length-1):
                yield [seq[i]]+result

def find_path(C, K):
    i_j = []
    paths = []
    for i in range(N):
        for j in range(i+1, N):
            if mat[i][j] == C:
                i_j.append([i, j])
    for p in i_j:
        if p[1]-p[0] >= K:
            paths += [[p[0]]+i+[p[1]] for i in xcombination(range(p[0]+1, p[1]), K-1)]
    return paths


paths = find_path(48, 3)
for path in paths:
    for step in range(len(path)-1):
        print str(path[step])+"->"+str(path[step+1])+"("+str(mat[path[step]][path[step+1]])+") ", 
    print

您示例的输出答案:

0->1(8)      1->2(4)      2->8(36)
0->1(8)      1->3(7)      3->8(33)
0->1(8)      1->4(12)      4->8(28)
0->1(8)      1->5(18)      5->8(22)
0->1(8)      1->6(20)      6->8(20)
0->1(8)      1->7(29)      7->8(11)
0->2(12)      2->3(3)      3->8(33)
0->2(12)      2->4(8)      4->8(28)
0->2(12)      2->5(14)      5->8(22)
0->2(12)      2->6(16)      6->8(20)
0->2(12)      2->7(25)      7->8(11)
0->3(15)      3->4(5)      4->8(28)
0->3(15)      3->5(11)      5->8(22)
0->3(15)      3->6(13)      6->8(20)
0->3(15)      3->7(22)      7->8(11)
0->4(20)      4->5(6)      5->8(22)
0->4(20)      4->6(8)      6->8(20)
0->4(20)      4->7(17)      7->8(11)
0->5(26)      5->6(2)      6->8(20)
0->5(26)      5->7(11)      7->8(11)
0->6(28)      6->7(9)      7->8(11)