Реконструкция пути
Результат типичного поиска проиллюстрирован на рисунке 14. Круг обозначает адресат пути. Серые ячейки, те которые никогда не будут посещены в процессе поиска по алгоритму. Темно-серым обозначено препятствие.
Стрелки указывают на те грани которые характеризуют 'на данный момент лучший из всех известных' путей по всем исследованным ячейкам, то есть значения ed[v] для вершин указаны острием стрелок. Для удаленных ячеек (не маркированы) данный путь будет оптимален до этих ячеек. Более толстые темные стрелки указывают наиболее дешевый путь к адресату.
Рисунок 14 - маленькая часть дерева A* поиска
Если нас интересовало только нахождение стоимости минимального пути, тогда мы могли бы пропустить сохранение значений ed[v] ( и таким образом сохранили бы по байту с каждого узла). Теперь можно легко использовать указатели возврата ed[v] от вершины адресата для нахождения оптимального пути. Мы начинаем с ячейки адресата и затем идем в противоположном направлении по отношению к направлению грани, сохраненной в текущей ячейке, это продолжается до тех пор пока мы не достигаем исходной ячейки. С помощью данного перебора просто обратить последовательность ячеек, посещенных в течение трассировки указателей возврата, для того чтобы произвести уже 'нормальный' путь от источника до адресата.
7.2.4
Еще по теме Реконструкция пути:
- 3. Реконструкция промышленных объектов
- 3.6. Алгебраические методы реконструкции
- 1. Анализ условий и причины реконструкции объектов
- § 1. Характер реконструкции и ее цели
- § 2. Степень достоверности реконструкций
- 2. Реконструкция жилых и общественных зданий
- 1. От реконструкции к реставрации
- 3.4. Двумерная реконструкция Фурье
- 3.7. Итерационные методы реконструкции
- а) Реконструкция фонетических черт
- Особенности выполнения работ при реконструкции промышленного здания
- Статья 88. Порядок предоставления жилого помещения в связи с проведением капитального ремонта или реконструкции дома
- IV редакция. 1836-1838 (реконструкция)
- Основания для датировки и реконструкции
- б) Реконструкция морфологических и синтаксических черт
- Реконструкция Юга (1865–1877)
- 4. Реконструкция индивидуального жилого помещения своими силами или с привлечением подрядной строительной организации
- 4.2. Основные технико-экономические результаты строительства (реконструкции) малых ГЭС
- Основания, порядок, условия и размер субсидий, предоставляемых гражданам на строительство (реконструкцию) или приобретение жилых помещений
- § 1. Предоставление жилого помещения на время капитального ремонта или реконструкции дома