Solving-task-for-Data-Fusion.-Heroes

KO | EN

gitlite — search

#javascript #hacktoberfest #react #ai #typescript #go #golang #machine-learning #rust #docker #java #cli #vue #open-source

Solving-task-for-Data-Fusion.-Heroes

(★ 11)

Здесь я показываю как удалось решить задачу на оптимизацию пути мультиагентной задачи.

Solving-task-for-Data-Fusion.-Heroes Latest Version Download

Download Latest Version (.zip)

// repository documentation

Was this content helpful?

★ 0 (0 ratings)

### **Алгоритм решает задачу маршрутизации героев по объектам с разными типами ограничениями:**  
1) Мельницы открываются и закрываются, поэтому можно прийти за золотом только в конкретный день и конретное место  
2) Герои имеют разное количество очков хода (ох уж эти гномы-спринтеры, как Гимли)

**Задача** - максимизировать число своевременных посещений, минимизируя число используемых героев.  
**Качество решения** рассчитывается как score = 500 * число посещений - 2500 * число героев.  
Решение даёт для 20-ти геров 291 000 очков. (Пока максимум, что мне удалось добиться)

### **Алгоритм работает следующим образом:**  
1. Сперва строится начальное решение жадным способом:  
На каждом шаге перебираются все допустимые пары «герой–объект».  
Для каждой пары оценивается возможность добавить объект в конец текущего маршрута героя.  
Эвристическая оценка учитывает длину переезда, ожидание до дня открытия, номер дня, остаток очков движения и штраф за запуск нового героя.  
Из всех допустимых ходов выбирается лучший, после чего объект закрепляется за маршрутом.

2. После этого запускается локальное улучшение вставками для объектов, которые не попали ни в один маршрут.  
Каждый такой объект пробуется во всех позициях всех существующих маршрутов.  
Вставка принимается только если она увеличивает число своевременных посещений.  
Среди полезных вставок выбирается та, которая минимально увеличивает длину маршрута.

3. Далее алгоритм переходит к перестройке ранних частей маршрутов через схему префикс–суффикс.  
Маршрут делится на префикс, который можно пересобрать, и суффикс, который временно фиксируется.  
Новый префикс строится через beam search, то есть одновременно рассматриваются несколько лучших частичных вариантов.  
При этом сохраняются только те префиксы, после которых старый суффикс всё ещё достижим.  
Оптимизация идёт в двух фазах: сначала усиливается покрытие объектов первого дня, затем улучшается покрытие объектов первых трёх дней. В первом дне находится наибольшее число мельниц. А мельницы первых трех дней представляют собой львиную долю всех мельниц на неделе.  
На каждой итерации случайно выбирается подмножество героев, для которых перестраиваются только ранние части маршрутов, а остальные фиксируются.

В итоге метод представляет собой гибридную эвристику, сочетающую жадную инициализацию, локальные вставки, beam search и итерационную частичную перестройку решения.  
В качестве ответа предлагаю ознакомиться с файлом, который можно отправить на контест - solution_heroes.csv  
Так же посмотреть анимацию по тому как герои перемещаются по мельницам в heroes_visualization.html  
(NB// Можно посмотреть как строится маршрут на разных алгоритмах и разному числу героев :) )

PS//
Учитывая, что это мой первый подобный опыт участия в мероприятии прошу не судить строго. Я хотел опробовать свои силы и понял, что многое мне не по зубам и что я ещё "зелёный" аналитик.  
При работе и написании кода я использовал ИИ (git hub copilot в PyCharm), о чем заявляю сразу и открыто, так как отрицать это было бы глупо.  
Надеюсь Вам понравится решение и особенно визуализация :)

Всем хорошего времени суток)

Solving-task-for-Data-Fusion.-Heroes

Solving-task-for-Data-Fusion.-Heroes Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Solving-task-for-Data-Fusion.-Heroes

Solving-task-for-Data-Fusion.-Heroes Latest Version Download

Today's picks

Was this content helpful?

Recent Feedback

Download README