Почему DFS не проверяет дочерние элементы узла, который был выбран для разработки, на предмет состояния цели

Question

Извините, если моя грамматика далека от совершенства, английский не мой родной язык.

Если я правильно понимаю, DFS выполняет целевой тест для узла, только если он был выбран для разработки, а не во время его создания. Мне это кажется странным, потому что после того, как DFS выберет узел для разработки, он все равно добавит всех потомков узла в открытый список. при этом почему бы не проверить, является ли один из его дочерних элементов целевым состоянием, и если это так, DFS может вернуть решение и завершить работу? Продолжайте поиск в более глубоких слоях после генерации целевого состояния, которое кажется огромной тратой времени, я не прав?

большое спасибо!

Answer 1

Нет, вы не ошибаетесь, конечно, если вы найдете пункт назначения в соседних узлах текущего узла (дочерние элементы в ваших формулировках), вы можете прекратить его.

Однако я буду придерживаться "стандартной" реализации по двум причинам: (только мои личные проблемы)

1. Более простая реализация, более высокая читаемость. Например, вы можете захотеть что-то сделать, когда доберетесь до пункта назначения, тогда стандартным способом по сравнению с вашим способом псевдокод

//The way I like to implement
void dfs(int x){
  if(x is destination){
     do_something(); return;
  }
  mark x visited
  foreach x's unvisited neighbor{
      dfs(x's neighbor)
  }
}
          
//The way you suggest to implement
void dfs(int x){
  mark x visited
  foreach x's unvisited neighbor{
      if(x's neighbor is destination){
         do_something(); return;
      }
      dfs(x's neighbor)
  }
}

Я просто думаю, что, поскольку DFS основан на рекурсии, и, насколько я понимаю, поставить проверку базового случая на первое место функции, вынеся ее из цикла FOR, является более "рекурсивной" реализацией.

Также, если do_something() довольно сложная задача, код может стать грязным, если вы поместите проверку и обработку в цикл For (проблема читабельности).

2. Сложность по времени одинакова. Вы правы, что она может сохранить много уровней рекурсии, в зависимости от порядка поперечного узла.

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

   Поскольку временная сложность одинакова, поскольку каждый узел посещается не более одного раза, сложность составляет O(N+M), где N - количество узлов, а M - количество ребер.

   Так что не стоит рисковать написанием некоторых грязных кодов, чтобы сэкономить незначительное время, вообще говоря.