Искусственный интеллект Поиск с равномерной стоимостью

Question

У меня есть несколько вопросов о функциях поиска в искусственном интеллекте, которые я не могу понять.Я знаю, что поиск с равномерной стоимостью является частным случаем алгоритма поиска A *, если его эвристика является постоянной функцией.Также я знаю, что поиск в ширину (BFS) - это особый случай A *, когда все граничные затраты положительны и идентичны.Поиск по принципу «лучший в первую очередь» также является частным случаем поиска A *.Но как я могу это показать?Как я могу доказать, что все вышеперечисленное верно?

Answer 1

Хм, я не знаю, как это выразить элегантно, но все, что вы сказали, верно по ... определению!

В A * у вас есть эвристическая функция, и вы жадно исследуете свое дерево, выбирая наиболее перспективные ветви.

Если стоимость для каждого ребра одинакова, то A * начинается только с узлов, которые находятся на «расстоянии 1», поскольку все они имеют наименьшую стоимость: 1. Затем A * исследует узлы на «расстоянии 2» от корневой узел, поскольку их стоимость теперь является наименьшей из всех возможных узлов: 2. Рекурсивно это приводит к BFS.

Это идентично для равномерной стоимости. Для поиска Best-First это немного отличается, A * - это особый случай поиска Best-first, а не наоборот =).