Как стать автором
Обновить

Поиск гамильтонова пути с помощью мембранной системы за полиномиальное время

Ненормальное программирование
Составление алгоритмов в рамках той или иной классической алгоритмической модели (машины Тьюринга и Поста, нормальные алгоритмы Маркова, счетчиковые машины Минского и т.д.) смело можно относить к ненормальному программированию в силу исключительной минимальности выразительных средств этих моделей. Не исключением из данного правила является и такая относительно новая алгоритмическая модель, как мембранные системы или P-системы, придуманная румынским ученым Георгием Пауном чуть более десяти лет назад. Целью этого нововведения было исследование вычислительных возможностей клеткоподобных структур (имеются в виду биологические клетки), а вообще вся эта деятельность была инспирирована знаменитым опытом Адлемана по решению задачи о поиске Гамильтонова пути с помощью ДНК-вычислений. Как это ни странно, но данный топик посвящен как раз решению (к сожалению, виртуальному) той же самой задачи, но уже с помощью простейшей мембранной системы. Итак, под катом читатель найдет 1) краткое описание того, что такое мембранные системы; 2) как «программировать» такое «железо»; 3) мембранный алгоритм решения задачи о гамильтоновом пути, обладающий полиномиальным временем выполнения.

Мембранная система


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

По сути, мембранная система представляет собой древовидную структуру, в которой роль корня играет либо среда, либо скин-мебрана. Мембрана A является дочерней по отношению к мембране B, если А непосредственно вложена в B. Мембранные системы обычно записываются в виде строки, в которых сами мембраны обозначаются скобками (важное замечание – порядок расположения объектов внутри скобок не играет абсолютно никакой роли). Рассмотренная выше система, например, может быть записана следующим образом: [0baha[1I]1Hrb[2lvoe]2ra]0 или так [0ahra[2ovel]2Hrbb[1I]1a]0 или вообще вот так:
[0[1I]1[2love]2Habrahabr]0

Эволюция мембранной системы


Любая мембранная система является динамической, т.е. изменяется со временем, при этом говорят об ее эволюции. Законы (правила) эволюции определяет разработчик системы, и эти правила являются ее неотъемлемой частью. В литературе, посвященной мембранным вычислениям, имеется много типов таких правил. Для наших целей будет достаточно правил только трех основных типов: эволюция внутримембранных мультимножеств; перенос символов вовне; деление мембран.
Эволюция мультимножеств описывается правилами вида A → B, где A и B – две строки, представляющие собой некоторые подмножества символов (поэтому порядок расположения символов в этих строках не важен). Например, aab → bc. Смысл такого рода правил заключается в том, что если в некоторой мембране имеется комбинация символов A, то она должна быть заменена на комбинацию B. Имеются противопоказания нюансы. Во-первых, действует принцип максимального параллелизма – все подстановки, которые могут быть применены, должны быть применены. Во-вторых, если имеется несколько конкурирующих правил, то выбор одного из них выполняется недетерминировано, т.е. случайно. В-третьих, иногда для разрешения подобных конфликтов на множестве правил вводится приоритет, т.е. отношение частичного порядка. Кстати, мембранные системы с приоритетом правил как раз и являются алгоритмически универсальными моделями, совместимыми с машиной Тьюринга (но мы приоритет использовать не будем).
Символы в процессе эволюции системы могу переноситься между мембранами, в частности, вывод символов из мембраны в окружающий ее регион описывается следующим правилом [A] → []B. Например, [ab] → c. Смысл такого правила заключается в том, что если в некоторой мембране имеется комбинация символов A, то она выносится из мембраны и превращается в комбинацию B.
Наконец, самая интересная операция (позволяющая реализовывать алгоритмы, типа описываемого ниже) – деление мембран. Правило деления мембраны имеет вид [a] → [B][C] (здесь a – некоторый символ, B и C – строки). Например, [x] → [aa][b]. Смысл этой операции: если внутри мембраны образовался символ a, то это мембрана делится (сначала в ней выполняются все правила предыдущих двух типов) на две, в первой символ a заменяется на комбинацию B, во второй – на C.
Заметим, что каждое правило, в принципе, может быть привязано к конкретной мембране (с заданной меткой), однако, для наших целей такое усложнение модели, к счастью, не потребуется.
Предполагается, что на каждом такте (дискретного времемени) в системе выполняются все те правила, которые могут быть выполнены в данный момент времени. Вкупе с алгоритмической универсальностью это означает, что мембранные системы могут рассматриваться как параллельная вычислительная модель. Причем степень параллелизма в такой модели является динамической — чем больше объектов в системе, тем (в среднем) больше количество одновременно срабатываемых правил. Этим мембранные системы выгодно отличаются от, например, параллельных машин Тьюиринга.

Задача о гамильтоновом пути


Пусть задан ориентированный граф G и в этом графе задана стартовая вершина. Будем передвигаться по ребрам графа согласно их направлениям (против шерсти стрелки ходить нельзя). Если существует такой маршрут обхода графа, который включает в себя вершины ровно по одному разу, то такой маршрут и называется гамильтоновым путем. Если из последней вершины гамильтонова пути можно перейти к стартовой вершине, то такой путь называется гамильтоновым циклом. Собственно, рассматриваемая ниже задача формулируется так: имеется ли в заданном графе G гамильтонов путь, начинающийся с u-ой вершины? Таким образом, решением задачи является всего один бит информации – путь существует (1) или не существует (0). Это классическая NP-полная задача (хотя, чаще всего она и рассматривается, как задача поиска гамильтонова цикла), соответственно, в настоящее время неизвестен ни один полиномиальный алгоритм ее решения.
Пронумеруем все вершины графа от 1 до n. Не ограничивая общности рассуждений (такая стандартная отмазка отговорка), будем считать, что стартовая вершина является первой. Сам граф будем задавать с помощью набора (строки) символов, соответствующих дугам графа. Каждая дуга u→v задается специальным символом вида Auv. Заметим, что Auv — это один символ (изображение которого составлено из нескольких других символов)! Например, граф на рисунке справа задается символьной строкой A=A13A21A32A24A43. Кстати, этот граф содержит в себе единственный гамильтонов путь, исходящий из первой вершины: 1→3→2→4.

Мембранный алгоритм


Идея алгоритма следующая. На первом шаге создаем (с помощью операции деления) достаточно большое одинаковых мембран, в которых закодированы условия задачи (т.е. граф G). На втором шаге, внутри каждой мембраны производится случайный поиск гамильтонова пути – делается максимум n-1 итерация, на каждой итерации делается попытка продлить текущий путь с помощью выбора случайной исходящей дуги из текущей вершины. Если попытка неудачная, то процесс эволюции внутри данной мембраны останавливается. В принципе, в этом случае можно было бы и удалить всю мембрану, но мы такой ерундой (написанием garbage collector’а) заниматься не будем, чтобы не загромождать основную идею. За счет того, что число мембран, в которых выполняется поиск, достаточно велико, вероятность того, что в графе имеется гамильтонов путь, а алгоритм его не обнаружил, может оказаться достаточно маленькой (точнее, этой вероятностью мы может управлять).
Входные данные алгоритма: изначально имеется всего одна мембрана, в которой располагается а) набор символов A, представляющий собой граф, в котором мы ищем путь из первой вершины; б) список непосещенных вершин, заданный символами U2, U3,..., Un (первая вершина считается уже посещенной); в) счетчик делений DT. Например, для показанного выше графа исходная мембрана имеет вид [DTU2U3U3A13A21A32A24A43].
Первый шаг – создание нужного количества идентичных мембран. Это достигается с помощью следующего правила:
1: [Di] → [Di-1] [Di-1], i = T,...,1

Применение этого правила приводит к удвоению каждой мембраны, при этом, счетчик делений уменьшается на единицу. Несложно догадаться, что число мембран в результате будет увеличиваться экспоненциально – 1, 2, 4, 8 и т.д. После T итераций мы будем иметь 2T идентичных мембран, у которых счетчик делений будем равен D0. Появление в мембране этого символа запускает второй шаг алгоритма – построение гамильтонова пути. Этот шаг реализуется следующими четырьмя правилами.
2: D0 → X1L1
3: XiAij → Yj, i, j = 1,...,n
4: YjUj → Zj, j = 1,...,n
5: ZjLk → XjLk+1, j = 1,...,n, k = 1,...,n-1

Важное замечание: когда мы говорим, например, о правиле 3, мы подразумеваем целый набор правил, для всех возможных символов Xi и Aij. Т.е. под «как бы» правилом 3 скрываются на самом деле n2 «настоящих» правил. Теперь краткое описание того, что делают указанные четыре правила. Правило 2: запуск второго шага алгоритма, текущая вершина – первая (символ X1), символ L1 означает, что длина текущего пути пока равна единице. Правило 3: находясь в вершине с меткой Xi, делаем случайный переход по какой-нибудь исходящей из этой вершины дуге. Правило 4: если вершина, в которую мы перешли, еще не посещалась, то переход принимается. Правило 5: меняем текущую вершину и увеличиваем на единицу длину текущего пути.
Если в результате применения правила номер 3 мы оказались в вершине, которая уже посещалась ранее, то все, кина больше не будет данная мембрана перестает эволюционировать, потому что ни одно из правил к ее набору символов не применимо. Этой мембране не повезло. Ничего, значит повезет другим! Если конечно в графе имеется гамильтонов цикл. Если такого цикла нет, то не более чем через n итераций второго шага вся жизнь в нашей мембранной системе замрет. А что же произойдет, если какой-нибудь мембране удастся пройти весь путь? В этом случае в данной мембране будет сгенерирован символ Ln, который по сути и означает, что пройден путь длиной в n вершин, причем никакая вершина не посещалась дважды. Значит, появление такого символа является сигналом успешного поиска. Чтобы упростить распознавание ответа, добавим в систему последнее правило.
6: [Ln] → []S

Здесь S обозначает успех (от success). Итак, если после Т+n итераций алгоритма в среде, окружающей наши мембраны, появится хотя бы один символ S, то граф является гамильтоновым, если нет, то с некоторой вероятностью P этот граф негамильтонов (нам банально могло не повезти, и несмотря на то, что в графе есть все-таки искомый путь, ни одна мембрана его так и не нашла). Настал черед разобраться с этой вероятностью, а заодно и с пока неопределенным параметром T.

Epic fail и его вероятность


Сейчас нам придется немного позаниматься математикой. Рассмотрим худший случай неудачного поиска, когда в графе имеется всего один гамильтонов путь. Более-менее очевидно, что при случайном выборе исходящих дуг вероятность обнаружения этого пути (для отдельно взятой мембраны) больше, чем q=1/nn, т.к. на каждой итерации у нас имеется максимум n исходящих дуг, из которых как минимум одна входит в искомый путь. Всего итераций n-1, для простоты формулы мы увеличим это число до n. Тогда вероятность p не обнаружения этого же пути меньше, чем p=1-1/nn. Кажется, что эта величина подозрительно похожа на единицу, но все же там имеется небольшой люфт, которым мы и воспользуемся. Вспомним, что у нас имеется не одна мембрана, а сразу M=2T таких мембран. И нас интересует вероятность того, что ни одна из них не найдет наш путь. Имеем серию из M опытов, выполняемых по схеме Бернулли – с вероятностью успеха q и неудачи p. Известно, что число успехов в такой серии подчиняется биномиальному распределению, в частности, вероятность того, что не будет ни одного успеха (epic fail) оказывается равной P=pM. И вот торжественный момент – выберем M равным Knn, где K – некоторый положительный параметр. Тогда, P=(1-1/M)KM. А т.к. M является весьма большим уже для небольших значений n, то можно применить второй замечательный предел и окажется, что величина P хорошо описывается формулой P=e-K. Например, для K = 100, вероятность не обнаружения имеющегося гамильтонова пути будет равна приблизительно P=10-44, т.е. это событие (epic fail) оказывается практически невероятным. Да, это все прекрасно, но ведь и M (число мембран) тоже оказывается не маленьким. Но, вспомним, что M=2T, а T – это тот самый параметр, который управляет первым шагом алгоритма. Так вот, из соотношения 2T=Knn легко выводится, что T = O(nlog2n). А это, в свою очередь, как раз и означает, что суммарная сложность всего алгоритма является линейно-логарифмической, а следовательно, полиномиальной. Что и требовалось показать! При этом, вероятность некорректной работы алгоритма управляется параметром K, который практически не влияет на сложность алгоритма.

Вместо заключения


Во-первых, если мы зафиксируем некоторое значение n и по этому значению 1) вычислим T; 2) сформируем набор правил, как это было описано выше, то построенная таким образом мембранная система будет решать задачу поиска гамильтонова пути в любом графе, число вершин которого не превышает n. Т.е. такая система является в самом деле алгоритмом (программой), а не схемой решения одного единственного экземпляра задачи. При этом, алфавит данной системы будет полиномиальным относительно n.
Во-вторых, если на секунду отвлечься от магического словосочетания «полиномиальный алгоритм решения NP-полной задачи», то сразу станет очевидно, что мы просто подменили временную экспоненциальность на пространственную, т.к. каждой мембране нужно свое место под солнцем — набор байтов в памяти компьютера или физический объем, если мембраны реализуются клетками или молекулами (как в опыте Адлемана). Если предположить, что одна мембрана занимает объем равный объему атома водорода (недостижимая пока граница) и положить K=1, то суммарный объем мембран после первого шага алгоритма для небольшого графа из 100 вершин составит порядка 10900 объемов Земли (что-то мне кажется, что это число превышает оцениваемый объем вселенной). Так что, бесплатных пирожных нам обнаружить так и не удалось. Зато мы познакомились с новой алгоритмической моделью и с еще одним весьма нетривиальным (не побоюсь этого слова — ненормальным) способом «программирования».

Спасибо всем за внимание!
Теги:гамильтонов путьмембранная системаNP-полная задачаполиномиальный алгоритм
Хабы: Ненормальное программирование
Всего голосов 82: ↑79 и ↓3 +76
Просмотры4.7K

Похожие публикации

Лучшие публикации за сутки