Один алгоритм комбінаторної генерації

    Комбінаторика в старших класах школи, як правило, обмежується текстовими завданнями, в яких потрібно застосувати одну з трьох відомих формул — для числа сполучень, перестановок або розміщень. У інститутських курсах з дискретної математики розповідають і про більш складні комбінаторних об'єктах — дужкових послідовностях, деревах, графах… При цьому, як правило, ставлять завдання обчислити кількість об'єктів даного типу для деякого параметра n, наприклад кількість дерев на n вершинах. Дізнавшись кількість об'єктів для фіксованого n, можна задатися і більш складним питанням: як всі ці об'єкти за розумний час пред'явити? Алгоритми, вирішальні подібного роду завдання, називаються алгоритмами комбінаторної генерації. Таким алгоритмам, наприклад, присвячена перша глава четвертого тому «Мистецтва Програмування» Дональда Кнута. Кнут дуже докладно розглядає алгоритми генерації всіх кортежів, разбиений числа, дерев та інших структур. Придумати якийсь алгоритм, що працює помірно швидко, для кожної з цих завдань нескладно, але з подальшою оптимізацією можуть виникнути серйозні проблеми.
 
У процесі написання магістерської дисертації, захищеної в Академічному Університеті , мені було потрібно вивчити і застосувати один з алгоритмів комбінаторної генерації, відповідний для особливого класу задач. Це генерація структур, на яких додатково введено деяке відношення еквівалентності. Щоб було зрозуміло, про що йде мова, я наведу простий приклад. Давайте спробуємо згенерувати всі тріангуляції шестикутника. Вийде щось таке:
 
 
 
Написати алгоритм, який поверне всі такі тріангуляції, досить нескладно. Наприклад, згодиться така процедура: фіксуємо яке-небудь ребро (нехай це буде ребро 1-6), після чого в циклі перебираємо вершини, які не є його кінцями. На поточному вершині та фіксованому ребрі будуємо трикутник, а що залишилися після цього дві області тріангуліруем рекурсивно. Якщо придивитися до виходять в результаті роботи цього алгоритму тріангуляції, то можна помітити, що багато з них майже однакові і відрізняються лише тим, як розставлені позначки (номера) вершин. Тому, корисно було б придумати алгоритм, який буде генерувати так звані непомеченние тріангуляції — ті, що зображені на наступному малюнку:
 
 
 
 
Більш формально, нехай на нашому множині об'єктів діє деякий відношення еквівалентності , розривання все безліч на класи ізоморфних один одному об'єктів. Требуется згенерувати по одному представнику з кожного класу. Ви, напевно, помітили, що дві правих тріангуляції на другому малюнку теж дуже один на одного схожі і з них можна залишити тільки одну. Насправді, все залежить від того, яке відношення еквівалентності ми обрали. Якщо вважати ізоморфними тільки ті тріангуляції, які можна накласти один на одного після повороту, то їх залишиться чотири, а якщо дозволити ще можливість перевертати шестикутник, то три.
 
Здавалося б, згенерувати по одному представнику з кожного класу нескладно: генеруємо всі об'єкти, після чого попарно тестуємо на ізоморфізм і викидаємо дублікати. На жаль, для деяких типів об'єктів це буде працювати страхітливо довго навіть для невеликих n. Задачу перевірки ізоморфізму, наприклад, двох графів, за поліноміальний час вирішувати не вміють, а значить, підпрограму, вирішальну цю задачу, бажано викликати якомога рідше. Ще один мінус запропонованого наївного підходу полягає в тому, що всі об'єкти доведеться тримати в пам'яті одночасно. При цьому, якщо почекати повільну програму, яка видає вірну відповідь, ще теоретично можна, то отримати переповнення пам'яті замість відповіді вже зовсім неприйнятно. Так що, для генерації попарно неізоморфних об'єктів потрібно скористатися якимось більш хитрим методом. Такий метод неодноразово перевідкривається для багатьох конкретних комбінаторних об'єктів (графів, дерев, разбиений), а в загальному вигляді був описаний в статті Isomorph-Free Exhaustive Generation .
 
Я розповім про цей метод на прикладі задачі, наскільки більш загальної порівняно із завданням про тріангуляції: ми будемо генерувати всі «розсічення», тобто способи розбити багатокутник не обов'язково на трикутники, а на багатокутники з числом сторін зі списку, який подається на вхід програмі.
 
Для того, щоб цей метод описати потрібно кілька формальних визначень.
 
Нехай X — деяке безліч «структур». Елементи безлічі X ми називатиме поміченими об'єктами . У нашій задачі поміченими об'єктами є розсічення, вершини яких пронумеровані проти годинникової стрілки. Структура даних для помічених розтинів проста — це списки суміжності:
 
 
public class Dissection {
    private int[][] adjacent;
  
    ...
}

 
Нехай G — деяка група перестановок, діюча на безлічі X. Це означає, що кожному позначеному об'єкту x з X і кожному елементу g групи G поставлений у відповідність інший позначений об'єкт y = g * x, причому виконані наступні властивості:
 
 
     
множитися будь-яких елементів групи h і g відповідає послідовне застосування дій до об'єкта x: h * (g * x) = (hg) * x.
 Одиниця групи e переводить кожен позначений об'єкт x сам в себе: e * x = x.
 
 
Можна показати, що всі безліч X розбивається на класи еквівалентності відносного такого ставлення: x і y еквівалентні, якщо x = g * y. У нашому першому прикладі з тріангуляції, елементи групи — повороти на 0, 60, 120, 180, 240 і 300 градусів — ділять всі безліч на чотири класи еквівалентності, елементи яких відрізняються саме своєю структурою, а не позначками вершин. Ці класи еквівалентності і були зображені на другому малюнку. Ми будемо називати ці класи непоміченими об'єктами .
 
Кожному елементу X ми зіставимо натуральне число, яке будемо називати порядком. Порядок у всіх еквівалентних об'єктів повинен бути однаковий. Ця властивість дозволяє доопределить порядок для класів еквівалентності (непомічених об'єктів): він буде дорівнює порядку будь-якого представника відповідного класу. Для нашого прикладу на малюнку, порядок — це кількість вершин в багатокутнику. У всіх непомічених об'єктів на малюнку він дорівнює шести.
 
Це були досить загальні визначення. Тепер перейдемо до визначень, специфічним для майбутнього алгоритму. Кожному поміченого об'єкту x зіставимо два безлічі — безліч нижніх об'єктів L (x) і безліч верхніх об'єктів U (x). Порядки елементів у цих множинах з визначення дорівнюють порядку x. Перш ніж дати формальні вимоги до нижнім і верхнім об'єктам, я спробую дати інтуїтивне опис. Кожен нижній об'єкт повинен містити в собі інформацію про те, як однозначно перейти від поточного об'єкту до об'єкту меншого порядку. Наприклад, нижній об'єкт-розсічення — це розсічення, в якому додатково виділено (наприклад, пофарбований в червоний колір) один з «крайніх» багатокутників, який можна від цього розсічення відрізати. Верхній об'єкт — це, навпаки, позначений об'єкт плюс інформація, що дозволяє його однозначним чином «наростити», збільшивши порядок. Верхнє розсічення, наприклад, — це розсічення, в якому одна із сторін багатокутника додатково виділена (наприклад, пофарбована в червоний колір) і на ній написано число. Подивившись на таке розсічення, ми можемо зрозуміти, до якої сторони приклеїти новий багатокутник, щоб збільшити порядок. Число сторін приклеиваемого багатокутника визначатиметься тим, яке число написано на ребрі. Цю ідею можна проілюструвати наступним малюнком, що зображує два об'єкти — нижній і верхній, що відповідають одному і тому ж розсіченню.
 
 
 
У програмі нижні і верхні розсічення представлені так:
 
 
public class LowerDissection {
    private Dissection dissection;
    private int after;
  
    ...
}

 
 
public class UpperDissection {
    private Dissection dissection;
    private int after, size;
  
    ...
}

 
Для нижнього розсічення ми зберігаємо лише номер вершини, з якої починається багатокутник, який ми збираємося видаляти. Для верхнього розсічення зберігається номер вершини, після якої потрібно буде приклеювати новий багатокутник, а так само число його сторін.
 
Можна помітити, що деякі нижні і верхні об'єкти перебувають у відношенні «відповідності»: нижньому об'єкту відповідає верхній, що виникає після того, як ми зменшили порядок способом, закодованим в нижньому об'єкті.
 
 
 
Тут нижньому об'єкту зіставляється верхній, результат видалення виділеного чотирикутника. На наступному малюнку — навпаки: до верхнього об'єкту, а точніше, до його виділеному ребру з написаною на ньому п'ятіркою, приклеюється п'ятикутник. При цьому виходить нижній об'єкт, що зберігає інформацію про те, як відкотити виконану операцію.
 
 
 
Тепер формально, що ж потрібно вимагати від згаданих конструкцій:
 
 
     
Група G діє на трьох типах об'єктів: помічених, верхніх і нижніх. Кожне з цих трьох множин замкнуто щодо дії групи (це значить, що, наприклад, подіяв елементом групи на нижній об'єкт, не можна отримати верхній — досить формальна вимога).
 Для кожного позначеного об'єкта x і елемента групи g: L (g * x) = g * L (x); U (g * x) = g * U (x) (запис g * L (x) означає, що ми застосовуємо g до кожного елементу безлічі L (x), аналогічно для g * U (x)).
 Для кожного нижнього об'єкта y, відповідне йому безліч верхніх об'єктів не порожньо.
 Якщо два нижніх об'єкта y і x еквіваленти (тобто, y = g * x), то будь-які два відповідних їм верхніх об'єкта теж еквівалентні.
 Якщо два верхніх об'єкта y і x еквіваленти, то будь-які два відповідних їм нижніх об'єкта теж еквівалентні.
 Порядок нижнього об'єкта більше, ніж порядок будь-якого відповідного йому верхнього.
 
 
Щоб краще зрозуміти цю концепцію, пропоную вам на хвилину відволіктися від читання і подумати, як виглядатимуть нижні і верхні об'єкти, якщо як безлічі X взяти графи без трикутників (тобто, такі графи, в яких ніякі три вершини не з'єднані ребрами всі одночасно ).
 
 Відповідь Звичайно, це не єдиний спосіб, але досить природно в якості нижніх об'єктів взяти графи без трикутників, в яких одна з вершин пофарбована в червоний колір (це означатиме, що ми збираємося її видаляти), а в якості верхніх — графи без трикутників, в яких в червоний колір пофарбовані кілька вершин (це означатиме, що ми збираємося додати вершину і з'єднати її з усіма червоними вершинами). При цьому потрібно вимагати, щоб червоні вершини було попарно з'єднані. У цьому випадку після додавання нової вершини трикутники не утворюються.
 
 
Продовжимо. Нехай від деякого Непомічені об'єкта не можна нічого «відкусити». Таким чином, нижніх об'єктів, відповідних йому (а точніше, відповідних його поміченим об'єктам), немає. Такий об'єкт називається непріводімим . У нашому випадку, непріводімимі є розсічення, що складаються з єдиного багатокутника. Всі інші є приводяться .
 
Наш алгоритм буде генерувати всі неізоморфних розсічення послідовно, починаючи з непріводімих, поступово нарощуючи їх порядок. Для цього ми будемо приклеювати до поточного розсіченню всі можливі багатокутники з усіх можливих сторін. Проблема, однак, полягає в тому, що до одного і того ж розсіченню можна прийти декількома способами. Наприклад, до розсічення восьмикутника, якому відповідав нижній об'єкт на двох попередніх картинках, можна прийти, приклеївши до трикутника чотирикутник, а потім п'ятикутник, а можна — приклеївши, навпаки, до п'ятикутник трикутник і чотирикутник. Таким чином, виникає можливість згенерувати одне і те ж розсічення кілька разів, і навіть не помітити цього. Це те, чого якраз хочеться уникнути.
 
Щоб обійти цю проблему, згенерувавши нове розсічення, ми будемо перевіряти, чи правда, що останнє додавання багатокутника відповідає якомусь єдиному канонічному способом побудови цього розсічення. Для цього нам знадобиться функція P, що зіставляє кожному позначеному об'єкту безліч нижніх об'єктів, для яких він є «нащадком». Функція P повинна задовольняти таким вимогам:
 
 
     
Якщо L (x) пусто, то і P (x) теж порожньо.
 Якщо L (x) не порожньо, то P (x) складається з таких і тільки таких відповідають об'єкту х нижніх об'єктів, що будь-які два з них переходять один в одного під дією якогось елементу g, для якого g * x = x.
 Для будь-якого Непомічені об'єкта x і елемента групи g: g * P (x) = P (g * x).
 
 
Варто звернути особливу увагу на другу вимогу: воно, фактично, означає, що безліч P (x) має складатися з декількох об'єктів, що є еквівалентними щодо симетрій об'єкта x. Нехай, наприклад, вийшло так, що розсічення x симетрично щодо лише поворотів на 0 і 180 градусів. Тоді P (x) має складатися з рівно двох нижніх об'єктів, які утворюються один з одного за допомогою таких поворотів.
 
Спробуємо задовольнити загальній вимозі в нашому прикладі. Для цього візьмемо якесь розсічення x і прокрутимо на ньому помітки усіма n способами (n — кількість вершин). Кожен раз, коли з вершин 1 і 2 буде починатися «крайній» багатокутник (такий, що його можна відрізати), будемо таку нумерацію запам'ятовувати. Після цього з усього виділеного подможества нумерацій вершин виберемо ті, які дають лексикографічно мінімальну (підійде і будь-який інший розумний порядок) запис списків суміжності. Ці нумерації виділяють нам деякі багатокутники на вихідному об'єкті х — ті, які при відповідних нумерації починаються з 1 і 2. P (x) якраз і складається з нижніх об'єктів для x, в яких ці багатокутники пофарбовані в червоний колір. Без малюнка тут не обійтися:
 
 
 
Отже, ми вибрали розсічення x, зображене зліва, і вісьмома різними способами переставили позначки. Способи a, c, e і g нам відразу не підходять: на вершинах 1,2, ..., i не побудований багатокутник, який можна відрізати. Видно, що способи b і f, по суті, однакові, так само як і способи d і h. З цих чотирьох способів вибираємо ті, які в деякому сенсі «мінімальні». Як ми вже помітили, можна визначити мінімум як завгодно, але однозначно. Наприклад, підійде мінімальна лексикографічно запис списків суміжності. У цьому випадку способи b і f виграють. Ці спосіб виділяють нам трикутники 2,3,4 і 6,7,8 на вихідному позначеному об'єкті х. У результаті ми отримуємо два нижніх об'єкта, показаних на малюнку справа.
 
Функція P — найважливіша для швидкої генерації. Задовольнити зазначеним вимогам і зберегти високу швидкість роботи, в дійсності, вельми складно. Як видно, функція P, в деякому розумінні, дозволяє вказати, який із способів «відкусити» крайній багатокутник є канонічним, з точністю до ізоморфізму. Якщо концепція зрозуміла, пропоную вам придумати, як повинна працювати функція P (x) для вже згаданих графів без трикутників.
 
 Відповідь Відповідь, звичайно, не однозначний. Один з простих (але не дуже ефективних) способів такої: для графа без трикутників x переберемо всі способи перенумерувати вершини, після чого залишимо ті, які дають лексикографічно мінімальну запис списків суміжності. Для кожного з таких способів виберемо вершину v, що має номер 1, і складемо нижній об'єкт — граф x з пофарбованої в червоний колір вершиною v. Всі такі різні нижні об'єкти і утворюють результат роботи P (x).
 
 
Код, який додає до описаних вище класам методи, що реалізують всі перераховані функції, краще подивитися в репозиторії : у ньому занадто багато технічних подробиць, щоб обговорювати його в деталях.
 
Тепер все готово для того, щоб описати безпосередньо алгоритм генерації. Він буде запускатися для кожного неприводимого розсічення. Для поточного розсічення ми розглядаємо всі неізоморфних способи створити верхній об'єкт, а потім кожен отриманий верхній об'єкт нарощуємо до нижнього з збільшенням порядку. Далі, за допомогою функції P кожен нижній об'єкт перевіряємо на те, що він дійсно є батьком відповідного йому поміченого об'єкту. Якщо ця перевірка проходить, то вважаємо, що даний позначений об'єкт є представником нового класу еквівалентності; запускаємо алгоритм для нього рекурсивно. Можна, звичайно, довести коректність цього алгоритму, але, відчуваю, я і так небагато перестарався з формалізмом, та й для того, щоб розібратися з доказом, простіше звернутися до вихідній статті .
 
Краще давайте спочатку подивимося на код, який відповідає за генерацію:
 
public static void generateSubtreeFrom(Dissection root, int maxOrder) {
        for (UpperDissection upper : root.createAllUpper()) {
            LowerDissection lower = upper.createArbitraryLower();
            if (lower != null) {
                Dissection probableChild = lower.getUnderlyingDissection();
                if (probableChild.getOrder() <= maxOrder && lower.isParentFor(probableChild)) {
                    root.addChild(probableChild);
                    generateSubtreeFrom(probableChild, maxOrder);
                }
            }
        }
    }

 
А тепер — на результат генерації всіх неізоморфних розтинів на 3,4 і 5-косинці, аж до порядку, рівного восьми. Стрілки спрямовані від батьків до нащадків. Видно, що всі розсічення утворили дерева, корінням яких є Неприводимі об'єкти.
 
 
 

 
Вихідний код програми, яка згенерувала цей малюнок, доступний на гуглокоде . Результатом її роботи є опис у форматі graphviz.

На закінчення додам, що для розглянутої задачі можна, в принципі, придумати більш простий і при цьому більш швидкий алгоритм. Однак, описана процедура застосовна практично до всіх типів комбінаторних об'єктів, які можна побудувати індуктивним способом, «нарощуючи» структуру. Більш того, для деяких видів графів, принаймні, за твердженням автора алгоритму, такий підхід дає одні з кращих, якщо не кращі на сьогоднішній день швидкості генерації.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.