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

  • BNF : Le monde en sphères

    Я узнал про эту выставку давно, когда она была в Абу-Даби. Делали её Лувр вместе с BNF, поэтому после Эмиратов её  привезли в Париж. Тема мне очень…

  • La saga des calendriers

    Не помню, где я наткнулся на эту книгу — издание моего любимого журнала, но достаточно старое, вряд ли его реклама могла быть в недавних выпусках.…

  • Гравитационный манёвр

    В продолжение предыдущего поста про гравитацию. Внезапно осознал, что гравитационный манёвр, которым мы так восхищались, когда следили…

  • Post a new comment

    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

  • BNF : Le monde en sphères

    Я узнал про эту выставку давно, когда она была в Абу-Даби. Делали её Лувр вместе с BNF, поэтому после Эмиратов её  привезли в Париж. Тема мне очень…

  • La saga des calendriers

    Не помню, где я наткнулся на эту книгу — издание моего любимого журнала, но достаточно старое, вряд ли его реклама могла быть в недавних выпусках.…

  • Гравитационный манёвр

    В продолжение предыдущего поста про гравитацию. Внезапно осознал, что гравитационный манёвр, которым мы так восхищались, когда следили…