Жадный лучший первый поиск и первый глубокий поиск

Question

Может ли Greedy Best First Search вести себя как Depth First Search в любом случае?

Я вижу, что наихудший случай обоих этих алгоритмов похож на O (b ^ m).Значит ли это, что они ведут себя одинаково?

Answer 1

«Лучший сначала» просто означает, что он полностью полагается на некоторую эвристическую , которая оценивает возможные варианты и расширяет сначала лучшие варианты.Поиск по глубине не использует такой эвристики.

Один из способов думать об этом - это то, что Джикста вернет кратчайший путь на графе с неотрицательными ребрами.Когда вы добавляете в скоринговый механизм поиска в первую очередь, вы получаете A *.Забери Джикстра, ты снова вернешься лучше всех.

Answer 2

Возможно ли, что Greedy Best First Search ведет себя как поиск в глубину в любом случае?

Нет.Если это так, то будет Поиск в глубину.

Я вижу, что наихудший случай обоих этих алгоритмов похож на O (b ^ m).Значит ли это, что они ведут себя одинаково?

Нет.