Akon32 в начале контеста предлагал вместо A* использовать генетический алгоритм. Мы таки реализовали A*, но мне уже надоело бесуспешно тюнить его целевую функцию, так что я подумал-таки и про ГА.
Что нам понадобится:
- генератор решений
- мутатор решений
- скрещивалка решений
- функция починки решений, поломанных мутациями
- управляющая функция, которая будет скрещивать и мутировать топовые решения в надежде получить ещё лучшие
Генератор решений
В первом приближении просто random walk — на каждом шаге делает первое попавшееся действие, приводящее его в новое валидное состояние. Будет генерировать огромные решения, зато быстро.
Также при наличии решения от A* (файла .sol) можно подгружать и его — оно наверняка гораздо оптимальнее и будет отличной основой для мутаций и скрещиваний.
Мутатор решений
Делает одно из:
- удаляет произвольное количество действий с произвольной позиции в решении
- добавляет в произвольную позицию решения произвольное количество произвольных действий.
В результате не обязательно получится валидное решение, но на это у нас будет фиксер.
Скрещивалка решений
- Берёт два существующих валидных решения
- для каждого решения строит множество точек, через которые проходит центр бота
- ищет пересечение этих множеств
- для каждого элемента пересечения:
- находит все разбиения первого решения этой точкой (например, решение AAAAAFDDDFWWWW разбивается элементом F на пары (AAAAAF,DDDFWWWW) и (AAAAAFDDDF,WWWW))
- находит такие же разбиения для второго решения
- склеивает все возможные пары разбиений, чтобы получить новые валидные решения
В результате не обязательно получаем валидное решение, но, опять-таки, есть фиксер.
Функция починки мутированных решений
Следует решению, пока не наткнётся на невалидное действие. Вместо этого действия запускает генерилку, чтобы "дорешать" уже имеющееся решение до конца
Управляющая функция
Принимает на вход массив лучших решений, скрещивает несколько из них, мутирует какие-то другие, возвращает массив такого же размера, но обновлённый лучшими решениями. Будет вызываться в цикле, пока не надоест.
Akon32 в начале контеста предлагал вместо A* использовать генетический алгоритм. Мы таки реализовали A*, но мне уже надоело бесуспешно тюнить его целевую функцию, так что я подумал-таки и про ГА.
Что нам понадобится:
Генератор решений
В первом приближении просто random walk — на каждом шаге делает первое попавшееся действие, приводящее его в новое валидное состояние. Будет генерировать огромные решения, зато быстро.
Также при наличии решения от A* (файла .sol) можно подгружать и его — оно наверняка гораздо оптимальнее и будет отличной основой для мутаций и скрещиваний.
Мутатор решений
Делает одно из:
В результате не обязательно получится валидное решение, но на это у нас будет фиксер.
Скрещивалка решений
В результате не обязательно получаем валидное решение, но, опять-таки, есть фиксер.
Функция починки мутированных решений
Следует решению, пока не наткнётся на невалидное действие. Вместо этого действия запускает генерилку, чтобы "дорешать" уже имеющееся решение до конца
Управляющая функция
Принимает на вход массив лучших решений, скрещивает несколько из них, мутирует какие-то другие, возвращает массив такого же размера, но обновлённый лучшими решениями. Будет вызываться в цикле, пока не надоест.