Введение

В ряде приложений, имеется проблема определения оптимального пути. Это может быть нахождение самого быстрого пути в сети для определения самого безопасного пути для робота, блуждающего по поверхности Марса. В этом контексте, мы ограничим нашу область рассмотрения частным случаем нахождения путей в Евклидовом трехмерном пространстве. Даже больше, мы ограничим себя перемещениями по поверхностям, которые заданы двухмерной сеткой. Более конктерно, мы рассмотрим случай нахождения оптимального пути для транспортного средства, перемещающегося по поверхности нашей земли (1.2) как представляется в сегодняшних географических информационных (1.1) системах.

1.1