Единый поиск стоимости
При поиске по единообразной стоимости C сначала расширит D как самый дешевый или G, потому что это цель?
Обычно правило заключается в том, что поиск с одинаковой стоимостью расширяет самый дешевый узел, однако G является целью, а также в целом это будет самая низкая стоимость?
Не могли бы вы объяснить?
1 ответ
В этом случае вы нашли цель со стоимостью 4. Но представьте, что было бы преимущество со стоимостью 0,5 от D до G. Затем вам нужно будет продолжить поиск стоимости пути 3,5 из SACDG. Если вы остановитесь, как только найдете цель ниже C, вы получите неоптимальный результат решения.
Однако, если вы знаете, что минимальная стоимость ребра равна 1, вы можете остановиться, потому что лучший путь через D будет стоить 4, что равно значению пути SACG.
Главное здесь то, что вы не можете остановиться, пока не докажете, что каждый путь, который вы исследуете, будет по крайней мере таким же дорогим, как лучшее решение, найденное на данный момент.