我要做的是在一个图上实现一个深度搜索算法来达到一个目标状态,但是我一直得到一个KeyError
。对于更小更简单的图形,它似乎可以正常工作,但这个不起作用。你知道吗
#The Graph to Search
graph = {
'state1' : set(['state2','state3','state4']),
'state2' : set(['state5']),
'state5' : set(['state10','state11']),
'state10' : set(['state20']),
'state20' : set(['state34','state35']),
'state11' : set(['state21','state22','state23']),
'state21' : set(['state36','state37']),
'state22' : set(['state38','state39']),
'state23' : set(['state40','state41']),
'state3' : set(['state6','state7','state8']),
'state6' : set(['state12','state13']),
'state12' : set(['state24']),
'state24' : set(['state42','state43']),
'state13' : set(['state25']),
'state25' : set(['state44','state45']),
'state7' : set(['state14','state15']),
'state14' : set(['state26']),
'state26' : set(['state46']), #GOALSTATE
'state15' : set(['state27']),
'state8' : set(['state16','state17']),
'state16' : set(['state28']),
'state17' : set(['state29']),
'state4' : set(['state9']),
'state9' : set(['state18','state19']),
'state18' : set(['state30','state31','state32']),
'state19' : set(['state33'])
}
#Depth First Algorithm
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
while stack:
(vertex, path) = stack.pop()
for next in graph[vertex] - set(path) :
if next == goal:
yield path + [next]
else:[enter image description here][1]
stack.append((next, path + [next]))
#Method Call
list(dfs_paths(graph, 'state1', 'state46'))
正如timgeb提到的,有更好的方法可以做到这一点。但是正如pkpnd提到的,代码有时失败的原因是一些路径状态没有相应的键,因此需要跳过它们。你知道吗
我做了一些其他的小改动,比如使用更现代的
set
语法,不使用next
作为变量名,因为这是一个内置函数。我还使用set.difference
方法,而不是-
操作数形式,因此不需要将路径列表转换为集合。你知道吗输出
相关问题 更多 >
编程相关推荐