Алгоритмы Поиска Пути на Python. Алгоритм А*, Дейкстры, Поиск в ширину [ Pygame ]
HTML-код
- Опубликовано: 5 сен 2020
- В данном видео мы познакомимся и на практике применим алгоритмы поиска кратчайших путей такие, как алгоритм Дейкстры (Dijkstra), алгоритм А*(A star) и алгоритм поиска в ширину (BFS) на языке Python (Пайтон, "питон").
Увидим что алгоритм поиска в ширину (breadth first search) используется там, где нет затрат на перемещение. Алгоритм Дейкстры применяется для взвешенного графа в том случае, когда надо найти пути до всех вершин в графе. И алгоритм А* (A star, А со звездочкой) идеально подходит в поиске пути для определенной точки или вершины.
Алгоритмы поиска пути имеют важное и фундаментальное значение в разработке игр, маршрутизации и работы навигаторов.
Для вывода графической информации будем использовать библиотеку Pygame. Pygame это удобная библиотека для вывода графической информации и для создания несложных игр, превосходно подходит для начинающих программировать на языке Python (Пайтон, "Питон").
Чтобы установить Pygame, напечатайте в терминале и нажмите Enter: "pip install pygame" (без кавычек)
Код из видео:
github.com/StanislavPetrovV/P...
#standalonecoder
![Выращиваю Фракталы на Python [ Turtle ]](http://i.ytimg.com/vi/NZC5GiNle4Q/mqdefault.jpg)
![Выращиваю Фракталы на Python [ Turtle ]](/img/tr.png)
![Как Работать с Физикой на Python. Доска Гальтона [ Pygame + Pymunk ]](http://i.ytimg.com/vi/rF1ra9xm9Pc/mqdefault.jpg)
![Eminem - The Death of Slim Shady [Album Trailer]](http://i.ytimg.com/vi/X0HIrS6kUYI/mqdefault.jpg)
Просто красотище. Почему не было таких видео в то время когда я учился ( ... Автору ЖЫРНЫЙ Лайк.
Почему ЖЫРНЫЙ?
@@aangryguyy Ну типа, ЖЫРНЫЙ, а не жирный, типа совсем жирный.
Комментарий в поддержку программистов на Python
Cgc
Лайк, коммент для продвижения канала
Я уверен, что у людей, которые только вкатываются в математику и программирование это вызовет неподдельный интерес)
Спасибо за такие видео
Это, то чего мне не хватало! Спасибо огромное, ты лучший!
Полгода назад искал как описывать препятсвия в таких алгоритмах - сам конечно допёр, но потом попадались только статьи от 2ГИС, и вот мне решили показать наконец-то то что я искал - да почему бы и нет - прогу то всё равно надо сделать, но рекомендации ютуба это С-скорость, ну как говорится лучше поздно чем никогда
Посмотрел сотни видео по этой теме и прочитал множество статей. Реализация просто гениальна. Очень элегантно, автор жжет
Продолжай в том же духе
Красавчик, спасибо за прекрасно подготовленный и поданый материал! В проверке остальных твоих видосов!
Это самый полезный канал на ютубе(мне надо было систему поиска пути) очень помог.
Довольно интересные темы на канале, спасибо за видео!
Да ты в каждом видео делаешь крутые проекты. И оставляешь код. Я думаю студенты обожествляют тебя за такие труды.
Кроме как огромного человеческого спасибо , на данный момент ничем помощь каналу не могу , но возможно благодаря этим знаниям , я смогу что то годное выпустить , и вот тогда смогу и чем то материальным отблагодарить .
Какой же ты красава! Спасибо за контент)
Как всегда, круто!)
Спасибо за ваши видео, желаю дальнейших успехов
Отличная подача материала! Успехов вам)
Шикарно объяснил всё. Спасибо большое!
Прекрасный контент! Хорошо сделано! Желаю удачи в продвижении, 👍
Cool, respect.
Круто, видел подобный алгоритм в книге - грокаем алгоритмы, Спасибо за видео
снова коммент для продвижения канала
Великолепно!
Супер полезный материал, ахуительная подача, реализация на питоне(просто я только питон и знаю) и это все на русском - ну тут просто мое почтение и моя благодарность, мистер.
Шикарный канал!!! Ты молодец!
Прекрасно👏
Огонь! Спасибо за видео!)))
Класс!!! Тема очень интересна!
Это очень полезно, спасибо большое
Это просто мега, супер видео, автор молодец с большой буквы, лайк лайк ...
Респект, классные видео👍
Успел до 100 просмотров)
Еще коммент для продвижения канала
👍👍👍
Святой человек, спасибо тебе!)
супер видео!
Нет слов, чисто лайк
Красавчик!
Спасибо, очень помогло в универе
Очень качественно. 10/10
Крутотень!
Спасибо!
👍
Интересно:)
Лайк, подписка. Спасибо
Благодарю
Круть!
Круто)
Оставлю комментарий, что бы помочь в продвижении)
Сделай видео про различные фракталы(кривая дракона, песочница и тд) думаю будет невероятно круто.
Чел ты крут
Хочу ещё))
поддержу
Пушка
Лайк, коммент
Луууучший
Сросибо
Очень круто, жаль сложно.
Аааа!!!! Вы куда пропали ?!? Канал годный ...
коммент для продвижения канала, зачем я делаю это
Вот не поверишь как ты помог, материал классный. Кроме алгоритма Дейкстры и А* существуют ещё алгоритмы построения позволяющие построить дерево Штейнера?
Классно, но не хватает комментариев в коде на гитхабе)
сделай пж урок по рэй марчинг, ищу ищу информацию да все никак не понимаю найденного, ты очень хорошо объясняешь пж сними ролик🥺🥺🥺
Мне приходилось искать методом волнового алгоритма путь по поверхности 3D модели. Только вместо клеток - вершины.
Никера не понял. Но очень интересно!
Подскажите пожалуйста, где вы нашли такую картинку карты (Алгоритм Дейкстры)((и как сетку сделали? В Пеинте?))? Где можно найти подобные? Заранее спасибо
upd:
про сетку: не заметил офис, прошу прощения)
Сделай пожалуйста дискорд сервер канала
Очень прошу: пишите, пожалуйста, комментарии в коде, который Вы выкладываете на github. Так будет легче понять что и где происходит. Спасибо
⭐⭐⭐⭐⭐
Очень интересно! Правда в коде особо не старался разобраться, так как уже устал задень. Завтра попробую понять))) И не забрасывай это дело. Но мне не даёт покоя вопрос - сколько же тебе лет?)
Где-то 30.
Класс! А если поле не квадратами, а шестиугольниками, то эти алгоритмы работают так же? Или там вся соль в представлении системы координат для такого поля?
Да, вся соль в представлении такой карты, а алгоритмы те же.
643 лайка и 0 дизов, молодец)
однако!
У меня вопрос(2:45): Зачем в переменную graph запихивать каждую соседнюю клетку сразу всех клеток? Разве это не забьёт память не нужной информацией, если карта будет большой, в то время, когда 80% этой информации даже не понадобится.
Разве не легче вызывать функцию get_neighbours с параметрами текущей клетки тогда, когда это нужно, чтобы получать только тех соседей, которые нужны.
А такое-же, только в 3д будет?
братан, у тебя нету случайно текст этого видео в записаной форме?? мне очень нужно, пожалуйсто
Что если у тебя не будет пути из А в В в графах такое возможно?
Отлично, автор ответь по электронной почте пожалуйста
Кажется переменная cur_cost не нужна и можно просто добавлять в приоритетную очередь элементы. 7:17
А можно как то сделать чтобы алгоритм двигался с 0 на 1 а с 1 на 0 (желательно кодом если можно)
Deque не содержится в collections что делать
В коде с Поиском в ширину есть одна проблема, по крайней мере я точь в точь писал код и иногда выдовало ошибку, бро, когда припятствия рандомно строятся то начальная точка пути, а именно [0][0] может быть не пустой, и путь не будет строится
grid[0][0] = 0
Проблема решается ))
@@doctorbuglindesh8563 ну я так и решил)
Я и тут
А как можно нарисовать не кратчайший путь, а самый длинный? Очень нужно, а я не очень понимаю как сделать
У меня к тебе вопрос .. Как в этом алгоритме сделать минимальное количество поворотов ? Тоесть найти путь с минимальным количеством поворотов
Привет
Вердикт:У автора уровень IQ выше 140
™
Разрешите вопрос, border_radius, как автор это сделал, в моем коде он ругается на это, типа какого хрена, переменная делает здесь. Подскажите как сделать
Установите Pygame 2-ю версию
pip install pygame==2.0.0dev22
@@StandaloneCoder спасибо большое
У тебя профессиональный пайчарм?
Обычный Community Edition
Что делать если в коде с гит хаба rect() выдает ошибку?
удалить параметр border_radius из rect или установить pygame 2.0.0
pip install pygame==2.0.0dev24
Зачееееееееееет!!!
А алгоритм вообще быстрый? А то я на питоне волновой алгоритм на поле 3000 х 3000 быстрее чем 0.15 секунд не смог разогнать (и то с математическим модулем)
Путь искали до определенной точки или пути до всех точек на поле?
@@StandaloneCoder ну смотри, брался массив карты из 0 и 1,где 0 - свободно, 1 - преграды. Каждый такт от начала я заполнял соседние свободные элементы количеством шагов, который я собственно итерировал,и проверял - конечная это точка или нет. Если точка конечная, то уже от неё искал самые низкие значения, и добавлял индекс в список, который и являлся восстановленным путем.
Ах да, путь до одной точки
Помогите пожалуйста, у меня не работает почему то
за что отвечает TILE
А сделай ботов на нейросетях
Я вставил , и почему то неработает
слишком быстро рисуется код, слишком быстро читается текст
какой сложный синтаксис, для понимания ... чайнику
Круто, всего 1 дизлайк)