Олимпиада 2020 обсуждение алгоритмов
-
- professor
- Сообщения: 3393
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 172 раза
- Контактная информация:
Олимпиада 2020 обсуждение алгоритмов
Тема вопросов плавно превратилась в тему обсуждения алгоритмов.
Предлагаю перенести это сюда.
Команды по желанию могут выложить свои решения, поделиться идеями и находками.
Предлагаю перенести это сюда.
Команды по желанию могут выложить свои решения, поделиться идеями и находками.
-
- professor
- Сообщения: 3393
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 172 раза
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
Дополнение: вроде спорных ситуаций нет, так что мы (организаторы) не будем принудительно публиковать решения участников.
Но с другой стороны, вряд ли там есть секретные военные разработки, так что призываю участников поделиться.
Сейчас идёт последний раунд, так что изменение быть не должно, можно вскрываться.
Но с другой стороны, вряд ли там есть секретные военные разработки, так что призываю участников поделиться.
Сейчас идёт последний раунд, так что изменение быть не должно, можно вскрываться.
-
IvanLis
- guru
- Сообщения: 5462
- Зарегистрирован: 02 дек 2009, 17:44
- Награды: 7
- Версия LabVIEW: 2015, 2016
- Откуда: СССР
- Благодарил (а): 28 раз
- Поблагодарили: 86 раз
Re: Олимпиада 2020 обсуждение алгоритмов
Я полностью "ЗА"
Думал по возможности сделать кратное описание алгоритмов каждого этапа и выкладывать их по готовности вместе с исходниками.
Так и логика понятна будет, не то что в коде разбираться. И процесс эволюции виден, как от этапа к этапу все менялось.
Тем более некоторые задумки понятны, а некоторые очень интересно узнать и понять.
Знание нескольких принципов освобождает от знания многих фактов!
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
-
- professor
- Сообщения: 3393
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 172 раза
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
Я конечно подыгрываю всем командам, но почему такие разные результаты, плохо понимаю.
Любопытно, что алгоритм Ивана в целом самый эффективный, но в паре случаев он "сломался". Возможно, еды не хватило :)
Любопытно, что алгоритм Ивана в целом самый эффективный, но в паре случаев он "сломался". Возможно, еды не хватило :)
-
- professor
- Сообщения: 3393
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 172 раза
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
Они скоро настигнут всю еду :)
И каждый добежавший с грузом может свериться, что таскает самое близкое.
Хотя, предыдущий раунд показал, что иногда полезнее утащить у конкурентов, а потом уже своё забирать.
Я тут подумал, ты же вычисляешь относительные координаты куч. Можно было бы кодировать в центре муравейника их расположения. И каждый добежавший с грузом может свериться, что таскает самое близкое.
Хотя, предыдущий раунд показал, что иногда полезнее утащить у конкурентов, а потом уже своё забирать.
-
IvanLis
- guru
- Сообщения: 5462
- Зарегистрирован: 02 дек 2009, 17:44
- Награды: 7
- Версия LabVIEW: 2015, 2016
- Откуда: СССР
- Благодарил (а): 28 раз
- Поблагодарили: 86 раз
Re: Олимпиада 2020 обсуждение алгоритмов
Я бы его назвал "тактикой выжженной земли", изначально нацеливался на 100% охват территории, что бы ничего не пропустить.
На скрине, когда метки не исчезали видно покрытие, т.е. фактически везде побывал.
Шаг сканирования задается при жестко, он у меня равен 5, практически все кучи, что равны 5 должны быть обнаружены хотя бы одним муравьем. Если куча размером 20, то 3 муравья в нее минимум попадут. Но если есть достоинства, значит есть и недостатки.
Недостаток, например по сравнению с lab55, они выигрывают массовостью. Т.е. один нашел, тропинку протоптал, а остальные за ним рванули. Эта тактика хорошо себя показывает, если кучи маленькие и их мало.
Ну и ранее я написал, т.к. у меня поиск по спирали, а рельеф например как в раунде 3, с радиальными оврагами. То мои муравьи много времени тратят именно на поиск, постоянно поднимаясь в гору.
Хотя я при тестах на разных рельефах, сначала пытался носить еду по оврагам, минимизировав спуски/подъемы. Но тесты показали, что в среднем, сколько ты поднимаешься, столько и спускаешься, т.е. так на так и выходит. А предугадать "лестницы" которые преходилось преодолевать в раундах 1 и 2, наверное можно, но мало вероятно.
Знание нескольких принципов освобождает от знания многих фактов!
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
-
IvanLis
- guru
- Сообщения: 5462
- Зарегистрирован: 02 дек 2009, 17:44
- Награды: 7
- Версия LabVIEW: 2015, 2016
- Откуда: СССР
- Благодарил (а): 28 раз
- Поблагодарили: 86 раз
Re: Олимпиада 2020 обсуждение алгоритмов
1. С учетом рельефа, ближний не значит короткий.Artem.spb писал(а): ↑28 дек 2020, 21:49 Я тут подумал, ты же вычисляешь относительные координаты куч. Можно было бы кодировать в центре муравейника их расположения.
И каждый добежавший с грузом может свериться, что таскает самое близкое.
Хотя, предыдущий раунд показал, что иногда полезнее утащить у конкурентов, а потом уже своё забирать.
2. В центр муравейника достаточно сложно попасть, что бы оставить там метку другим. Я с этим столкнулся еще на 1 этапе.
3. На мой взгляд, эффективнее таскать с разных мест, чем с ближайшего. Тем более, после того как ближняя куча закончится, муравьи продолжат поиск с того места, где он закончился и с большей степени вероятности, присоединятся к тем что таскают из дальней.
----------------
Я в первом раунде делал следующий алгоритм:
1. все кто нашел хавчик, бегут в центр муравейника и метят путь
2. когда прибежал в центр, то проверяют, есть ли метка в точке разбега (центр)
3. если метка есть, то значит кто-то вернулся раньше (он назначается "лидером"), а значит есть более короткий путь
4. все бегут по кротчайшему пути, периодически его обновляя (за это отвечает лидер)
5. пересекающие путь муравьи, которые ничего не нашли, они его однозначно должны пересечь (надеюсь), возвращаются в центр муравейника, а оттуда уже вместе с остальными
Знание нескольких принципов освобождает от знания многих фактов!
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
-
- professor
- Сообщения: 3393
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 172 раза
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
Проверял видео и вспомнил возможную оптимизацию.
В третьем всю еду умудрились разобрать. Так вот надо было добавить состояние "еда кончилась", в котором обрабатывать действия только тех насекомых, которые что-то тащат. А то много ресуров вхолостую гонял.
Идея пришла в голову сегодня днём, но уже не стал на последнем раунде её впиливать.
В третьем всю еду умудрились разобрать. Так вот надо было добавить состояние "еда кончилась", в котором обрабатывать действия только тех насекомых, которые что-то тащат. А то много ресуров вхолостую гонял.
Идея пришла в голову сегодня днём, но уже не стал на последнем раунде её впиливать.
-
- professor
- Сообщения: 3393
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 172 раза
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
Соглашусь, но рельеф появился только на последнем туре.
И по видео я не заметил, чтобы кто-то пользовался знаниями о размерах мира. Много кто таскает еду через край.
По поводу же рельефа. Ну довольно разумно предположить симметрию мира, иначе мне сложно обеспечить равные условия для всех, так что варианты есть. Можно сообщать не только координаты, но и количество шагов. "ходи туда три дня, там СТОЛЬКО!"
Ну а с полем зрения 5х5 попадать в центр и не обязательно :)
-
alerm
- leader
- Сообщения: 682
- Зарегистрирован: 02 май 2012, 21:28
- Награды: 1
- Версия LabVIEW: 20
- Благодарил (а): 57 раз
- Поблагодарили: 9 раз
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
Я, наверное, описывать подробно алгоритм не буду, там и так видно.
На первом этапе муравьи просто ищут еду, а если нашли, то начинают таскать домой. Если в клетках 3*3 нет меток, то муравей поставит метку, неся еду. У каждого муравья существует некий параметр ("храбрость"), который отвечает за количество шагов вне муравейника. После возвращения муравья домой, этот параметр увеличивается.
На втором этапе добавилось несколько правил:
1) если муравей нашёл еду по метке, то он только таскает еду;
2) если муравей нашёл еду сам, то существует 33% вероятность, что он оставит метку, если её ещё нет именно в том месте, где пойдет он (плюс соседние клетки);
3) параметр "храбрость" увеличивается не так сильно между заходами, и если муравей отдалился от муравейника больше чем на половину диагонали квадрата со стороной M (+10%), то "храбрость" будет уменьшаться с каждым заходом пока не станет меньше 500, затем снова начнет увеличиваться;
4) добавилось состояние (т.е. вернулось), отвечающее за поиск еды, если муравей вернулся на место кучки, а еды не нашёл.
На третьем этапе увеличение параметра "храбрость" происходит ещё медленнее и убралось +10% к расстоянию, после отдаления на которое "храбрость" начинает уменьшаться. Если в куче еды оставалось менее 10 полных загрузок (2550) еды, то отключалось состояние "поиск еды" (пункт 4 на втором этапе).
Так же на втором и третьем этапах добавились коэффициенты к скорости, хотя на последнем этапе это не помогло, и муравьи "зависали"
Запускать через test many ants.vi
На первом этапе муравьи просто ищут еду, а если нашли, то начинают таскать домой. Если в клетках 3*3 нет меток, то муравей поставит метку, неся еду. У каждого муравья существует некий параметр ("храбрость"), который отвечает за количество шагов вне муравейника. После возвращения муравья домой, этот параметр увеличивается.
На втором этапе добавилось несколько правил:
1) если муравей нашёл еду по метке, то он только таскает еду;
2) если муравей нашёл еду сам, то существует 33% вероятность, что он оставит метку, если её ещё нет именно в том месте, где пойдет он (плюс соседние клетки);
3) параметр "храбрость" увеличивается не так сильно между заходами, и если муравей отдалился от муравейника больше чем на половину диагонали квадрата со стороной M (+10%), то "храбрость" будет уменьшаться с каждым заходом пока не станет меньше 500, затем снова начнет увеличиваться;
4) добавилось состояние (т.е. вернулось), отвечающее за поиск еды, если муравей вернулся на место кучки, а еды не нашёл.
На третьем этапе увеличение параметра "храбрость" происходит ещё медленнее и убралось +10% к расстоянию, после отдаления на которое "храбрость" начинает уменьшаться. Если в куче еды оставалось менее 10 полных загрузок (2550) еды, то отключалось состояние "поиск еды" (пункт 4 на втором этапе).
Так же на втором и третьем этапах добавились коэффициенты к скорости, хотя на последнем этапе это не помогло, и муравьи "зависали"
Запускать через test many ants.vi
-
IvanLis
- guru
- Сообщения: 5462
- Зарегистрирован: 02 дек 2009, 17:44
- Награды: 7
- Версия LabVIEW: 2015, 2016
- Откуда: СССР
- Благодарил (а): 28 раз
- Поблагодарили: 86 раз
Re: Олимпиада 2020 обсуждение алгоритмов
Сделал краткое описание алгоритма первого этапа.
В архиве присутствуют незадействованные функции, которые остались от не вошедших в финальную версию разработок, некоторые из них могут не работать, так что не ругайтесь.
Надеюсь не утомил своей писаниной. Описание 2 и 3 этапов сделаю позже.
В архиве присутствуют незадействованные функции, которые остались от не вошедших в финальную версию разработок, некоторые из них могут не работать, так что не ругайтесь.
Надеюсь не утомил своей писаниной. Описание 2 и 3 этапов сделаю позже.
Знание нескольких принципов освобождает от знания многих фактов!
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
Правила форума
Как добавить в сообщение картинку или файл
Конвертация / версий (форматов) VI
Как правильно задать вопрос...
-
- professor
- Сообщения: 3393
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 172 раза
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
А что даёт возвращение?
Если я правильно понимаю, в муравейнике нет данных о найденной еде. Тогда для чего муравей бегает домой?
-
alerm
- leader
- Сообщения: 682
- Зарегистрирован: 02 май 2012, 21:28
- Награды: 1
- Версия LabVIEW: 20
- Благодарил (а): 57 раз
- Поблагодарили: 9 раз
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
Ну... тут несколько причин: чтобы муравьи бесконечно не убегали от дома, а также возможность введения усталости или голода.
-
- professor
- Сообщения: 3393
- Зарегистрирован: 31 июл 2011, 23:05
- Награды: 2
- Версия LabVIEW: 12-18
- Благодарил (а): 49 раз
- Поблагодарили: 172 раза
- Контактная информация:
Re: Олимпиада 2020 обсуждение алгоритмов
Усталость и голод реально были претендентами в последних турах :)
-
- Похожие темы
- Ответы
- Просмотры
- Последнее сообщение
-
- 2 Ответы
- 567 Просмотры
-
Последнее сообщение jane_wild