0:48 Описание инструментов 1:34 Алоритм поиска в ширину 3:00 Алгоритм поиска в глубину 3:58 Жадный поиск 5:02 Сравнение результатов трех алгоритмов в одинаковых условиях
Можно еще добавить проверку в алгоритм поиск в ширину, что если следуя по прямой нет препятствий то не париться ) допустим в играх часто кликают мышкой недалеко от персонажа и чаще всего путь чист
Жадный алгоритм практически так и двигается по прямой, к цели. А при поиске в ширину, боюсь, что гарантировать отсутствие препятствия при клике "недалеко" невозможно. Поэтому все равно пришлось бы проверять клетку на препятствие, а что делать в случае его нахождения? Так же невозможно гарантировать, что в направлении к цели нет тупика.
Ну жадный получается самым красивым и естественным чтоль. Возможно он и не находит самый короткий путь. Хотя поиск в ширину тоже же не единственный маршрут показывает, а несколько. По сути да он выдаёт маршрут из нескольких равноценных. Потому можно широкий поиск как самый оптимальный сделать ещё и красивым, если он будет выбирать из полученных маршрутов не самый первый из равноценных, а тот из равноценных, который ближе к цели.
Вообще для жадного алгоритма (и любого другого) есть алгоритмы надстройки вроде алгоритма Йена, которые отвечают за нахождение k кратчайших путей. И как раз жадные алгоритмы - чемпионы по нахождению кратчайшего пути за приемлемое время, тот же Дейкстра относится к жадным, но почти всегда находит кратчайший (если пути нет то и находить нечего). А* тоже самое - модификация Дейкстры. Секрет в том, что Дейкстра - это жадная вариация поиска в ширину, то есть перебираются не все ребра и вершины подряд по очереди, а те которые обладают наименьшей меткой. В то время как жадный идет напролом и не пытается проверить предыдущие ответвления, вруг по ним идти короче.
Простой жадный тупее чем А*, А* это жадный поиск в ширину, то есть это все еще поиск в ширину но с эвристикой отвечающей за оптимальность пути. А* с неоптимальной эвристикой деградирует до уровня жадного и поиска в ширину, или даже хуже. Но с оптимальной эвристикой их превосходит.
Есть, простой жадный тупее чем А*, А* это жадный поиск в ширину, то есть это все еще поиск в ширину но с эвристикой отвечающей за оптимальность пути. А* с неоптимальной эвристикой деградирует до уровня жадного и поиска в ширину, или даже хуже.
@@masklab6748Слушай а если сделать чтоб Старт и Финиш искали путь друг к другу? Я думаю так они найдут самый короткий путь от Старта до Финиша типо Финиш ищет Старт а Старт ищет Финиш Запутано сказал сори.. 😂🎉
0:48 Описание инструментов
1:34 Алоритм поиска в ширину
3:00 Алгоритм поиска в глубину
3:58 Жадный поиск
5:02 Сравнение результатов трех алгоритмов в одинаковых условиях
Залил проект на гитхаб github.com/Fastto/UnityPathFinding
Можно еще добавить проверку в алгоритм поиск в ширину, что если следуя по прямой нет препятствий то не париться ) допустим в играх часто кликают мышкой недалеко от персонажа и чаще всего путь чист
Жадный алгоритм практически так и двигается по прямой, к цели.
А при поиске в ширину, боюсь, что гарантировать отсутствие препятствия при клике "недалеко" невозможно. Поэтому все равно пришлось бы проверять клетку на препятствие, а что делать в случае его нахождения?
Так же невозможно гарантировать, что в направлении к цели нет тупика.
@@masklab6748 а если скомбинировать, допустим запустить жадный алгоритм и если встретится препятствие, то с этой точки подключить поиск в ширину?
Ну жадный получается самым красивым и естественным чтоль. Возможно он и не находит самый короткий путь.
Хотя поиск в ширину тоже же не единственный маршрут показывает, а несколько. По сути да он выдаёт маршрут из нескольких равноценных. Потому можно широкий поиск как самый оптимальный сделать ещё и красивым, если он будет выбирать из полученных маршрутов не самый первый из равноценных, а тот из равноценных, который ближе к цели.
Вообще для жадного алгоритма (и любого другого) есть алгоритмы надстройки вроде алгоритма Йена, которые отвечают за нахождение k кратчайших путей.
И как раз жадные алгоритмы - чемпионы по нахождению кратчайшего пути за приемлемое время, тот же Дейкстра относится к жадным, но почти всегда находит кратчайший (если пути нет то и находить нечего). А* тоже самое - модификация Дейкстры. Секрет в том, что Дейкстра - это жадная вариация поиска в ширину, то есть перебираются не все ребра и вершины подряд по очереди, а те которые обладают наименьшей меткой. В то время как жадный идет напролом и не пытается проверить предыдущие ответвления, вруг по ним идти короче.
"Жадный" алгоритм можно было сразу назвать А* и никого не путать)
Это разные алгоритмы
Простой жадный тупее чем А*, А* это жадный поиск в ширину, то есть это все еще поиск в ширину но с эвристикой отвечающей за оптимальность пути. А* с неоптимальной эвристикой деградирует до уровня жадного и поиска в ширину, или даже хуже. Но с оптимальной эвристикой их превосходит.
Жадный? А* что ли изобрели? Или реально есть отличия?
Есть, простой жадный тупее чем А*, А* это жадный поиск в ширину, то есть это все еще поиск в ширину но с эвристикой отвечающей за оптимальность пути. А* с неоптимальной эвристикой деградирует до уровня жадного и поиска в ширину, или даже хуже.
А как же алгоритм "одной руки". И да, персонажу нужно имя придумать.
Поиск в глубину это почти алгоритм одной руки ), но без попадания в мертвую петлю в закольцованных коридорах
@@masklab6748Слушай а если сделать чтоб Старт и Финиш искали путь друг к другу? Я думаю так они найдут самый короткий путь от Старта до Финиша типо Финиш ищет Старт а Старт ищет Финиш
Запутано сказал сори.. 😂🎉
Есть вариант на Java?
Есть конвертеры c# => Java,
я так реализацию многослойного перцептрона перегнал, с небольшими коррекциями все отлично завелось )
тут 287 ставлю - не вышло круглого числа )