algorithm - 最短路径算法 - 具有不可访问单元格的矩阵

Question

我在一次采访中被问到这个问题。我不知道该怎么做。基本上我有一个布尔矩阵 - 其中 0 表示一个单元格不可访问。给定一个起点和一个目标单元格，我如何构造一条从起点到终点的最短路径，而不会跳过任何不可访问的单元格。您可以在所有四个方向旅行。

谢谢

Answer 1

一个简单的广度优先搜索就足以解决这个问题。这是 Python 中的示例实现。

输入.txt

4 4
1 1 4 4
1 1 0 0
0 1 0 0
0 1 1 0
0 0 1 1 

解决方案：

import sys
from collections import deque
sys.stdin = open ("Input.txt", "r")
Table   = []
Queue   = deque()
Visited = set()

n, m = [int (i) for i in sys.stdin.readline().split()]
startx, starty, endx, endy = [int(i)-1 for i in sys.stdin.readline().split()]
for j in xrange(n): Table.append ([int (i) for i in sys.stdin.readline().split()])

if Table[startx][starty] == 0:
    print 0
    sys.exit(0)

def process (X, Y, Dist):
    if (X == endx and Y == endy):
        print Dist + 1
        sys.exit(0)
    if X + 1 != m and Table[X + 1][Y] and (X + 1, Y) not in Visited:
        Queue.append ((X + 1, Y, Dist + 1))
    if Y + 1 != n and Table[X][Y + 1] and (X, Y + 1) not in Visited:
        Queue.append ((X, Y + 1, Dist + 1))
    if X - 1 != -1 and Table[X - 1][Y] and (X - 1, Y) not in Visited:
        Queue.append ((X - 1, Y, Dist + 1))
    if Y - 1 != -1 and Table[X][Y - 1] and (X, Y - 1) not in Visited:
        Queue.append ((X, Y - 1, Dist + 1))

Queue.append ((startx, starty, 0))
while (len(Queue)):
    CurrentX, CurrentY, Distance = Queue.popleft()
    if ((CurrentX, CurrentY) in Visited): continue
    Visited.add ((CurrentX, CurrentY))
    process (CurrentX, CurrentY, Distance)

Answer 2

您需要使用面包优先搜索。从这个矩形板上调制一个图形。

主要思想：

Distance to start cell = 0

Previous cell for start = some not existed cell

Add start cell to queue

Mark start cell as visited

While queue is not empty

     Take off cell Y from queue, if cell Y equal to finish cell, exit

     Check all possible moves from it (goes Up, Down, Left, Right, except "walls")

     For every possible cell adjancent from Y
            Check that possible cell X is not visited before
                 If Yes, mark X as visited and add to queue
                 Distance to cell X = distance to cell Y + 1
                 Previous cell in shortest path to cell X = Y

之后，您可以轻松地获得最短路径，从前一个数组中的完成单元格移动。

有关更多信息 - 检查维基百科 - https://en.wikipedia.org/wiki/Breadth-first_search

Answer 3

我会使用一个简单的洪水填充类型算法： -

create array of integers equal in size to boolean array => map
set all values in map to 0
set value at (start x, end x) to 1
found path = false
step = 1

while !found path
  for each cell in map where value == step
    for each valid adjacent cell
      if cell == end position
        map [cell] = step
        found path = true
        end search
      end if
      if map [adjacent cell] == 0
        map [adjacent cell] = step + 1
      end if
    end for
  end for
end while

number of steps between start cell and end cell inclusive == step

您可以使用堆栈和队列轻松提高效率。您需要检查没有可能路线的地图。