#algorithm #graph #language-agnostic #dijkstra
#алгоритм #График #язык — не зависит от языка #dijkstra
Вопрос:
У меня проблема с графиком. Мой график выглядит так:
Реальная проблема в том, что я хочу найти путь с наименьшим количеством «поворотов» между двумя точками. Вот пример :
На этом изображении я рисую простой график 3×3, и кратчайший путь между красной точкой и синей точкой — это зеленая линия, потому что она имеет только один поворот, вместо этого розовая линия имеет 3 поворота.
Я хочу соответствующим образом взвесить ребра графика, а затем использовать алгоритм Дейсктры, чтобы найти подходящий путь
Комментарии:
1. У вас есть какой-нибудь код, который вы можете показать?
2. если вы взвесите горизонтальные ребра как 1, а вертикальные — как 0,999, я думаю, вы можете получить путь всего за один «поворот». Но это всего лишь моя интуиция
3. Аналогично идее vivoconunxino, выполните поиск с помощью * с помощью эвристики h1(x, y) = a x y и / или h2(x, y) = x a y. Где a<1.
4. Используйте алгоритм, основанный на ребрах, и введите функцию стоимости хода
5. Я нахожу решение. Простое ребро имеет стоимость 1, ребро поворота имеет стоимость 2 * (H W), где H — высота графика, а w — ширина. Спасибо всем 😉
Ответ №1:
Ключом к решению является то, что взвешивание операции «поворот» требует больших затрат. Фактически, доступно любое значение, которое больше W H. В то время как, я предполагаю, нужно ли вам модифицировать вашу проблему? Если доступны все ячейки вашего графика, кратчайший путь между двумя точками, очевидно, уникален, и нет необходимости вызывать алгоритм кратчайшего пути, такой как Дейсктра. Если они находятся в одной строке, просто идите прямо, если нет, нужен только один поворот. Поэтому я предлагаю вам добавить некоторое условие, например, некоторые точки недоступны, тогда эта проблема становится интересной.