Я не понимаю, как возникают следующие сложности.временные и пространственные сложности ширины первого поиска
espeacialy б (б^д-1) во временной сложности
Сложность Время: Общее онемение. из созданных узлов: 1 + b + b2 + ... + bd + b (b^d-1) = O (b^(d + 1)) Сложность объекта: O (b^(d + 1))
, где б - максимальный коэффициент ветвления дерева поиска D - глубина раствора наименьшей стоимостью
в корне, вы расшириться b узлы в следующих элементов в дереве поиска. Это, если ни одно из них не является решением, в свою очередь, расширяет b узлов от каждого. Это продолжается до тех пор, пока не будет найдено решение, которое будет на глубине d.
Следовательно: O (Ь^d)
(я не знаю, где вы получили +1 от, однако ...)
- эта сложность как для пространства, так и для времени? –
Да. Каждый узел должен быть как обычным (время), так и сохраненным (пробелом) до тех пор, пока не будет найдено решение. – Paul
также эта сложность зависит от структуры данных im, использующей ??? –
Если алгоритм был применить тест цели к узлам при выборе для расширения, а не при генерации, весь слой узлов на глубине d будет расширен до того, как цель будет обнаружена, а временная сложность будет равна O (b^(d + 1)).
В более простых терминах в BFS мы используем очередь для сохранения тракта посещаемого пути. Каждая вершина на графике посещается не более одного раза. Следовательно, размер очереди максимальный V. Следовательно, пространственная сложность, если функция числа вершин в графе iee O (| V |). Что касается временной сложности, мы запускаем цикл, чтобы перебирать все вершины в графе. Это O (| V |). Также для каждой найденной вершины нам нужно проверить все его соседи и, следовательно, число ребер, к которым оно связано. Это дает O (| E |). Таким образом, сложность может быть объяснена обозначением O (| V | + | E |).
Где вы получили формулы? –
На самом деле наш доктор просто дал его нам в lec –