Поиск единой стоимости

Question

Для поиска с равномерной стоимостью, C расширит ли сначала D, как самый дешевый, или G, потому что цель?

Обычно правило состоит в том, что поиск с равномерной стоимостью расширяет самый дешевый узел, однако G цель, а также в целом это будет самая низкая стоимость?

Не могли бы вы объяснить?

Answer 1

В этом случае вы нашли цель со стоимостью 4. Но представьте, что существует ребро со стоимостью 0,5 от D до G. Тогда вам нужно будет продолжить поиск пути стоимостью 3,5 от SA- C -DG. Если вы остановитесь, как только найдете цель ниже C, вы получите неоптимальный результат решения.

Однако, если вы знаете, что минимальная крайняя стоимость равна 1, вы можете остановиться, потому что лучший путь через D будет стоить 4, что совпадает с путем SA- C -G.

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