Pour la science № 454 — rotor-router
Sep. 1st, 2015 11:32 am![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
green_frRotor-router — удивительное дело, нельзя поставить ссылку на Википедию, придётся самому описывать. Представим себе бесконечное поле в клеточку. В одну из клеточек (центр, начало) ставим маркер направления, например «север». Затем в эту же точку запускаем «агента». Агент действует следующим образом: если на клеточке, куда он попал, стоим маркер направления, то он поворачивает маркер на 90° и идёт в указанном направлении. А если он попадает на клеточку, где нет маркера. то он ставит там маркер «север» и пропадает. Затем мы запускаем следующего агента в центр, и т.д.
Механизм прост как две копейки, но результат, мягко говоря, удивительный. Во-первых, все агенты рано или поздно пропадают, никто не крутится бесконечно. Во-вторых, все клеточки рано или поздно получают свои маркеры, ни одна не забыта. В-третьих — очень скоро занятая маркерами зона принимает форму круга, и чем дальше, тем ближе эта форма к идеальному кругу (вот здесь можно полюбоваться на результаты, позумить, поискать интересные шаблоны).
Хороший пример, зачем программисту нужна математика — для эффективного моделирования лучше использовать теорему о коммутативности: если запустить агента А1 в точку Т1, а после него агента А2 в точку Т2, то конечный результат будет в точности таким же, как если бы сначала запустили А2, а потом А1. То есть, можно запускать новых агентов, не дожидаясь, пока пропадут старые (если в этом месте вы задумались, а зачем вообще программисту может понадобиться моделировать всё это, авторы пишут, что этот механизм очень похож на то, как «общаются» муравьи / термиты при постройке муравейника — каждый муравей занят тем, о чём ему говорит его непосредственное окружение, но он же и изменяет это окружение таким образом, чтобы в итоге получалось что-то согласованное).
Ещё интересный вариант для графов. Берём произвольный связный граф, расставляем в каждой вершине по маркеру направления (на одно из рёбер, выходящих из этой вершины) и запускаем агента. После какого-то (конечного) периода брожения по графу агент приводит его в стационарное состояние, в котором начинает описывать полные круги. То есть, проходит по каждому ребру два и только два раза (в разных направлениях — если представить каждое ребро как два ориентированных, то за один цикл агент будет проходить по одному разу по каждому ребру). Прекрасная задачка по информатике для школьников — поиск выхода из лабиринта, например. Ну и в жизни может пригодиться — всегда носите с собой мелок в кармане!
Механизм прост как две копейки, но результат, мягко говоря, удивительный. Во-первых, все агенты рано или поздно пропадают, никто не крутится бесконечно. Во-вторых, все клеточки рано или поздно получают свои маркеры, ни одна не забыта. В-третьих — очень скоро занятая маркерами зона принимает форму круга, и чем дальше, тем ближе эта форма к идеальному кругу (вот здесь можно полюбоваться на результаты, позумить, поискать интересные шаблоны).
Хороший пример, зачем программисту нужна математика — для эффективного моделирования лучше использовать теорему о коммутативности: если запустить агента А1 в точку Т1, а после него агента А2 в точку Т2, то конечный результат будет в точности таким же, как если бы сначала запустили А2, а потом А1. То есть, можно запускать новых агентов, не дожидаясь, пока пропадут старые (если в этом месте вы задумались, а зачем вообще программисту может понадобиться моделировать всё это, авторы пишут, что этот механизм очень похож на то, как «общаются» муравьи / термиты при постройке муравейника — каждый муравей занят тем, о чём ему говорит его непосредственное окружение, но он же и изменяет это окружение таким образом, чтобы в итоге получалось что-то согласованное).
Ещё интересный вариант для графов. Берём произвольный связный граф, расставляем в каждой вершине по маркеру направления (на одно из рёбер, выходящих из этой вершины) и запускаем агента. После какого-то (конечного) периода брожения по графу агент приводит его в стационарное состояние, в котором начинает описывать полные круги. То есть, проходит по каждому ребру два и только два раза (в разных направлениях — если представить каждое ребро как два ориентированных, то за один цикл агент будет проходить по одному разу по каждому ребру). Прекрасная задачка по информатике для школьников — поиск выхода из лабиринта, например. Ну и в жизни может пригодиться — всегда носите с собой мелок в кармане!
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2015-09-01 10:36 am (UTC)no subject
Date: 2015-09-01 11:52 am (UTC)no subject
Date: 2015-09-01 11:57 am (UTC)no subject
Date: 2015-09-01 01:12 pm (UTC)Здесь - нет никакого дифура, есть алгоритм, похожий на машину Тюринга, но попроще, а вместо линейной ленты - двумерная решётка. Число направлений - 4. Число стартовых клеток потенциально бесконечно. Результат - стрелка в одном из 4 направлений в каждой клетке решётки. Верно, что эти стрелки после пары миллионов шагов организуются в линии, но линии с бифуркациями, и если эти линии и являются решениями какого-то дифура (нелинейного обязательно, поскольку бифуркации), то не похоже, чтобы до этого дифура можно было добраться.
no subject
Date: 2015-09-01 01:58 pm (UTC)no subject
Date: 2015-09-01 04:36 pm (UTC)no subject
Date: 2015-09-01 07:45 pm (UTC)no subject
Date: 2015-09-01 08:09 pm (UTC)no subject
Date: 2015-09-02 08:49 am (UTC)no subject
Date: 2015-09-01 03:38 pm (UTC)no subject
Date: 2015-09-01 03:51 pm (UTC)no subject
Date: 2015-09-01 03:58 pm (UTC)no subject
Date: 2015-09-01 04:23 pm (UTC)no subject
Date: 2015-09-01 07:42 pm (UTC)Я правильно помню, что "нехороший человек" - это "акунин"?
no subject
Date: 2015-09-01 08:11 pm (UTC)no subject
Date: 2015-09-01 05:00 pm (UTC)