Поиск пути по 2D массиву

Question

У меня есть двумерный массив int, который я обработал и получил из изображения. Каждый индекс можно рассматривать как вес этого пикселя. Я хочу найти путь между двумя индексами (я приведу эти индексы в качестве входных данных), который имеет наименьшую стоимость. Было бы замечательно, если бы направление движения можно было изменить (например, только вниз и влево, вверх и влево, или все. И т. Д., В противном случае оно может быть внизу, влево и вправо)

Как я могу это сделать в C #?

Answer 1

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

1. Любой путь, который> = базовая линия (или текущий лучший), завершается
2. Любой путь, который попадет в индексдважды заканчивается
3. Любой успешный путь устанавливает новую базовую линию (или лучшую)

Answer 2

Алгоритм A * (как уже помечено :)) является хорошим выбором для этого.

См., Например, Как реализовать алгоритм A *?