Найти короткий путь от стартовой до финальной точки с учетом препятствий в Python

Question

Найти короткий путь от стартовой до финальной точки с учетом препятствий в Python

ксения боковая Знаток (471), закрыт 2 года назад

Получила задание в университете найти самое короткое расстояние от точки S до точки T.
Пробовала различные варианты, но из-за того, что размерность достаточно большая (20х50) программа либо не работает вообще, либо делает расчеты несколько часов.

Подскажите, пожалуйста, как можно решить эту задачу?

Основные этапы, которые должна содержать программа:
1) Создайте лабиринт
Используйте соответствующую структуру данных для внутреннего представления лабиринта, предпочтительно массив NumPy.

2) Визуализируйте лабиринт

3) Определите путь
Путь может быть получен эвристическим или точным способом.
.
4) Распечатайте путь
а. Текстовая форма (координаты): (x1, y1) -> (x2, y2) ->
б. Графическая форма

Answer 1

))) Ну график будет совсем не такой....
Всё довольно просто до точки Х (на рисунке).
Прибавляешь 1 к абциссе, пока не встретишь препятствие, потом прибавляешь 1 к ординате, пока не обойдешь препятствие.
А дальше? Опять препятствие (точка х). И куда двигаться? И вверх и вниз - одинаково верные решения. Но вверху - тупик. А подсказки нет. Т. ч. будет два варианта решения - прямой (вниз) и с возвращением в точку Х (вверх)

Answer 2

https://youtu.be/xXvNDrF4obQ возможно подойдет этот алгоритм