Наименьшее расстояние в лабиринте с использованием поиска в глубину - PullRequest
Новая
       40

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

0 голосов
/ 13 декабря 2018

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

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

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

Пример: 

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

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

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

Я пишу на 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

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

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

Ответы [ 2 ]

0 голосов
/ 13 декабря 2018

Проблема с вашей логикой в ​​том, что вы помечаете узел как непосещенный, увеличивая ненужный поиск, Вы уверены, что, если кратчайшая ванна между точкой A и Dest не может быть длиннее, чем кратчайший путь между B и Destпроходя через 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
0 голосов
/ 13 декабря 2018

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

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

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