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

  • Renault Megane Estate PHEV

    Вторая часть, как выразился _not_me, рекламного поста про нашу машинку :-) Потому что водить её оказалось одновременно и удобно,…

  • Стоимость электричества для машины

    У нас с начала мая новая машинка, я  писал, что интересно будет посмотреть на цифры, а тут мы как раз съездили в Италию, данных набралось. Во-первых…

  • Board Game Arena и Queimada

    На BGA обнаружился когда-то купленный у Эдит Saint-Petersbourg. Симпатичная игрушка, основная сложность в которой заключается в понимании момента,…

  • 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

  • Renault Megane Estate PHEV

    Вторая часть, как выразился _not_me, рекламного поста про нашу машинку :-) Потому что водить её оказалось одновременно и удобно,…

  • Стоимость электричества для машины

    У нас с начала мая новая машинка, я  писал, что интересно будет посмотреть на цифры, а тут мы как раз съездили в Италию, данных набралось. Во-первых…

  • Board Game Arena и Queimada

    На BGA обнаружился когда-то купленный у Эдит Saint-Petersbourg. Симпатичная игрушка, основная сложность в которой заключается в понимании момента,…