Уход от направленного смещения
При простой реализации A* производит один, из возможного большого числа оптимальных путей. Однако, это не всегда может быть один наиболее визуально приятный путь. Его можно получить при помощи уклона (предпочтения), меняя порядок, при котором соседи равной стоимости, удаляются из приоритетной очереди.
При этом могут получаться визуально более приятные пути в областях, где однородные стоимости граней. См. рисунок 15. Точно какие направления предпочтены и в том, какой порядок является конечно высоко зависимым от реализации.
Наклоный путь Рандомизированный путь Визуально приятный путь
Рисунок 15 - Три одинаковых по стоимости пути в графе с однородными издержками края
Наиболее интуитивный способ, чтобы избежать уклонения, казалось бы в том, что бы регулярно, или даже беспорядочно, переставлять порядок, при котором расширения поиска пути к соседним ячейкам исследованы. Однако, в практических тестах, это не производит удовлетворительные уточнения. Вероятное объяснение - то, что эта схема только вводит новый порядок предпочтений, которые являются статическим относительно графа. Как альтернативу, введем случайный элемент. С вероятностью 0.5, примем новый путь, которые не уточнил бы текущий самый лучший путь, но не ухудшил его (то есть новые пути по стоимости равняются текущей самой лучшей стоимости). Это дает удовлетворительный результат (если не совершенный) как отмечено на примере на рисунке 15. Число 0.5 было выбрано, потому что вероятность наличия двух в равной степени хороших расширений данного пути на реальной карте - (эвристически, если Вы будете) намного больше, чем наличия трех или более. Таким образом, когда мы приходим в точку, где мы должны выбрать между двумя в равной степени хорошими путями, мы можем использовать подбрасывание монеты, игнорируя возможность третьего равного пути стоимости и все еще ожидать результат без значительного уклона. 7.2.5