0
我試圖在python中實現廣度優先搜索。我試圖通過一個網格找到一條路徑,從一個廣場開始,找到朝向廣場的路徑。整個網格上都有障礙物,標有字符'o'。在「圖」是指節點,一個簡單的類的二維數組:python中的廣度優先搜索陷入無限循環
# Node class
class Node:
def __init__(self, val, pos):
self.val = val
self.pos = pos
self.visited = False
def __str__(self):
return "%s" % self.val
我知道這不是最乾淨的實現BFS的 - 我沒有太多的經驗,使用Python,所以有時我不得不使用重複的代碼,因爲我不確定python如何處理一些局部變量下的指針。無論如何,這個BFS無限循環,我無法弄清楚爲什麼。任何幫助,將不勝感激!
邊緣基本上是一個隊列,並且在更深入地移動一層之前,按照左,上,右和下的順序檢查每個節點的相鄰正方形。
# Breadth First Search
def bfs(arena, start):
# fringe implemented as a FIFO list (behaves like a queue)
fringe = []
fringe.append([start])
start.visited = True
while fringe:
# get the first path from the fringe queue
path = fringe.pop(0)
print "pop!"
# get the last node from the path
node = path[-1]
# goal check
if node.val == 'g':
print "PATH FOUND!!"
return path
# get all adjacent nodes, construct a new path and push it to the fringe queue
pos = node.pos
# get left node first
if pos[1]-1>=0:
neighbor = graph[pos[0]][pos[1]-1]
newPath = path[:]
if neighbor.val == 'o':
neighbor.visited = True
graph[pos[0]][pos[1]-1].visited = True
if neighbor is not neighbor.visited:
neighbor.visited = True
graph[pos[0]][pos[1]-1].visited = True
newPath.append(neighbor)
fringe.append(newPath)
print "left node added!"
# get node above current node
if pos[0]-1>=0:
neighbor = graph[pos[0]-1][pos[1]]
newPath = path[:]
if neighbor.val == 'o':
neighbor.visited = True
graph[pos[0-1]][pos[1]].visited = True
if neighbor is not neighbor.visited:
neighbor.visited = True
graph[pos[0-1]][pos[1]].visited = True
newPath.append(neighbor)
fringe.append(newPath)
print "top noded added!"
# get node to the right of current node
if pos[1]+1 < columns:
neighbor = graph[pos[0]][pos[1]+1]
newPath = path[:]
if neighbor.val == 'o':
neighbor.visited = True
graph[pos[0]][pos[1]+1].visited = True
if neighbor is not neighbor.visited:
neighbor.visited = True
graph[pos[0]][pos[1]+1].visited = True
newPath.append(neighbor)
fringe.append(newPath)
print "right node added!"
# get node below current node
if pos[0]+1 < rows:
neighbor = graph[pos[0]+1][pos[1]]
newPath = path[:]
if neighbor.val == 'o':
neighbor.visited = True
graph[pos[0]+1][pos[1]].visited = True
if neighbor is not neighbor.visited:
neighbor.visited = True
graph[pos[0]+1][pos[1]].visited = True
newPath.append(neighbor)
fringe.append(newPath)
print "node below added!"
,您的節點類有一些類變量,把它們放在裏面__init__,這可能是你的問題的原因 – Peeyush 2014-09-27 03:29:54
謝謝你指出!我沒有意識到這是如何在Python中的類工作。我已更新,但問題仍然存在。我會繼續尋找! – Emma 2014-09-27 03:45:53
'fringe.append([start])'應該是'fringe.append(start)'。 – Pradhan 2014-09-27 03:49:46