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

Question

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

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

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

Thanks

Answer 1

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

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

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

Answer 2

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

Answer 3

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

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

• ПСК

Пикс: S (стоимость 0), B (стоимость 1), А (стоимость 2), D (стоимость 3), C (стоимость 5), G (стоимость 7)

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

• Жадные:

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

выборка: S, A (H = 3), С (Н = 1), G (H = 0)

Ответ: S> А-> С- > G

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