Какова наихудшая временная и пространственная сложность алгоритма поиска с равномерной стоимостью?

Question

Моя книга здесь (Искусственный интеллект, современный подход) говорит, что наихудшая временная и пространственная сложность алгоритма поиска с равномерной стоимостью будет O (b [C * / e]), где b - коэффициент ветвления, C * - стоимость оптимального решения, и каждое действие стоит по крайней мере e. Но почему это так?

Answer 1

Во-первых, сложность O(B^(C/e)) [экспоненциальный в C/e ].

Чтобы понять это, сначала подумайте о простом примере:

Позволять G=(V,E) быть графом с коэффициентом ветвления B, График невзвешенный (w(e) = 1 для каждого e).

Попробуйте найти кратчайший путь от S до T.
В этом случае алгоритм фактически является BFS, и он обнаружит все узлы на пути до длины SOL, где SOL длина кратчайшего пути, который O(B^|SOL|)

Для общего случая - та же идея верна, вам нужно найти все узлы с указанием стоимости C, Таким образом, вы обнаруживаете узлы до глубины C/e, давая вам O(B^(C/e)) общее количество узлов необходимо изучить.

Экспоненциальный фактор объясняется тем, что: Первый уровень (корень) имеет B^0=1 узлы, второй уровень имеет B узлов. от каждого из них вы обнаружите B узлы, давая вам B^2....

---

РЕДАКТИРОВАТЬ:
Пропустил это до сих пор, но название требует сложности пространства, а не сложности времени. Тем не менее, ответ остается тем же, так как поиск с равномерной стоимостью содержит visited установить для уже посещенных узлов. Поскольку каждый узел, который вы обнаруживаете, также добавляется к нему - ответ остается O(B^(C/e))

Answer 2

C*/e означает среднее количество узлов, которые следует посетить во время поиска, и для посещения каждого из этих узлов вы должны посмотреть на все возможные b ветви (по крайней мере корневые узлы), поэтому вы должны проверить узел b^{[C * / e]} в своем поиске. Это сложность вашего времени поиска, если предположить, что процесс на каждом узле занимает O (1).

_{PS: в худшем случае это Ω (b^{[C * / e]})}