Олимпиада 2020 обсуждение алгоритмов

Ответить
Artem.spb

Activity Автор
professor
professor
Сообщения: 3393
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Версия LabVIEW: 12-18
Благодарил (а): 49 раз
Поблагодарили: 172 раза
Контактная информация:

Олимпиада 2020 обсуждение алгоритмов

Сообщение Artem.spb »

Тема вопросов плавно превратилась в тему обсуждения алгоритмов.
Предлагаю перенести это сюда.
Команды по желанию могут выложить свои решения, поделиться идеями и находками.
:drink:
Artem.spb

Activity Автор
professor
professor
Сообщения: 3393
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Версия LabVIEW: 12-18
Благодарил (а): 49 раз
Поблагодарили: 172 раза
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение Artem.spb »

Дополнение: вроде спорных ситуаций нет, так что мы (организаторы) не будем принудительно публиковать решения участников.
Но с другой стороны, вряд ли там есть секретные военные разработки, так что призываю участников поделиться.
Сейчас идёт последний раунд, так что изменение быть не должно, можно вскрываться.
Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
guru
guru
Сообщения: 5462
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Версия LabVIEW: 2015, 2016
Откуда: СССР
Благодарил (а): 28 раз
Поблагодарили: 86 раз

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение IvanLis »

Artem.spb писал(а): 28 дек 2020, 20:41 Команды по желанию могут выложить свои решения, поделиться идеями и находками.
Я полностью "ЗА" :super:
Думал по возможности сделать кратное описание алгоритмов каждого этапа и выкладывать их по готовности вместе с исходниками.
Так и логика понятна будет, не то что в коде разбираться. И процесс эволюции виден, как от этапа к этапу все менялось.

Тем более некоторые задумки понятны, а некоторые очень интересно узнать и понять.
Artem.spb

Activity Автор
professor
professor
Сообщения: 3393
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Версия LabVIEW: 12-18
Благодарил (а): 49 раз
Поблагодарили: 172 раза
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение Artem.spb »

Я конечно подыгрываю всем командам, но почему такие разные результаты, плохо понимаю.
Любопытно, что алгоритм Ивана в целом самый эффективный, но в паре случаев он "сломался". Возможно, еды не хватило :)
Artem.spb

Activity Автор
professor
professor
Сообщения: 3393
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Версия LabVIEW: 12-18
Благодарил (а): 49 раз
Поблагодарили: 172 раза
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение Artem.spb »

Они скоро настигнут всю еду :)
3-4_3.png
Я тут подумал, ты же вычисляешь относительные координаты куч. Можно было бы кодировать в центре муравейника их расположения.
И каждый добежавший с грузом может свериться, что таскает самое близкое.
Хотя, предыдущий раунд показал, что иногда полезнее утащить у конкурентов, а потом уже своё забирать.
Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
guru
guru
Сообщения: 5462
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Версия LabVIEW: 2015, 2016
Откуда: СССР
Благодарил (а): 28 раз
Поблагодарили: 86 раз

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение IvanLis »

Artem.spb писал(а): 28 дек 2020, 21:39 Любопытно, что алгоритм Ивана в целом самый эффективный, но в паре случаев он "сломался".
Я бы его назвал "тактикой выжженной земли", изначально нацеливался на 100% охват территории, что бы ничего не пропустить.
На скрине, когда метки не исчезали видно покрытие, т.е. фактически везде побывал.
Шаг сканирования задается при жестко, он у меня равен 5, практически все кучи, что равны 5 должны быть обнаружены хотя бы одним муравьем. Если куча размером 20, то 3 муравья в нее минимум попадут.
3-2_8.png
Но если есть достоинства, значит есть и недостатки.
Недостаток, например по сравнению с lab55, они выигрывают массовостью. Т.е. один нашел, тропинку протоптал, а остальные за ним рванули. Эта тактика хорошо себя показывает, если кучи маленькие и их мало.

Ну и ранее я написал, т.к. у меня поиск по спирали, а рельеф например как в раунде 3, с радиальными оврагами. То мои муравьи много времени тратят именно на поиск, постоянно поднимаясь в гору.

Хотя я при тестах на разных рельефах, сначала пытался носить еду по оврагам, минимизировав спуски/подъемы. Но тесты показали, что в среднем, сколько ты поднимаешься, столько и спускаешься, т.е. так на так и выходит. А предугадать "лестницы" которые преходилось преодолевать в раундах 1 и 2, наверное можно, но мало вероятно.
Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
guru
guru
Сообщения: 5462
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Версия LabVIEW: 2015, 2016
Откуда: СССР
Благодарил (а): 28 раз
Поблагодарили: 86 раз

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение IvanLis »

Artem.spb писал(а): 28 дек 2020, 21:49 Я тут подумал, ты же вычисляешь относительные координаты куч. Можно было бы кодировать в центре муравейника их расположения.
И каждый добежавший с грузом может свериться, что таскает самое близкое.
Хотя, предыдущий раунд показал, что иногда полезнее утащить у конкурентов, а потом уже своё забирать.
1. С учетом рельефа, ближний не значит короткий.
2. В центр муравейника достаточно сложно попасть, что бы оставить там метку другим. Я с этим столкнулся еще на 1 этапе.
3. На мой взгляд, эффективнее таскать с разных мест, чем с ближайшего. Тем более, после того как ближняя куча закончится, муравьи продолжат поиск с того места, где он закончился и с большей степени вероятности, присоединятся к тем что таскают из дальней.

----------------
Я в первом раунде делал следующий алгоритм:
1. все кто нашел хавчик, бегут в центр муравейника и метят путь
2. когда прибежал в центр, то проверяют, есть ли метка в точке разбега (центр)
3. если метка есть, то значит кто-то вернулся раньше (он назначается "лидером"), а значит есть более короткий путь
4. все бегут по кротчайшему пути, периодически его обновляя (за это отвечает лидер)
5. пересекающие путь муравьи, которые ничего не нашли, они его однозначно должны пересечь (надеюсь), возвращаются в центр муравейника, а оттуда уже вместе с остальными
Artem.spb

Activity Автор
professor
professor
Сообщения: 3393
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Версия LabVIEW: 12-18
Благодарил (а): 49 раз
Поблагодарили: 172 раза
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение Artem.spb »

Проверял видео и вспомнил возможную оптимизацию.
В третьем всю еду умудрились разобрать. Так вот надо было добавить состояние "еда кончилась", в котором обрабатывать действия только тех насекомых, которые что-то тащат. А то много ресуров вхолостую гонял.
Идея пришла в голову сегодня днём, но уже не стал на последнем раунде её впиливать.
Artem.spb

Activity Автор
professor
professor
Сообщения: 3393
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Версия LabVIEW: 12-18
Благодарил (а): 49 раз
Поблагодарили: 172 раза
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение Artem.spb »

IvanLis писал(а): 28 дек 2020, 22:02 1. С учетом рельефа, ближний не значит короткий.
Соглашусь, но рельеф появился только на последнем туре.
И по видео я не заметил, чтобы кто-то пользовался знаниями о размерах мира. Много кто таскает еду через край.
По поводу же рельефа. Ну довольно разумно предположить симметрию мира, иначе мне сложно обеспечить равные условия для всех, так что варианты есть. Можно сообщать не только координаты, но и количество шагов. "ходи туда три дня, там СТОЛЬКО!"
Ну а с полем зрения 5х5 попадать в центр и не обязательно :)
Аватара пользователя
alerm

Activity
leader
leader
Сообщения: 682
Зарегистрирован: 02 май 2012, 21:28
Награды: 1
Версия LabVIEW: 20
Благодарил (а): 57 раз
Поблагодарили: 9 раз
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение alerm »

Я, наверное, описывать подробно алгоритм не буду, там и так видно.

На первом этапе муравьи просто ищут еду, а если нашли, то начинают таскать домой. Если в клетках 3*3 нет меток, то муравей поставит метку, неся еду. У каждого муравья существует некий параметр ("храбрость"), который отвечает за количество шагов вне муравейника. После возвращения муравья домой, этот параметр увеличивается.

На втором этапе добавилось несколько правил:
1) если муравей нашёл еду по метке, то он только таскает еду;
2) если муравей нашёл еду сам, то существует 33% вероятность, что он оставит метку, если её ещё нет именно в том месте, где пойдет он (плюс соседние клетки);
3) параметр "храбрость" увеличивается не так сильно между заходами, и если муравей отдалился от муравейника больше чем на половину диагонали квадрата со стороной M (+10%), то "храбрость" будет уменьшаться с каждым заходом пока не станет меньше 500, затем снова начнет увеличиваться;
4) добавилось состояние (т.е. вернулось), отвечающее за поиск еды, если муравей вернулся на место кучки, а еды не нашёл.

На третьем этапе увеличение параметра "храбрость" происходит ещё медленнее и убралось +10% к расстоянию, после отдаления на которое "храбрость" начинает уменьшаться. Если в куче еды оставалось менее 10 полных загрузок (2550) еды, то отключалось состояние "поиск еды" (пункт 4 на втором этапе).

Так же на втором и третьем этапах добавились коэффициенты к скорости, хотя на последнем этапе это не помогло, и муравьи "зависали" :buuh:

Запускать через test many ants.vi
ants.7z
2015
(275.05 КБ) 111 скачиваний
Аватара пользователя
IvanLis

Activity Professionalism Tutorials Gold Man of the year 2012
Автор
guru
guru
Сообщения: 5462
Зарегистрирован: 02 дек 2009, 17:44
Награды: 7
Версия LabVIEW: 2015, 2016
Откуда: СССР
Благодарил (а): 28 раз
Поблагодарили: 86 раз

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение IvanLis »

Сделал краткое описание алгоритма первого этапа.
В архиве присутствуют незадействованные функции, которые остались от не вошедших в финальную версию разработок, некоторые из них могут не работать, так что не ругайтесь.
Надеюсь не утомил своей писаниной.
ant_IvanLis_st1.zip
lv2015
(211.48 КБ) 110 скачиваний
ant_IvanLis_st1.pdf
(702.76 КБ) 98 скачиваний
ant_IvanLis_st1.docx
(533.34 КБ) 89 скачиваний
Описание 2 и 3 этапов сделаю позже.
Artem.spb

Activity Автор
professor
professor
Сообщения: 3393
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Версия LabVIEW: 12-18
Благодарил (а): 49 раз
Поблагодарили: 172 раза
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение Artem.spb »

alerm писал(а): 30 дек 2020, 17:30. У каждого муравья существует некий параметр ("храбрость"), который отвечает за количество шагов вне муравейника. После возвращения муравья домой, этот параметр увеличивается.
А что даёт возвращение?
Если я правильно понимаю, в муравейнике нет данных о найденной еде. Тогда для чего муравей бегает домой?
Аватара пользователя
alerm

Activity
leader
leader
Сообщения: 682
Зарегистрирован: 02 май 2012, 21:28
Награды: 1
Версия LabVIEW: 20
Благодарил (а): 57 раз
Поблагодарили: 9 раз
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение alerm »

Artem.spb писал(а): 31 дек 2020, 10:00 А что даёт возвращение?
Если я правильно понимаю, в муравейнике нет данных о найденной еде. Тогда для чего муравей бегает домой?
Ну... тут несколько причин: чтобы муравьи бесконечно не убегали от дома, а также возможность введения усталости или голода.
Artem.spb

Activity Автор
professor
professor
Сообщения: 3393
Зарегистрирован: 31 июл 2011, 23:05
Награды: 2
Версия LabVIEW: 12-18
Благодарил (а): 49 раз
Поблагодарили: 172 раза
Контактная информация:

Re: Олимпиада 2020 обсуждение алгоритмов

Сообщение Artem.spb »

alerm писал(а): 09 янв 2021, 13:02 Ну... тут несколько причин: чтобы муравьи бесконечно не убегали от дома, а также возможность введения усталости или голода.
Усталость и голод реально были претендентами в последних турах :)
Ответить
  • Похожие темы
    Ответы
    Просмотры
    Последнее сообщение

Вернуться в «Olympiad 2020»