Складання алгоритмів в рамках тієї чи іншої класичної алгоритмічної моделі (машини Тьюринга і Поста, нормальні алгоритми Маркова, лічильникові машини Мінського і т. д.) сміливо можна відносити до ненормального програмування в силу виняткової мінімальності виразних засобів цих моделей.
Не винятком з даного правила є і така відносно нова алгоритмічна модель, як мембранні системи або 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) займатися не будемо, щоб не захаращувати основну ідею. За рахунок того, що число мембран, в яких виконується пошук, досить велике, ймовірність того, що в графі є гамільтонів шлях, а алгоритм його не виявив, може виявитися досить маленькою (точніше, цією ймовірністю ми може керувати).
Вхідні дані алгоритму: спочатку є всього одна мембрана, в якій розташовується а) набір символів 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). Отже, якщо після T + 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 обсягів Землі (щось мені здається, що це число перевищує оцінюваний об'єм всесвіту). Так що, безкоштовних тістечок нам виявити так і не вдалося. Зате ми познайомилися з новою алгоритмічною моделлю і з ще одним досить нетривіальним (не побоюся цього слова - ненормальним) способом «програмування».
Спасибі всім за увагу!