Проблема поиска кратчайшего пути по поверхности 2D-сетки

Question

Я задал этот вопрос три дня назад, и меня сожгли авторы, потому что я не включил достаточную информацию. Мне жаль насчет того.

У меня есть 2D-матрица, и каждое положение массива связано с глубиной воды в канале, я надеялся применить алгоритм Дейкстры или аналогичный алгоритм «наименьшей стоимости», чтобы узнать наименьшее количество бетона, необходимое для создания мост через воду.

Потребовалось некоторое время для форматирования данных в чистую версию, поэтому я изучил некоторые рудиментарные навыки Matlab, которые это сделали. Я удалил большую часть земли, так что теперь береговая линия стандартизирована до определенного значения, мой план состоит в том, чтобы использовать петлю для перемещения по каждому «пикселю» на «западном» берегу и запускать алгоритм наименьшей стоимости против него до ближайшего «восточный» берег и перемещаться по всей сетке, в конечном счете находить наименее затратный.

Это моя проблема, подгоняя данные к любому из алгоритмов. К сожалению, меня переполняют варианты и разные форматы, потому что другие примеры для других случаев использования.

Мое другое соображение состоит в том, что когда вычисляется самый короткий путь затрат, это будет зубчатая линия, которая не подходит для моста, поэтому мне нужно ограничить радиус изгиба на пути, если это вообще возможно, я знаю, как это сделать.

Изображение канала:

Любые советы в методе подход было бы здорово, мне просто нужно знать, если кто-то знает способ, который должен работать, тогда я буду тратить время обучения как установить данные.

Answer 1

Вы можете применить Дейкстр для вашей проблемы таким образом:

1. два «сухих» регионов вы хотите подключиться, соответствуют матричным со значением 0; другие ячейки имеют положительное значение, определяющее глубину (или стоимость заполнения этого места бетоном).

2. Ваши ребра являются связями соседних ячеек в вашей матрице. (Это может быть 4- или 8-окрестность.) Вес ребра - среднее арифметическое значений связанных ячеек.

3. , то вы применяете алгоритм Дейкстры с начальной точкой в ​​одной «сухой» области и конечной точкой в ​​другой «сухой» области.

Самый дешевый путь соединит две ячейки со значением 0 и его вес будет соответствовать сумме затрат на посещенные ячейки. (Половина каждого веса ячейки исходит от края, идущего к ячейке, другая половина от края, выходящего из ячейки.)

Таким образом, вы получите, возможно, довольно кривую дорожку, ведущую через воду, которая может быть полезный намек на то, где можно построить дешевый мост.

Вы можете ускорить вычисление с помощью алгоритма A *. Поэтому для достижения другой стороны для каждой ячейки требуется нижняя граница оставшихся затрат. Такую нижнюю границу можно вычислить, исследуя «концентрические кольца» вокруг точки, коль скоро кольца не содержат 0-ячейки другой стороны. Сумма минимальных значений ячеек для каждого кольца тогда является нижней границей остальных затрат.

Answer 2

Альтернативный подход, в котором подчеркивается ограничение, которое требуется для не-зубчатой ​​формы для вашего моста, заключается в использовании Монте-Карло, моделируемого отжига или генетического алгоритма, где первоначальный «мост» состоял из простой кривой сплайна между двумя случайно выбранными конечными точками (по одной на каждой стороне пропасти), плюс небольшое количество или случайно выбранные промежуточные точки в пропасти. У вас будет физически «реалистичный» мост и разумно оптимизированная стоимость бетона.