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

    Составление алгоритмов в рамках той или иной классической алгоритмической модели (машины Тьюринга и Поста, нормальные алгоритмы Маркова, счетчиковые машины Минского и т.д.) смело можно относить к ненормальному программированию в силу исключительной минимальности выразительных средств этих моделей. Не исключением из данного правила является и такая относительно новая алгоритмическая модель, как мембранные системы или 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 объемов Земли (что-то мне кажется, что это число превышает оцениваемый объем вселенной). Так что, бесплатных пирожных нам обнаружить так и не удалось. Зато мы познакомились с новой алгоритмической моделью и с еще одним весьма нетривиальным (не побоюсь этого слова — ненормальным) способом «программирования».
     
    Спасибо всем за внимание!
    Поделиться публикацией
    Комментарии 59
      +7
      «Папа, а с кем ты сейчас разговаривал?»
      Жму руку тому, кто это понимает.
        –8
        del
          +2
          Да ладно. Все ж понятно:
          Паун ввел ввел свою алгоритмическую модель и описал, как в ней решаются классические задачи.
          Да и к тому же эта алгоритмическая модель не вырожденная и не искусственная, а очень даже естественная и простая для понимания. Да еще и автор ее хорошо и популярно ее описал.

          Ну для людей, которые не знакомы с базовыми знаниями дискретной математики или теории сложности это возможно покажется сложным, но как подсказывает мой опыт — сложным оказывается только то, во что не хочешь вникать, а стоит разобраться — все становится ясным как день.
          +3
          Заголовок сломал мой мозг. Хабр еще торт
            –7
            ппц :(
              +5
              Спасибо, очень интересно. Похоже на эдакую смесь классического метода ветвей и границ со спуском по дереву и генетических алгоритмов.
                +4
                Кстати, да! Хотя от генетики здесь маловато чего есть, но ее применение в данном контексте напрашивается :)
                0
                Отдаленно напоминает lambda calculus, тоже по-марсиански, тоже все на подстановках.
                Как дерево мембраны в процессе вычислений выглядит не посмотреть?
                  +7
                  спасибо, ничего не понял
                    –1
                    спасибо, что сообщили
                    0
                    Стоп. А Разве тогда задача не является не-NP-полной? :)
                      +2
                      Почему-то создалось ощущение, что речь идёт о фактически цепях Маркова.
                      Вероятно, на биологических клетках это не так, но оцифровка — таки они.
                        0
                        И в этой аналогии что-то есть! Буду думать… :)
                          0
                          Кстати, такая же аналогия возникла. Недетерминированные цепи Маркова + генетические алгоритмы? :)
                          +1
                          Нет. Приведенный алгоритм (как и любой другой впрочем) решает задачу за полиномиальное время только на «удачных» для алгоритма конфигурациях. При этом если мы формализуем критерии этой конфигурации и добавим в условие задачи — она станет разрешимой за полиномиальное время. Просто зачастую при решении NP'шных задач мы реально не нуждаемся в решении для произвольных входных данных, а вот в зависимости от специфики нашых входных данных подобные алгоритмы и разрабатываются.
                            0
                            Мне кажется (более того, я уверен), что приведенный алгоритм все-таки решает задачу за полиномиальное время всегда! Правда, используя для этого слишком много пространства…
                              0
                              Обращения к памяти не мгновенные. Следовательно, если мы используем n байт памяти, а n — экспоненциально зависит от размерности входных данных, то суммарное время доступа к памяти тоже будет экспоненциально зависеть от размерности входных данных.
                                +1
                                А что Вы скажете о колонии бактерий, размер которой увеличивается по экспоненте? Просто они делают это (делятся) одновременно, не используя никаких общих ресурсов (память, энергия и т.д.), по крайней мере на начальном этапе роста… :)
                                  0
                                  А тогда у них экспоненциально увеличивается число вычислителей, т.к. каждая бактерия — независимый вычислитель. В итоге вычислительное время все равно требуется экспоненциальное.
                                    0
                                    ОК, время от получения условий задачи до его решения — полиномиально, а общее время, затраченное на решение (например, в мембрано-часах) — экспоненциально… :)
                                      +2
                                      Согласно современной физике, для нашего трехмерного пространства — при экспоненциальном увеличении числа необходимой материи — экспоненциально увеличивается расстояние до нее (в самом лучшем случае, где все пространство заполнено материей — расстояние до ближайшей материи определяется пропорционально корню третьей степени от уже использованной материи), а т.к. в данный момент не открыто возможности перемещаться или передавать информацию быстрее света — то получаем конечную скорость и экспоненциально определяемое расстояние. А следовательно и в реальном времени задача эмеет экспоненциальную сложность по времени. Это относится конечно к существующей доказанной физической теории, если ее дополнят/опровергнут — возможно я окажусь неправ, но все же алгоритм мы рассматриваем здесь и сейчас.
                                        0
                                        Уговорили! :) Кстати, интересно, а что, если пространство, в котором мы собираемся реализовать предложенный алгоритм, будет бесконечномерным? :)
                                          0
                                          Если оно все будет заполнено материей, имеет постоянную кривизну, изотропно, лоренц-инвариантно и прочая канитель — то на каждом шаге достаточно будет сделать движение вдоль произвольного направления в пространстве, чтобы найти новую материю, это математически, физически — наличие такого пространства очень сомнительно.
                                          Хотя тут я не могу гарантировать, что алгоритм выполнится за полиномиальное время, наверняка есть еще какие-то хитрые аспекты, вносящие экспоненту.
                            0
                            Является-является! :) Так как NP-полнота задача определяется не по времени ее решения, а скорее, наоборот: если задача NP-полная, то ее решение на любом последовательном вычислителе потребует экспоненциального времени.
                              +2
                              Неправда, еще никто не доказал что P!=NP.
                                0
                                А что, есть шанс? :)
                                  +1
                                  Ну, тут статей примерно 50/50 :)
                                    0
                                    Спасибо большое за ссылку, почитаю на досуге…
                            –8
                            Поставил плюс за название.
                              +2
                              Забавная модель, интересный алгоритм.
                              И что, на реальном биологическом «железе» с этим экспериментировали? Можно где-то результаты увидеть?
                                +2
                                Да, как раз с биологического «железа» все и началось, Адлеман (Adleman, кстати, тот самый, чья буковка A стоит в аббревиатуре RSA) в начале 1990-х собственоручно провел опыт по решению задачи HPP с помощью ДНК-молекул для графа с 6 вершинами. Потратив на это несколько дней. :) Ссылка в начале топика есть. Если публике будет интересно, то я мог бы про это написать…
                                  +1
                                  Интересно:)
                                    0
                                    ОК
                                0
                                «Чувак я ни**я не понял, но ты заговорил со мной и достучался до моего сердца» (с) Джей и Молчаливый Боб
                                  +3
                                  Ох уж эти громкие названия :)
                                  Конечно, алгоритм не полиномиальный. Вы не подменяли временную сложность пространственной. Корректней сказать вы разложили ее по разным вычислительным устройствам. То же самое, что использовать машину тьюринга с очень большим количесвом лент и считывающих гловок. Но сложность алгоритма от этого не меняется.

                                  В остальном, интересно, спасибо.
                                    0
                                    Ну, я же честно сказал, что полиномиальным является только время! :) Кстати, я совсем не уверен, что какая-нибудь модификация МТ (со сколь угодно большим числом головок) сможет решить данную задачу за полиномиальное время, по крайней мере, если начальные данные записаны только на одной ее ленте…
                                      0
                                      Я к тому, что само понятие сложности алгоритмов имеет смысл только если мы рассматриваем машину тьюринга (или подобное вычисл.устройство). По этому сложность алгоритма по времени, строго говоря, не полиномиальна.
                                        0
                                        Это не совсем так. Сложность алгоритма действительно обычно меряется на машине Тьюринга, просто потому что эта модель наиболее адекватно (и в то же время просто) описывает устройство современных компьютеров.
                                        Сложность можно и по другим моделям мереть. И в рамках указанной модели сложность действительно не экспоненциальная получается. Другое дело, что если мембраны эмулировать на машине Тьюринга (а другого пути у нас пока нет), то так красиво уже не получится.
                                    +9
                                      0
                                      Вещь! :)
                                        –3
                                        del
                                      +3
                                      Проблема этого алгоритма в том, что он в процессе работы создает экспоненциальное количество мембран, и например при n=1000 для его реализации не хватит всего вещества Вселенной. Кроме того, совершенно непонятно причем здесь мембранная модель, абсолютно то же самое можно реализовать и на параллельном компьютере с достаточным (экспоненциальным) количеством процессоров.
                                        0
                                        И кстати совсем не обязательно использовать вероятностный алгоритм, можно сделать и полный перебор, чтобы каждая мембрана проверяла свой путь, так временная сложность будет вообще линейной
                                          0
                                          Если не использовать вероятностный алгоритм, то придется усложнять модель, например введением приоритета операций (правил). А линейного времени (для произвольных графов) мембранному коммьюнити при решении этой задачи пока не удалось достичь, и есть подозрение, что и не удастся. Но, кто знает, может у Вас получится!
                                            +1
                                            Хм, действительно, из-за того что можно делиться только на две части любое переборное решение можно оценить снизу Theta(n*log n), из-за того что в результате может получиться n! мембран с ответами
                                              0
                                              Кстати, верное соображение! Хотя в первых работах по данной тематике рассматривались такие «мощные» операции, как деление мембран сразу на n частей — вот там-то получить линейное время вполне по силам. Правда, такая модель становится еще дальше от своего биологического прототипа…
                                        –4
                                        Мне кажется, это очень тонкий троллинг. :)
                                          +1
                                          Есть немного :)
                                          +3
                                          Я не понял двух вещей:

                                          1) Где здесь показано, что время выполнения алгоритма действительно является полиномиальной функцией от размера задачи?
                                          2) В чем причина «блaгоговейного страха» народа перед заголовком? У нас тут клуб выпускников филфака?
                                            +1
                                            1) Предпоследняя часть
                                            2) Ну, лично мне изначально не было понятно только «мембранная система», но в статье прекрасно объяснили что это
                                            0
                                            Без конкертной аппартной реализации это простое бла-бла-бла. Если реализовывать такие алгоритмы на классических ЭВМ, то временная сложность алгоритма просто заменяется на пространственную.
                                              –6
                                              del
                                                0
                                                Конкретно для поиска гамильтонова пути это далеко не самый лучший алгоритм. Кстати не знал что он мембранным называется, хотя уже использовал, спасибо что просветили )
                                                  0
                                                  Мембранный он просто потому, что реализован в рамках мембраной модели, а так (почти) обычный алгоритм полного перебора. Был бы рад (без подколок) услышать от Вас описание лучшего алгоритма!
                                                    +2
                                                    В практических целях в большинстве случаев разумнее использовать модифицированные алгоритмы поиска в глубину. Кто-то делает поиск с возвратом, кто-то поиск от разных вершин. Я предпочитаю первичное разбиение графа на сегменты, так чтобы каждый сегмент удовлетворял правилу Дирака разумеется и после нескольких циклов дробления и составления участков пути поиском в глубину снова объединяю. Я таким образом в университете решал эту задачу, можно было бы найти код, но возможно не я один так делал, с терминологией у меня к сожалению несколько печально, так что может я также не знаю название этого алгоритма )
                                                      0
                                                      Надо будет поиграться с этой идеей… Хотя, как я заметил, для распараллеливания, чем алгоритм проще, тем лучше!
                                                        +1
                                                        Вот я тоже так считаю, таким образом наибольший эффект достигается.
                                                  +1
                                                  > Кстати, мембранные системы с приоритетом правил как раз и являются алгоритмически универсальными моделями, совместимыми с машиной Тьюринга
                                                  Насколько мне помнится, и без приоритетов тоже эквивалентны универсальной машине Тьюринга. Правда я не уверен, что там не нужно какие-то другие типы правил вводить, кроме описанных вами. По крайней мере, близкая по духу идея химических абстрактных машин (в которой нет приоритетов) так точно эквивалентна.

                                                  Почему бы не перебрать все варианты, т.е. не делать алгоритм вероятностным? Алгоритм останется полиномиальным (квадратичным, по прикидкам в уме, но наверно можно и лучше).

                                                  П.С. Я бы правила-схемы 3-5 в одно объединил: Xi Aij Uj Lk -> Xj Lk+1
                                                  Оно так и понятней становится, как по мне: «Если мы в вершине i, есть дуга из нее в j, мы не были в j, и длина пути k, то переходим в j и увеличиваем длину на 1»
                                                    0
                                                    Насколько мне помнится, и без приоритетов тоже эквивалентны универсальной машине Тьюринга.
                                                    Во всех просмотренных мною статьях по этой тематике алгоритмически универсальные мембранные системы снабжались всегда какими-то дополнительными условиями, правилами и т.д. Навскидку, я помню два таких ограничения — приоритет правил и поляризация мембран (фактически, динамическая смена идентификатора мембраны). Наверное, дело в символьных мультимножествах, если их заменить на строки (упорядоченные мультимножества), то все будет пучком.
                                                    Почему бы не перебрать все варианты, т.е. не делать алгоритм вероятностным
                                                    Я по этому поводу общался с человеком, входящим в мембранное братство, у нас не получилось превзойти линейно-логарифмическое время, не вводя тех самых доп. условий — приоритета или поляризации.
                                                    Я бы правила-схемы 3-5 в одно объединил
                                                    Есть такой вариант! Но мне нравятся бинарные отношения :)

                                                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                                                  Самое читаемое