Нахождение неглубокого пути через матрицу

Question

Я надеялся, что смогу получить некоторый совет относительно соответствующего алгоритма, чтобы найти самый мелкий (наименее крутой) путь между двумя точками в моей матрице/графе.

Я приложил график матрицы ниже. Мне нужен алгоритм, который идет от «B'eginning to» End. По глазу, довольно очевидно, что путь (юго-восток от B, а затем от северо-востока до E) всегда остается на красноватой окраске.

Длина пути не имеет значения.

Цвета представляют собой ось z и составляет от 0 до> 1. Желтый (самый яркий) - 1, а синий (самый темный) равен 0. Я хочу перейти от B-> E с изменением значения z по пути; таким образом, я хочу по существу оставаться на одном и том же цвете (вернее, я не хочу, чтобы цвет сильно менялся), поскольку я иду из B-> E.

Answer 1

Я полагаю, используя эвристический алгоритм поиска пути, как и A* с использованием разности между клетками, как вес. Подумайте об этом как о взвешенном графике, где вес ребер определяется разностью значений ячейки (поэтому менее крутой, чем дешевле).

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