September 1st, 2015

green_fr

Pour la science № 454 — rotor-router

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

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

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

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