green_fr (green_fr) wrote,
green_fr
green_fr

Pour la science № 454 — rotor-router

Rotor-router — удивительное дело, нельзя поставить ссылку на Википедию, придётся самому описывать. Представим себе бесконечное поле в клеточку. В одну из клеточек (центр, начало) ставим маркер направления, например «север». Затем в эту же точку запускаем «агента». Агент действует следующим образом: если на клеточке, куда он попал, стоим маркер направления, то он поворачивает маркер на 90° и идёт в указанном направлении. А если он попадает на клеточку, где нет маркера. то он ставит там маркер «север» и пропадает. Затем мы запускаем следующего агента в центр, и т.д.

Механизм прост как две копейки, но результат, мягко говоря, удивительный. Во-первых, все агенты рано или поздно пропадают, никто не крутится бесконечно. Во-вторых, все клеточки рано или поздно получают свои маркеры, ни одна не забыта. В-третьих — очень скоро занятая маркерами зона принимает форму круга, и чем дальше, тем ближе эта форма к идеальному кругу (вот здесь можно полюбоваться на результаты, позумить, поискать интересные шаблоны).

Хороший пример, зачем программисту нужна математика — для эффективного моделирования лучше использовать теорему о коммутативности: если запустить агента А1 в точку Т1, а после него агента А2 в точку Т2, то конечный результат будет в точности таким же, как если бы сначала запустили А2, а потом А1. То есть, можно запускать новых агентов, не дожидаясь, пока пропадут старые (если в этом месте вы задумались, а зачем вообще программисту может понадобиться моделировать всё это, авторы пишут, что этот механизм очень похож на то, как «общаются» муравьи / термиты при постройке муравейника — каждый муравей занят тем, о чём ему говорит его непосредственное окружение, но он же и изменяет это окружение таким образом, чтобы в итоге получалось что-то согласованное).

Ещё интересный вариант для графов. Берём произвольный связный граф, расставляем в каждой вершине по маркеру направления (на одно из рёбер, выходящих из этой вершины) и запускаем агента. После какого-то (конечного) периода брожения по графу агент приводит его в стационарное состояние, в котором начинает описывать полные круги. То есть, проходит по каждому ребру два и только два раза (в разных направлениях — если представить каждое ребро как два ориентированных, то за один цикл агент будет проходить по одному разу по каждому ребру). Прекрасная задачка по информатике для школьников — поиск выхода из лабиринта, например. Ну и в жизни может пригодиться — всегда носите с собой мелок в кармане!
Tags: pour la science
Subscribe

  • Cour de justice de la République

    Прочитал в Le Monde о том, что во Франции есть специальный суд для того, чтобы судить членов правительства за преступления, которые те совершили…

  • Queimada

    Ещё несколько игрушек из нашей ассоциации. Жизнь вернулась, люди собираются как минимум два раза в неделю (вторник + пятница), а иногда ещё…

  • Louvre : Le Corps et l'Âme

    В Лувре была выставка, посвящённая итальянской скульптуре Возрождения. Мастерская Мантенья, гравюра 1495 года. Это не скульптура, но почти что —…

  • Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments

  • Cour de justice de la République

    Прочитал в Le Monde о том, что во Франции есть специальный суд для того, чтобы судить членов правительства за преступления, которые те совершили…

  • Queimada

    Ещё несколько игрушек из нашей ассоциации. Жизнь вернулась, люди собираются как минимум два раза в неделю (вторник + пятница), а иногда ещё…

  • Louvre : Le Corps et l'Âme

    В Лувре была выставка, посвящённая итальянской скульптуре Возрождения. Мастерская Мантенья, гравюра 1495 года. Это не скульптура, но почти что —…