BFS功能没有返回正确的路径

Question

嘿，伙计们，你们怎么了。为此，我必须创建一个BFS函数，以找到称为Quoridor的游戏的目标和源之间的最短路径，我相信一些人以前会玩这个游戏。当我运行它时，没有发现错误，但我希望最短路径函数返回路径，就像我在searchBFS函数中一样。另外，对于马虎的帖子感到抱歉，这是我的第一个。

下面的代码....

from interface import * 
import engine 

#public routines 

def init(gameFile, playerId, numPlayers, playerHomes, wallsRemaining): 

""" 
    For all parts the engine calls this method so the player can initialize their data. 
     gameFile - a string which is the file containing the initial board state. 
     playerId - the numeric Id of the player (0-4). 
     numPlayers - the number of players (2 or 4). 
     playerHomes - a list of coordinates for each players starting cell (PO-P4). 
     wallsRemaining - the number of walls remaining (same for all players at start).""" 

    # log any message string to standard output and the current log file 
    engine.log_msg("player.init called for player " + str(playerId) + " File=" + gameFile + 
        ', playerId=' + str(playerId) + ', numPlayers=' + str(numPlayers) + ', playerHomes=' + 
        str(playerHomes) + ', wallsRemaining=' + str(wallsRemaining)) 

    playerData = None 

    # initialize your data structure here, and then return it. It will be 
    # passed back to you as 'playerData' in the shortest_path function. 

    return playerData 

def shortest_path(playerData, source, dest): 

"""Returns a list of coordinates representing the shortest path on the 
    board between the start and finish coordinates. 
     playerData - The player's data 
     source - the start coordinate 
     dest - the end coordinate""" 

    engine.log_msg("player.shortest_path called. Source: " + str(source) + 
        ", Dest: " + str(dest)) 

    path = [] 

def searchBFS(graph, source, dest): 

"""Performs a BFS search between source and destination nodes using a queue. 
    It returns the path as a list of graph nodes (or an empty list if no path exists).""" 

    dispenser = myQueue.Queue() 
    myQueue.enqueue(source, dispenser) 

    #construct the visited list. 

    visited = set() 
    visited.add(source) 

    #loop untill either the destination is found or the dispenser 
    #is empty (no path) 

    while not myQueue.empty(dispenser): 
     current = myQueue.front(dispenser) 
     myQueue.dequeue(dispenser) 
     if current == dest: 
      break 
     # loop over all neighbors of current 
     for neighbor in current.neighbors: 
      # process unvisited neighbors 
      if neighbor not in visited: 
       neighbor.previous = current 
       visited.add(neighbor) 
       myQueue.enqueue(neighbor, dispenser) 
    return constructPath(visited, source, dest) 

def constructPath(visited, source, dest): 

"""Returns the path as a list of nodes from source to destination""" 

    #construct the path using a stack and traversing from the destination 
    #node back to the source node using Node's previous 
    stack = myStack.Stack() 
    if dest in visited: 
     temp = dest 
     while tmp != source: 
      myStack.push(tmp, stack) 
      tmp = tmp.previous 
     myStack.push(source, stack) 

    path = [] 
    while not myStack.empty(stack): 
     path.append(myStack.top(stack)) 
     myStack.pop(stack) 
    return path 

Answer 1

stack = myStack.Stack() 
if dest in visited: 
    temp = dest 
    while tmp != source: 
     myStack.push(tmp, stack) 
     tmp = tmp.previous 

我觉得tmp和temp变量这里应该是一样的吗？虽然我会预期一个错误，因为tmp在使用之前未分配。