Поиск оптимального пути

Исключение избыточных путей

Расширение всех путей, ведущих к одной и той же вершине, снижает эффективность алгоритма. Для исключения избыточности можно использовать принцип динамического программирования:

Лучший путь, проходящий через некоторую промежуточную точку, состоит из лучшего пути от начала до этой точки и лучшего пути из этой точки к цели.

В алгоритм вводится правило: удаляются все пути, приводящие в одну и ту же точку кроме пути, имеющего минимальную оценку (после расширения, перед сортировкой).

Применение недооценок для увеличения эффективности поиска.

Поиск оптимального пути будет более эффективным, если будем основываться не только на оценке пройденного пути, но и на оценке оставшегося.

Если величина оценки окажется больше реальной длины пути, то процесс поиска пойдет неправильно. Чтобы избежать данной ситуации необходимо, чтобы оценка всегда была меньше, чем реальная длина пути. Для этого вводим недооценку.

Алгоритм А*

1. создать одноэлементную очередь, включающую путь нулевой длины.

2. пока головной путь в очереди не оканчивается целью и пока очередь не пуста повторять:

• удалить головной путь из очереди

• создать новые пути, расширяя его

• удалить из новых путей все циклические

• добавить новые пути в произвольное место очереди

• исключить все пути, приводящие в точку, кроме одного с минимальной оценкой

• отсортировать очередь согласно оценке пути, состоящей из суммы пройденного пути и недооценки оставшегося, так, чтобы наиболее дешевые оказались в голове.

3. если полный путь найден, показать его, иначе сообщить о неудаче.