Каково различие между Жадным Поиском и Однородным Поиском Стоимости?
Ища в дереве, мое понимание однородного поиска стоимости - то, что для данного узла A, имея детские узлы B, C, D со связанными затратами (10, 5, 7), мой алгоритм выберет C, поскольку у этого есть более низкая цена. После расширения C, я вижу узлы E, F, G с затратами (40, 50, 60). Это выберет 40, поскольку у этого есть минимальное значение от оба 3.
Теперь, это не все равно как выполнение Жадного Поиска, где Вы всегда выбираете то, что, кажется, лучшее действие?
Кроме того, определяя затраты от движения от определенных узлов до других, мы должны рассмотреть целую стоимость с начала дерева к текущему узлу или просто саму стоимость от движения от узла n к узлу n'?
Спасибо
2 ответа
Нет. Ваше понимание не совсем верно.
Следующим узлом, который необходимо посетить в случае равномерного поиска, будет D, так как это имеет самую низкую общую стоимость от корня (7, в отличие от 40+5=45).
Жадный поиск не возвращается обратно вверх по дереву - он выбирает наименьшее значение и фиксирует его. Uniform-Cost выберет наименьшее суммарное значение из всего дерева.
В единообразной стоимости вы всегда рассматриваете все неслышенные узлы, которые вы видели до сих пор, а не только те, которые подключены к узлу, на котором вы смотрели. Таким образом, в вашем примере, после выбора C, вы обнаружите, что посещение G имеет общую стоимость 40 + 5 = 45, что выше, чем стоимость начать снова от корня и посещения D, что имеет стоимость 7. Итак, вы посетите D Дальше.