пространственно-временные сложности первого поиска

Question

Я не понимаю, как возникают следующие сложности.

особенно b (b ^ d-1) во временной сложности

Сложность времени: Всего онемение. сгенерированных узлов: 1 + b + b2 +… + bd + b (b ^ d-1) = O (b ^ (d + 1)) Сложность пространства: O (b ^ (d + 1))

где б - максимальный коэффициент ветвления дерева поиска d - глубина наименее затратного решения

Answer 1

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

Следовательно: O (b ^ d)

(я не уверен, откуда вы взяли +1 отОднако ...)

Answer 2

Проще говоря, в BFS мы используем очередь для отслеживания пути посещения.Каждая вершина графа посещается не более одного раза.Следовательно, размер очереди максимальный V.Отсюда сложность пространства, если функция числа вершин в графе, т. Е. O (| V |).Что касается сложности времени, мы запускаем цикл, чтобы пройти по всем вершинам графа.Это O (| V |).Также для каждой найденной вершины нам нужно проверить всех ее соседей и, следовательно, количество ребер, с которыми она связана.Это дает нам O (| E |).Таким образом, сложность может быть объяснена обозначением O (| V | + | E |).

Answer 3

Если бы алгоритм применял целевой тест к узлам при выборе для расширения, а не при генерации, весь слой узлов на глубине d был бы расширен до того, как цель была обнаружена, и временная сложность составила бы O (b ^ (г + 1)).