Кратчайшее расстояние в лабиринте с использованием поиска в глубину

Дана матрица MxN, где каждый элемент может быть "o", "s" или "g" ("s" и "g" уникальны. Только одна начальная точка и одна конечная точка).

Предположим, что начальная ячейка 's' всегда равна (0,0).

Мы хотим найти кратчайшее расстояние между начальной ячейкой «s» и целевой ячейкой «g», избегая при этом препятствия «o».

Пример:

['s', ' ', ' ', ' ', ' ']
[' ', ' ', 'o', 'o', 'o']
['o', ' ', 'o', ' ', ' ']
[' ', ' ', ' ', 'o', ' ']
[' ', ' ', ' ', 'g', ' ']

Кратчайшее расстояние от «s» до «g» равно 7.

Я понимаю, что мы можем легко решить эту проблему, используя поиск в ширину или алгоритм блокировки. Однако мне было трудно понять, почему мой поиск в глубину не работает.

Я пишу на Python, и мой код выглядит следующим образом.

class Solution:
   :type maze: list of list
   :type start: tuple
   :type end: tuple
   :rtype: int
   def findShortestDistance(self, maze, start, end):
      self.shortest=math.inf

      #set the default value of visited to be False
      self.visited=defaultdict(lambda: False)

      self.maze=maze
      self.rows=len(maze)
      self.cols=len(maze[0])
      self.depthFirstSearch(0,0,0)
      return self.shortest

   def depthFirstSearch(self, i, j, numStep):
      if i<0 or j<0 or i>=self.rows or j>=self.cols:
         return
      elif self.maze[i][j]=='o':
         return
      elif self.maze[i][j]=='g':
         self.shortest=min(self.shortest,numStep)
         return
      elif self.visited[(i,j)]:
         return

      self.visited[(i,j)]=True

      self.depthFirstSearch(i-1,j,numStep+1)
      self.depthFirstSearch(i,j-1,numStep+1)
      self.depthFirstSearch(i,j+1,numStep+1)
      self.depthFirstSearch(i+1,j,numStep+1)

      self.visited[(i,j)]=False

Я искренне не понимаю, почему это не сработает, но я не смог пройти несколько скрытых тестовых случаев для вопроса.

Кроме того, может ли кто-нибудь сказать время выполнения этого алгоритма? Мне кажется, что экспоненциальный.


algorithm breadth-first-search depth-first-search
person fzy1995    schedule 12.12.2018    source источник

Ответы (2)


arrow_upward
0
arrow_downward

Что ж, DFS не лучшая идея, потому что вы будете постоянно пересматривать одни и те же подпути, а также потому, что вам придется исследовать ВСЕ возможные пути, чтобы найти самый короткий. Вообще говоря, когда у вас есть рекурсивная проблема с дублированием выполняемой работы, вам следует подумать о динамическом программировании. Однако в этом конкретном случае вы можете использовать DFS, что на самом деле очень похоже на то, что вы делаете со стандартным решением DP для этой проблемы.

Теперь несколько замечаний о вашей реализации:

  • избегайте мутаций вообще, и особенно в функциональных алгоритмах. Немного странно иметь рекурсивную функцию с побочными эффектами, а не с возвращаемым значением, хотя, возможно, это помогает уменьшить размер стека.
  • Мне довольно сложно вычислить сложность. Это в основном равно количеству допустимых путей любой длины, так что это довольно много, особенно когда есть несколько препятствий, потому что есть много путей длиной, примерно равной n*m.
  • Я не могу найти проблему в самой вашей логике. Вы уверены, что время просто не истекло из-за неудачных тестов?
person Dici    schedule 12.12.2018
comment
Я понимаю. Да, это имеет смысл. Я подозреваю, что это может быть просто тайм-аут при большом вводе тестов из-за высокой сложности. - person fzy1995; 13.12.2018

arrow_upward
0
arrow_downward

Проблема с вашей логикой заключается в том, что вы помечаете узел как непосещенный, что увеличивает ненужный поиск, Конечно, если кратчайшая ванна между точкой A и пунктом назначения не может быть длиннее, чем кратчайший путь между пунктом B и пунктом назначения, проходящий через A

Используйте следующее

class Solution:
   def findShortestDistance(self, maze, start, end):
        self.shortest=math.inf

        #set the default value of visited to be False
        self.visited=defaultdict(lambda: False)

        self.maze=maze
        self.rows=len(maze)
        self.cols=len(maze[0])
        self.depthFirstSearch(0,0,0)
        return self.shortest

   def depthFirstSearch(self, i, j, numStep):
        if i<0 or j<0 or i>=self.rows or j>=self.cols:
            return
        elif self.maze[i][j]=='o':
            return
        elif self.maze[i][j]=='g':
            self.shortest=min(self.shortest,numStep)
            return
        elif self.visited[(i,j)]:
            return

        self.visited[(i,j)] = True
        print("{} {}".format(i,j))
        self.depthFirstSearch(i-1,j,numStep+1)
        self.depthFirstSearch(i,j-1,numStep+1)
        self.depthFirstSearch(i,j+1,numStep+1)
        self.depthFirstSearch(i+1,j,numStep+1)

        return
person tooTired    schedule 13.12.2018
comment
Не совсем. Рассмотрим это `[' s ', ' ', ' '] [' o ', ' o ', ' '] [' g ', ' ', ' '] ` Поскольку конечная точка может быть где угодно, а препятствия могут быть где угодно, нам нужно будет повернуть быть в состоянии идти налево, или идти выше. - person fzy1995; 13.12.2018
comment
@ fzy1995 Спасибо за разъяснение этого момента, теперь я лучше понял проблему и изменил, чтобы добавить обход вверх и влево, но пометка узла как непосещенного приводит к бесконечному циклу поиска. Уверен, что если кратчайшая ванна между точкой А и Dest не может быть длиннее кратчайшего пути между B и Dest, проходящего через A. - person tooTired; 13.12.2018
comment
Я не согласен с вашей сложностью. Некоторые пути могут иметь длину в O(M*N), а путей бесчисленное множество (сейчас я не могу найти формулу для их подсчета), поэтому она должна быть намного больше, чем O(N*M). Я также не вижу, в каких ситуациях код OP приведет к бесконечному циклу. Каждый рекурсивный вызов должен останавливаться в какой-то момент, потому что существует конечное число допустимых позиций. Поскольку количество допустимых позиций строго уменьшается сразу после каждого рекурсивного вызова и что условие окончания определено для случая, когда больше нет допустимых ходов, можно с уверенностью сказать, что он всегда будет заканчиваться. - person Dici; 13.12.2018
comment
@Dici Спасибо за очень хорошее объяснение. - person tooTired; 14.12.2018
comment
Нп, но не верьте мне на слово! Если вы найдете пример, для которого он бесконечно зацикливается, мне было бы интересно это увидеть. - person Dici; 14.12.2018