Comments 23
что-то мне подсказывает что вы изобрели градиентный спуск. )
Эх молодежь :)
Алгоритм Ли Вам в помощь.
Превращаем вашу поверхность во взвешенный граф и запускаем на нем алгоритм Дейкстры. Это даст оптимальный маршрут.
Можно попробовать расширить алгоритм Ли или алгоритм А* на случай взвешенного графа, но не знаю что получится. Возможно - что-то интересное.
Да тут вообще не понятно, какие цели у автора. Если исходить из того, что ему надо найти путь до правой границы, и это должен быть локальный алгоритм (подыграем по максимому и предположим так надо). Ну посчитай ты локальный гессиан, найди локальный кратчайший путь до правой границы(наверное можно даже аналитически), будет хотя бы красиво, а не вот это уперся в стенку - повернул. Да и совсем тривиальный алгоритм должен взлететь, считаем градиент, проекция вектора направления на него является оптимальной линейной аппроксимацией локального поведения функции, считаем проекцию для точек кандидатов, выбираем минимум.
PS: совсем хорошая идея, локально находить при помощи МНК наилучшую плоскость, и выбирать на ней минимальный путь до правого края. На таком даже можно наверное диплом сделать, если расписать все это в виде научно-математической лабуды. )
Вот вот я тоже подумал - A* в студию и все будет быстро. В добавок - в A* и djskra можно вообще выбрасывать непроходимые сегменты (например если угол склона больше 35-40 градусов) и оно ещё быстрее все это обсчитает.
По факту описанный в статье алгоритм - это и есть А* :)
Пришла в голову такая мысль.
А что если мы скрестим JPEG с вариационным исчислением?
Шаг 1. JPEG использует дискретное косинусное преобразование (DCT) для вычисления аналитической аппроксимации g(x,y) дискретной функции f(x,y), где значения обоих функций -- это яркость пикселя. Иначе говоря из матрицы пикселей f получаем функцию g из суммы косинусов. Большую часть этих косинусов можно выкинуть за ненадобностью. Хорошая новость в том, что в DCT косинусы не считаются для каждой точки сетки -- только для строк и столбцов (O(2N) вместо O(N^2)).
Шаг 2. Зная аналитически заданную поверхность g(x,y), можно аналитически посчитать кратчайший путь методом вариационного исчисления. Иначе говоря -- найти геодезическую линию на поверхности.
Интересно, что первый шаг -- это просто матричное умножение. Второй шаг чуть сложнее. Для простых кейсов -- это может и пушкой по воробьям, но предположу, что на огромных сетках, где есть плавные перепады высот, это может дать выигрыш. Пусть и ценою некоторой потерей точности. Бонусом также можно накладывать аналитические ограничения.
Это скорее мысли в слух, на случай если вам вдруг интересно станет в этом направлении покопать.
Что-то напоминает, кажется принцип наименьшего действия. Даже с Википедией сверился, вроде так:
1) Складываем квадарат расстояния, метры, с квадратом тангенса, разы. Это ошибка уровня начальной школы! При изменении размерности шага одной и той же сетки роль наклона будет менятся: на мелкой (мерим в километрах) сетке алгоритм будет тупо держать начальный уровень (что мы и видим на картинках — метра хватает), а на крупной (мерим в фемтометрах) сетке — тупо переть вперёд игнорируя все перепады высот.
2) Вообще не задана задача оптимизации (если не считать, «хочу красиво»). Что оптимизируем? Длину пути? Расход энергии? Нет — ни то и не то. Какую-то странную величину не имеющую ни физических, ни математических аналогов. А раз задачи нет — то и нельзя понять правильно вы её решили или нет. Мусор на входе — мусор на выходе.
3) Тестовые примеры явно не раскрывают всех проблем алгоритма — поробуйте, например, создать «ловушку» в виде длиннной долины меж гор с тупиком — и путь у вас прекрасно пройдёт если не через локальный экстремум, то прямо рядом с ним. Да даже просто плавный холм с тангенсом наклона меньше порогового (зависит от размера шага сетки) — пройдёт прямо по экстремуму и не заметит.
Как задача на самообучение сойдёт. Но даже как алгоритм для мега тупого ИИ в игрушке, где именно такой и нужен — нет. Хотя бы потому что надо тангенсы считать, которые можно заменить просто квадратом перепада высоты с даже лучшим результатом (который не будет так сильно зависеть от шага)
Бросаются в глаза следующие проблемы.
(1) Точки P1,P2,P3 -- находятся строго впереди по оси Ох. Как следствие, если оптимальный путь должен будет содержать участки с движением в противоположном направлении, то алгоритм будет не в состоянии его найти. Например это может быть сильно извилистая тропинка между высоких гор.
(2) Отказаться от (1), может быть затруднительно, потому что в функция ошибки не содержит предыдущего направления движения. Для иллюстрации, можно рассмотреть плоскую поверхность (без холмов). На такой поверхности, для выбранной функции ошибки, не важно куда идти (верх, низ, вперед, назад) и, вообще говоря получится случайное блуждание. Именно искуственный выбор "всегда продвигаться вперед" и решает подобную проблема, а совсем не оптимальность направления.
(3) точки P1 и P3 дальше от точки отсчета, чем P2. Это подсказка, что нам больше нравится двигаться прямо (жесткая эвристика). При этом на плоскости эти пути должны быть равнозначны. Кроме того, это не позволяет применять алгоритм для других решеток.
(4) Почему добавлен именно tan? Видимо, просто потому что он легко вычисляется (отношения катетов, которые нам известны). Но учитывая, что шаг сетки фиксирован, можно было просто высоту брать с подборным коэффициентом.
(5) При подходящем выборе коэффициента перед tan (в функции ошибки), эта функция ошибки просто сводится к расстоянию от начальной точки до P1-P3. Учитывая, как выбраны P1-P3 (см. (1)), мы легко можем пойти в гору, а не по прямой.
(6) Контрпример. Пусть при x not= 0 высота строго равна нулю. При х=0 у нас дорожка ведущая в гору с фиксированным небольшим углом (пусть его tan^2 = a).
Для удобства будем считать DeX=DeY=1. Для направлений P1 и P3 скор равен 2, для Р2 скор равен 1 + a.
Получаем, что при a < 1 алгорим предложит нам идти в гору, хотя выгодне было немного свернуть.
Это следствие плохо выбранного скора и точек P1-P3.
Да жадная локальность, которая может завести в тупик, самая большая проблема. Надо либо строить карту, либо использовать глобальный алгоритм(Дейкстры, или его реализация на регулярной сетки - волновой). Если реализовать как волновой, то это будет single source shortest path tree, то достаточно пройти вдоль значений в правой границе и выбрать минимальное, это и будет оптимальный путь из точки до правой границы.
Спасибо всем за конструктивные комментарии!
Судя по частоте упоминания, самым оптимальным алгоритмом является алгоритм Дейкстры. Поэтому как появится время и желание - попробую его реализовать для нахождения оптимального маршрута между двумя произвольными точками на карте и написать статью.
По хорошему, помимо естественных ландшафтов - также необходимо добавлять на карту препятствия неприродного характера - здания и др. сооружения, которые, понятное дело, не сможет обойти алгоритм, описанный в этой статье.
судя по картинкам алгоритм просто идет по изовысоте (линии равной высоты), в принципе для поставленной задачи избегать горок это лучшее решение)
умный в Казахстан пойдёт
Нашел в себе силы для реализации алгоритма Дейкстры) Если кому интересно:
Статья переехала сюда: https://habr.com/ru/post/700462/
Умный в гору не пойдет