Mail.ruПочтаМой МирОдноклассникиВКонтактеИгрыЗнакомстваНовостиПоискОблакоVK ComboВсе проекты

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

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

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

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

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

3) Определите путь
Путь может быть получен эвристическим или точным способом.
.
4) Распечатайте путь
а. Текстовая форма (координаты): (x1, y1) -> (x2, y2) ->
б. Графическая форма
Лучший ответ
Сергей Бизон Искусственный Интеллект (400256) 1 месяц назад
))) Ну график будет совсем не такой....
Всё довольно просто до точки Х (на рисунке).
Прибавляешь 1 к абциссе, пока не встретишь препятствие, потом прибавляешь 1 к ординате, пока не обойдешь препятствие.
А дальше? Опять препятствие (точка х). И куда двигаться? И вверх и вниз - одинаково верные решения. Но вверху - тупик. А подсказки нет. Т. ч. будет два варианта решения - прямой (вниз) и с возвращением в точку Х (вверх)
ксения боковаяЗнаток (469) 1 месяц назад
Спасибо!
Я понимаю алгоритм, но у меня проблема с его реализацией ????
Сергей Бизон Искусственный Интеллект (400256) ксения боковая, Ксюха. извини, но у меня нет времени для написания программы
Остальные ответы
Alphapopokakapo3 Ученик (225) 1 месяц назад
https://youtu.be/xXvNDrF4obQ возможно подойдет этот алгоритм
Похожие вопросы