Итерация алгоритма UCS
Я пытался реализовать UCS и подумал, что для этого будет лучше, если я сначала нарисую от руки, как она работает, а не просматриваю код. у меня есть график
Я попытался реализовать UCS (поиск единой стоимости) на приведенном выше графике. Но я запутался в том состоянии, когда у меня есть
Открытые узлы как: (V2,9),(V5,9),(V5,10),(V2,12),(V6,13)
закрытые узлы как: (V1,0),(V3,4),(V4,5),(V2,6)
Нужно ли включать (V2,9) в открытые узлы, поскольку (V2,6) уже есть в закрытых узлах?
Я пробовал искать разные статьи на эту тему, и каждая давала разные ответы. Некоторые говорят, что включают, а другие говорят, что нет.
1 ответ
Это зависит от того, как реализована ваша очередь приоритетов. В основном есть два варианта:
(1) Узел не может присутствовать в очереди более одного раза. Если при посещении узла вы найдете более короткий путь к соседнему узлу, который уже находится в очереди, вы обновите его приоритет на основе вновь найденного пути (если он короче).
В этом случае запись очереди (V2,9) уже заменена на (V2,6) после посещения узла V3. (V2,12) никогда не будет добавлен в очередь, так как V2 уже присутствует в очереди с более высоким приоритетом при посещении V4.
(2) Вы не обеспечиваете уникальность узлов в очереди. При получении записи из очереди вы проверяете, был ли уже посещен узел (= он находится в том, что вы называете закрытыми узлами), и в таком случае пропускаете его.
В этом случае очередь содержит записи (V2,9),(V5,9),(V5,10),(V2,12),(V6,13) (как вы указали в своем вопросе). Вы пропускаете V2, поскольку он уже был посещен, и посещаете V5.
В любом случае узел никогда не добавляется в очередь после его посещения, иначе алгоритм не остановился бы.