![][1]

При поиске кратчайшего пути на графах большого размера плохо работает традиционная оценка стоимости т.к. данные заведомо не помещаются в памяти и общая стоимость больше зависит от числа обращений к диску нежели от числа просмотренных рёбер. А число дисковых операций — весьма субъективный фактор, зависимый от сложно формализуемой пригодности графа к хранению на диске в форме удобной для конкретного алгоритма. Кроме того, очень важным становится компактность — количество информации в расчете на ребро и вершину.

Под катом представлена обобщенная эвристика к алгоритму A\*, полезная именно в свете практической пригодности на больших графах при ограниченных ресурсах, например, на мобилке.
[Читать дальше →][2]

[1]: https://habrastorage.org/files/774/fa4/ae7/774fa4ae79404ae3990cfa3312b1c621.png
[2]: https://habrahabr.ru/post/326638/?utm_source=habrahabr&utm_medium=rss&utm_campaign=feed_posts#habracut