我目前处于优化问题之中。我正在使用动态编程，在完成计算后，剩下的是N x N矩阵，该矩阵表示：如果采用，mat[i][j]则该值是从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的所有路径？
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，而列表中的所有组合。您可以通过算法简单地执行此操作，以从n返回k个元素的所有组合。
在这里，我编写了代码来解决您在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)
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句