Обратная трассировка для нахождения пути
Как только конечный пункт маршрута окажется в открытом списке, необходимо будет составить путь обратно к исходной точке. Для этого мы берем родителя открытого узла в котором расположен конечный пункт. Затем берем родителя родителя и так далее до тех пор, пока не вернемся к исходной позиции. В результате вы получите путь от конечного пункта до начального. Теперь вам достаточно инвертировать полученный путь, чтобы получить маршрут от исходной точки до цели. На рис. 12.10 показан путь, сформированный алгоритмом для рассматриваемого примера.
Рис. 12.10. Найденный путь
На рисунке вы можете заметить, что в сформированный путь попали несколько лишних узлов. Это вызвано тем, что несколько узлов имеют одинаковую общую стоимость. Вы не можете выбрать сразу два узла, и просто берется тот узел, который находится в списке первым. Это может привести к увеличению объема работы, но в конце путь будет скорректирован.
| netlib.narod.ru | < Назад | Оглавление | Далее > |
