tg-me.com/iosdev/516
Last Update:
Алгоритм Дейкстры в Swift, используя GameplayKit. Погодите, что?!
Если вы когда-либо слышали что-то про теорию графов, то наверняка знакомы с алгоритмом Дейкстры.
Краткий термин для понимания, для чего он: алгоритм находит кратчайшие пути от одной из вершин графа до всех остальных, важное условие — он работает для рёбер без отрицательного веса.
Примеры задач, которые можно решить с помощью данного алгоритма:
⚪ Дана сеть автомобильных дорог, соединяющих города. Некоторые дороги односторонние. Требуется найти кратчайшие пути от исходного города до любого другого (если двигаться можно только по дорогам).
⚪ Имеется некоторое количество авиарейсов между городами мира, для каждого известна стоимость. Требуется найти самый дешёвый билет.
📖 Федерико Занетелло в одной из своих статей обратил внимание на то, что иногда для решения сложных задач можно пойти по нестандартному пути (кратчайшему, я бы сказал😅).
Что умеет GameplayKit?
В порядке перечисления: рандомизация, сущности и компоненты, стейт-машины, реализация минимакса, нахождение путей, системы правил, а также возможность создания симуляций для игровых персонажей.
Пожалуй, вы уже видите, куда клонит автор?
🛠 С помощью подкласса для GKGraphNode и нескольких строк кода автор покажет, как можно реализовать нахождение кратчайшего пути и использовать в вашем коде.
🛠 Сам проект также опенсорсный и находится здесь.
P.S. Заголовок материала показывает не всю суть, так как GameplayKit внутри может использовать и алгоритм Форда-Беллмана. Спасибо автору, который об этом также указывает.
И ещё один полезный вывод от Федерико заключается в том, что использовать коробочное решение иногда лучше, так как, например, GameplayKit поддерживается инженерами Apple постоянно, а наши с вами ресурсы не бесконечны.
Впрочем, эта тема гораздо шире и заслуживает отдельного обсуждения как-нибудь в будущем.
@iOS Dev
BY iOS Dev
Share with your friend now:
tg-me.com/iosdev/516