广度优先搜索比预期结果差一个索引

Question

我正在尝试在 Python 中实现面包优先搜索算法，以找到从矩阵（二维列表）左上角到数字 9 的最短路径，无论它可能落在哪个位置矩阵。出于某种原因，当我运行下面的代码和包含的打印语句时，我的 x 坐标将正确输出（达到索引 5 而不是期望的 5）。然而，我的 y 坐标仍然是一个索引短（例如需要 7，它停在 6）。此外，当我打印队列时，它不是空的，但由于某种原因该功能仍然结束。所以，我不明白为什么如果两个条件都不满足（即队列为空或我们想要的坐标已找到），代码会退出。

import numpy as np
from collections import deque


def shortest_path(maze):
    num_rows = len(maze)
    num_cols = len(maze[0])

row_moves = [1, -1, 0, 0]
col_moves = [0, 0, 1, -1]

# Convert maze to an array and use numpy to find coordinates of our goal, which is the 9.
maze_to_matrix = np.array(maze)
destination = np.where(maze_to_matrix == 9)
destination_x, destination_y = destination[1][0], destination[0][0]

def is_valid_move(matrix, visited, y, x):
    return (y >= 0) and (y < num_rows) and (x >= 0) and (x < num_cols) \
           and matrix[y][x] == 1 and not visited[y][x]


def bfs(matrix, dest_y, dest_x):

    # Construct matrix to keep track of visited cells.
    visited = [[False for x in range(num_cols)] for y in range(num_rows)]

    # Mark our origin as visited.
    # Our origin is always the top left node.
    visited[0][0] = True

    # Create an empty queue to keep track of our nodes to visit.
    queue = deque()

    # Append our starting coordinates and its minimum distance from the source to our queue.
    # First number is y coordinate, or outer list index.
    # Second number is x coordinate, or inner list index.
    queue.append((0, 0, 0))

    # Store the length of the longest path from source to destination
    min_dist = float('inf')

    # Pull most recently visited node off queue and determine if neighbouring
    # nodes are accessible. Continue until no valid unvisited nodes remain.
    while queue:
        (y, x, dist) = queue.popleft()
        print(f'y: {y} and dest_y: {dest_y}')
        print(f'x: {x} and dest_x: {dest_x}')

        # If our destination is found then break the loop and return value.
        if y == dest_y and x == dest_x:
            min_dist = dist
            break

        # Check for all possible movement directions from current (x, y)
        # and add valid movements to our queue.
        for i in range(4):
            if is_valid_move(matrix, visited, y + row_moves[i], x + col_moves[i]):
                visited[y + row_moves[i]][x + col_moves[i]] = True
                queue.append((y + row_moves[i], x + col_moves[i], dist + 1))
                print(queue)

    if min_dist != float('inf'):
        return min_dist
    else:
        return "Desired destination can't be reached from given origin points."

return bfs(maze, destination_y, destination_x)


maze = [
    [1, 0, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 0, 1, 0],
    [0, 1, 0, 1, 0, 1, 0],
    [1, 1, 0, 1, 1, 1, 0],
    [1, 0, 0, 0, 0, 1, 0],
    [1, 1, 1, 1, 0, 1, 0],
    [0, 0, 0, 1, 0, 1, 0],
    [0, 0, 0, 0, 1, 9, 0]
]

print(shortest_path(maze))

# Outputting y: 6 and dest_y: 7 x: 5 and dest_x: 5 and the queue is full.

Answer 1

没关系，我是个白痴...在我的 is_valid_move 函数中，我只计算矩阵中值为 1 的空格，这意味着我们的目标 9 永远不会有效。

所以 is_valid_function 应该是这样的：

return (y >= 0) and (y < num_rows) and (x >= 0) and (x < num_cols) \
           and (matrix[y][x] == 1 or matrix[y][x] == 9) and not visited[y][x]

广度优先搜索比预期结果差一个索引

Breadth First Search falling one index short of desired outcome

python

breadth-first-search

python-3.x