Дополнительная информация, необходимая для количества узлов, созданных с помощью Breadth First Search

Question

Я новичок в AI и проходил через книгу Питера Норвига. Я уже рассмотрел этот вопрос: What is the number of nodes generated by breadth-first search?. В нем говорится, что если мы применяем тест цели для каждого узла, когда он выбран для расширения, то у нас есть узлы = 1 + b + b^2 + b^3 + ... + b^d + (b^(d + 1) - b) Но что, если мое состояние цели является листовым узлом на последней глубине. Таким образом, после цели нет никакой глубины. Тогда как оценить b^(d + 1) ?. например: в дереве с максимальной глубиной 3, если моя цель лежит на глубине 3, то как бы я оценил b^(3 + 1), когда вообще нет 4-го уровня ?. Пожалуйста, очистите мои сомнения. Заранее спасибо!

Answer 1

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

Сгенерировано означает, что не все эти узлы протестированы, чтобы определить, являются ли они целью; они просто генерируются и сохраняются, чтобы в конечном итоге их можно было сравнить с целью, если цель еще не найдена.

Худший случай имеет два важных значения. Попытайтесь визуализировать первый поиск по ширине, затем вниз на один уровень, затем снова налево, затем вниз и т. Д. В худшем случае мы предполагаем, что на любом уровне глубины d цель игры: Цель - это самый последний (самый правый) узел. Это означает, что все узлы слева от него сравниваются с целевым узлом, а также любые его потомки/дочерние элементы.

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

Действительно, для вашего случая, что уравнение не совсем правильно, но это просто потому, что вы не имеете худшего случая. В вашем случае поисковый процесс действительно не должен генерировать последние (b^(d + 1) - b) узлов уравнения.

Заключительное примечание по терминологии вы использовали: вы спросили, как б^(d + 1) (например, Ь^(3 + 1) могут быть оценены, если нет уровня глубины ниже г = 3. Математически оценить этот термин по-прежнему нет. Даже в вашем случае нет уровня глубины 4, мы все еще можем математически оценить термин b^(3 + 1). В вашем случае это не сделало бы чтобы сделать это, потому что это неверно, но мы все равно можем оценить этот термин просто отлично.