对于大学作业,我们必须实现加权图的递归朴素最短路径算法。它应该检查所有的路线,从中我们可以找到最短的。在
我们已经在研究Python脚本很多时间了,但是我们不能让它正常工作。这就是我们现在所拥有的:
import numpy as np
global paths
paths = []
class Path:
def __init__(self):
self.NodeArray = [];
self.Weight = 0;
def vindpaden(start,end,pad):
pad.NodeArray.append(start)
print "path so far: " + str(pad.NodeArray)
global paths
print "Start:" + str(start) + ", " + "end: " + str(end)
if start == end:
print "returning"
paths.append(pad)
else:
for j in range(len(graph)):
if (j not in pad.NodeArray) and graph[start][j] != -1:
newpaths = vindpaden(j,end,pad)
graph = np.loadtxt("input2.txt")
graph = graph.astype(int)
start = 0
end = 1
path = Path()
vindpaden(start,end,path)
print "###### results:"
for p in paths:
print "length: " + str(p.Weight) + ", path: " + str(p.NodeArray)
我们使用邻接矩阵作为输入。对于测试,我们使用简单的测试图:
具有以下邻接矩阵(其中-1表示无连接):
^{pr2}$这将产生以下输出:
path so far: [0]
Start:0, end: 1
path so far: [0, 2]
Start:2, end: 1
path so far: [0, 2, 1]
Start:1, end: 1
returning
path so far: [0, 2, 1, 3]
Start:3, end: 1
######
length: 0, path: [0, 2, 1, 3]
因此,您可以看到它通过2找到从点0到点1的路径,然后它应该将路径[0,2,1]添加到数组路径中,并继续从点2查找路径。相反,它返回(不正确的)路径[0,2,1,3]。最后,数组路径中唯一的路径是[0,2,1,3],这也很奇怪。在
这就是我们期望的输出:
path so far: [0]
Start:0, end: 1
path so far: [0, 2]
Start:2, end: 1
path so far: [0, 2, 1]
Start:1, end: 1
returning
path so far: [0, 2, 3]
Start:3, end: 1
path so far: [0 ,2, 3, 1]
Start:1, end: 1
returning
######
length: 0, path: [0, 2, 1]
length: 0, path: [0, 2, 3, 1]
请注意,我们目前没有使用属性weight。任何帮助将不胜感激!在
吉姆
看起来您的问题是您只创建了
Path()
的单个实例,这会导致该实例的NodeArray
损坏。我认为发生的情况如下:NodeArray
包含{2
开始,1
之后的下一个节点是3
,因此3
被添加到NodeArray
列表中。因为列表没有被清除,新节点(3
)只是添加到末尾,结果是[0, 2, 1, 3
]。在1
已经在当前的NodeArray
中,if语句if (j not in pad.NodeArray) and graph[start][j] != -1:
失败,函数停止。在我认为您需要做的是在每次调用}复制到新的
vindpaden()
时创建一个新的Path()
,并将当前的Path
的{Path
。在相关问题 更多 >
编程相关推荐