Другие методы

Разные люди пробовали несколько подходов более математического характера. Например, [KIMM95] использует двумерную функцию, чтобы проследить эволюцию 'равно расположенных кривых' на поверхности, и из этого получить схему, нахождения самых коротких путей на многих поверхностях.

Другая идея состоит в том, чтобы определить некоторый сорт 'поверхности стоимости ' и следовать за локальным направлением градиента, то есть 'самого метод крутого спуска'. Однако, хотя основная идея абсолютна проста, обрабатать случай локального минимума - не так просто. Рассмотрим например реку, которая естественно течет в направлении отрицательного градиента высоты местности. В природе, это создает озера и водоемы вокруг локального минимума. Методы для обнаружения и обработки таких частных случаев могли бы возможно быть разработаны и использоваться в практическом поиске пути, но далее не описаны в этой статье.

Различные эвристические подходы также были предложены. См. например crash-and-turn алгоритм [LONN96, перевод ANIS98]. Практически эти методы сами по себе ведут себя далеко не оптимально на не очень простой местности, имеющие склоность иметь ситуации 'блокирования', и нельзя часто гарантировать, что путь будет найден вообще! Однако, эвристика может быть очень хорошей идеей для ускорения более 'исчерпывающих' методов типа тех в 2.1 и 2.2; особенно, если требование полной гарантии оптимальности может быть опущенно.

4