В чем разница между Greedy-Search и Uniform-Cost-Search?

При поиске в дереве мое понимание равномерного поиска стоимости заключается в том, что для данного node A, имеющего дочерние узлы B, C, D с соответствующими затратами (10, 5, 7), мой алгоритм выберет C, так как он имеет меньшую стоимость. После расширения C я вижу узлы E, F, G с затратами (40, 50, 60). Он выберет 40, так как он имеет минимальное значение от обоих.

Теперь, разве это не то же самое, что делать Greedy-Search, где вы всегда выбираете то, что кажется лучшим действием?

Кроме того, при определении затрат при переходе от определенных узлов к другим мы должны рассматривать всю стоимость с начала дерева до текущего node или просто для самой стоимости от перехода от node n до node n '?

Спасибо

Ответ 1

Неа. Ваше понимание не совсем правильно.

Следующий node, который будет посещаться в случае равномерного поиска стоимости, будет D, поскольку у него самая низкая общая стоимость от корня (7, а не 40 + 5 = 45).

Жадный поиск не возвращается к дереву - он выбирает самое низкое значение и фиксирует это. Uniform-Cost выберет самую низкую общую стоимость всего дерева.

Ответ 2

В обычном поиске затрат вы всегда рассматриваете все невидимые узлы, которые вы видели до сих пор, а не только те, которые связаны с node, на которые вы смотрели. Итак, в вашем примере, после выбора C, вы обнаружите, что посещение G имеет общую стоимость 40 + 5 = 45, что выше, чем стоимость начала снова от корня и посещения D, стоимость которого 7. Таким образом, вы посетили бы D следующий.

Ответ 3

Разница между ними заключается в том, что Greedy выбирает node с наименьшим эвристическим значением, а UCS выбирает node с наименьшей стоимостью действия. Сопоставьте следующий график:

Если вы запустите оба алгоритма, вы получите:

Выбор: S (стоимость 0), B (стоимость 1), A (стоимость 2), D (стоимость 3), C (стоимость 5), G (стоимость 7)

Ответ: S- > A- > D- > G

Жадность:

*, предполагая, что он выбирает A вместо B; A и B имеют такое же эвристическое значение

Выборы: S, A (h = 3), C (h = 1), G (h = 0)

Ответ: S- > A- > C- > G

Таким образом, важно различать стоимость действия, чтобы получить значение node по эвристическому значению, которое представляет собой информацию, которая добавляется к node, основываясь на моем опыте проблемы.