这是python中的搜索算法,可导航罗马尼亚城市。
class GraphTree:
graph = {
'Oradea': set(['Zerind','Sibiu']),
'Zerind': set(['Arad','Oradea']),
'Sibiu': set(['Arad','Rimnicu Vilcea','Fagaras','Oradea']),
'Arad': set(['Timisoara','Zerind','Sibiu']),
'Timisoara': set(['Lugoj']),
'Lugoj': set(['Mehadia']),
'Mehadia': set(['Drobeta']),
'Drobeta': set(['Craiova']),
'Rimnicu Vilcea': set(['Craiova','Pitesti','Sibiu']),
'Craiova': set(['Drobeta','Rimnicu Vilcea']),
'Fagaras': set(['Bucharest','Sibiu']),
'Pitesti': set(['Bucharest','Rimnicu Vilcea']),
'Bucharest': set(['Giurgiu','Urziceni','Pitesti','Fagaras']),
'Giurgiu': set(['Bucharest']),
'Urziceni': set(['Hirsova','Vaslui','Bucharest']),
'Hirsova': set(['Eforia','Urziceni']),
'Eforia': set(['Hirsova']),
'Vaslui': set(['Iasi','Urziceni']),
'Iasi': set(['Neamt','Vaslui']),
'Neamt': set(['Iasi'])}
def bfs(graph, start, end):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == end:
yield path + [next]
else:
queue.append((next, path + [next]))
def dfs(graph, start, goal):
queue = []
queue.append([start])
while queue:
path = queue.pop(0)
node = path[-1]
if node == end:
return path
for adjacent in graph.get(node,[]):
new_path = list(path)
new_path.append(adjacent)
queue.append(new_path)
print('bfs')
bfs(graph, 'Oradea', 'Neamt')
print('dfs')
dfs(graph, 'Oradea', 'Neamt')
运行算法时,我会继续遇到此错误:
---> 1 class GraphTree:
2
3 graph = {
4 'Oradea': set(['Zerind','Sibiu']),
5 'Zerind': set(['Arad','Oradea']),
另一个: 49 bfs(图,'oradea','neamt') 50印刷('dfs') -> 51 dfs(图,'oradea','neamt')
,最后:
39 path = queue.pop(0)
40 node = path[-1]
-> 41如果node == end: 42返回路径 43对于graph.get(node,[])中的相邻:
名称:名称'end'未定义
该算法在条件和声明正常上似乎是逻辑上正确的。为什么此搜索算法不起作用?
该算法应该能够导航从一个城市到另一个城市的地图,并首先使用广度(BFS)和深度(DFS)搜索返回路径。
你有
bfs(graph, start, end)
和
dfs(graph, start, goal)
^^^^
您代码的其他笔记:
- 您没有打印出搜索的结果,但看起来您打算这样做。
- 您在课堂上包裹了所有内容,但是您在代码中没有做任何其他需要的事情。
考虑到所有这些,这是另一个版本:
graph = {
'Oradea': set(['Zerind','Sibiu']),
'Zerind': set(['Arad','Oradea']),
'Sibiu': set(['Arad','Rimnicu Vilcea','Fagaras','Oradea']),
'Arad': set(['Timisoara','Zerind','Sibiu']),
'Timisoara': set(['Lugoj']),
'Lugoj': set(['Mehadia']),
'Mehadia': set(['Drobeta']),
'Drobeta': set(['Craiova']),
'Rimnicu Vilcea': set(['Craiova','Pitesti','Sibiu']),
'Craiova': set(['Drobeta','Rimnicu Vilcea']),
'Fagaras': set(['Bucharest','Sibiu']),
'Pitesti': set(['Bucharest','Rimnicu Vilcea']),
'Bucharest': set(['Giurgiu','Urziceni','Pitesti','Fagaras']),
'Giurgiu': set(['Bucharest']),
'Urziceni': set(['Hirsova','Vaslui','Bucharest']),
'Hirsova': set(['Eforia','Urziceni']),
'Eforia': set(['Hirsova']),
'Vaslui': set(['Iasi','Urziceni']),
'Iasi': set(['Neamt','Vaslui']),
'Neamt': set(['Iasi'])}
def bfs(graph, start, end):
queue = [(start, [start])]
while queue:
(vertex, path) = queue.pop(0)
for next in graph[vertex] - set(path):
if next == end:
yield path + [next]
else:
queue.append((next, path + [next]))
def dfs(graph, start, end):
queue = []
queue.append([start])
while queue:
path = queue.pop(0)
node = path[-1]
if node == end:
return path
for adjacent in graph.get(node,[]):
new_path = list(path)
new_path.append(adjacent)
queue.append(new_path)
print('bfs')
print(list(bfs(graph, 'Oradea', 'Neamt')))
print('dfs')
print(dfs(graph, 'Oradea', 'Neamt'))
当我运行此功能时,输出为:
bfs
[['Oradea', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Sibiu', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Zerind', 'Arad', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Zerind', 'Arad', 'Sibiu', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Zerind', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Sibiu', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu Vilcea', 'Pitesti', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt'], ['Oradea', 'Zerind', 'Arad', 'Timisoara', 'Lugoj', 'Mehadia', 'Drobeta', 'Craiova', 'Rimnicu Vilcea', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt']]
dfs
['Oradea', 'Sibiu', 'Fagaras', 'Bucharest', 'Urziceni', 'Vaslui', 'Iasi', 'Neamt']