November 30th, 2009

glider

Задачка

Сегодня, когда разбирался с транзакционной памятью, наткнулся на такое понятие как лайвлок (не читайте пока что о нем, ибо рядом наверняка будет решение сабжа поста) и почитал о средствах его разрешения. Алгоритм простенький, но изящный, и он мне так понравился, что я придумал задачку.

На плоскости, разлинеенной на зеленые квадратики 1х1, в четыре этапа создается лабиринт. На первом этапе выбираются случайные натуральные числа N и M, и случайный прямоугольник NxM закрашивается черным цветом. На втором этапе создаются коридоры лабиринта - квадраты, окрашенные черным, случайным образом красятся в белый цвет, но так, что в результате в лабиринте нет ни одного белого квадрата 2х2. На третьем этапе создаются двери - бесконечно тонкие полоски, разделяющие белые квадраты лабиринта по линии соприкосновения, которые открываются "в стенку", то есть параллельно линии соприкосновения квадратов. На четвертом этапе создаются выемки в стенах - для каждой клетки, которая примыкает к некоторой двери, рядом белым цветом закрашивается черная клетка, но так, чтобы эта черная, т.е. уже белая, клетка больше не примыкала ни к одной белой клетке (т.е. чтобы мы таким образом не пробили дырок в стенках, через которые можно было бы пролазить между коридорами). Если такой клетки нет, то начинаем создание лабиринта заново. Таким образом, рано или поздно получим двумерный лабиринт NxM, разбитый на единичные квадраты. У лабиринта несколько входов - белых квадратов, смежных с зелеными квадратами внешней плоскости. Если существует пара входов, между которыми можно пройти по белым квадратам, то лабиринт называется проходимым.

На плоскости двигаются по случайным маршрутам некоторое количество роботов, каждый размером 1х1 и каждый находится целиком в некотором единичном квадрате. Двигаются = каждый такт времени робот может либо попытаться передвинуться в соседний по горизонтали или вертикали единичный квадрат зеленого или белого цвета, либо остаться на месте. Если робот попробовал передвинуться, но целевая клетка занята другим роботом, то он остается на месте и понимает, что ему помешал другой робот. Все роботы знают устройство лабиринта, но не знают, где находятся другие роботы.

Время от времени в случайном порядке и в случайные моменты времени в лабиринт заходят роботы - каждый двигается по случайному маршруту, состоящему из белых квадратов, соединяющему какие-то два различных входа. Так как ширина каждой двери и каждого коридора равна ширине робота, то, например, пройти в одну и ту же дверь два робота одновременно не смогут. Но около каждой двери с обеих сторон в стенах есть углубление, в котором робот может спрятаться, освободив проход.

***

Задача: придумать алгоритм A (одинаковый для всех роботов), который бы исключил возможность неразрешимых заторов в любом проходимом лабиринте, то есть, чтобы при любой валидной окружающей среде Env0 (валидная среда включает в себя устройство проходимого лабиринта, раскладку роботов, время их появления и их маршруты) для каждого момента времени T1 существовал такой момент времени T2, что P{f(A, Env0, T2) > f(A, Env0, T1)} = 1, где f(A, Env, T) - функция, определяющая количество роботов, которые при использовании алгоритма A на момент времени T в раскладке событий, задаваемых Env, преодолели лабиринт, задаваемый Env, а P{...} обозначает вероятность.

Дополнительное условие №1. Роботы не могут общаться друг с другом, поэтому, столкнувшись друг с другом у двери, они поймут, что мешают друг другу, но не смогут договориться о том, кто кого пропустит, став в рядом находящуюся выемку.

Дополнительное условие №2. Не надо предлагать решения, которые заключаются в том, что роботы или двери как-то упорядочиваются. Пример: 1) каждой двери назначаем уникальный ключ, 2) храним ключи в системе и организуем доставку ключей по требованию (если два робота в один и тот же такт времени запросили один и тот же ключ, то ключ доставляется случайному), 3) оснащаем робота функцией обращения к системе за ключами, 4) перед входом в лабиринт запрашиваем ключи от всех дверей на пути робота (ведь мы заранее знаем карту), упорядочив двери, чтобы избежать дедлока. Эти решения хорошие, но есть более изящный подход, который не требует упорядочения.

***

Ядро решения задачи: http://bit.ly/4Xk1r. Успехов - наверняка, есть алгоритмы, которые по пропускной способности лабиринта еще круче, чем тот, что в слинкованном решении! Надеюсь, не испортил ваш мыслительный процесс постановкой задачи.