Постало завдання перебрати всі можливі варіанти «тріангуляцій». Це «склейки» з N трикутників, які підпорядковуються простим правилам:
- Стикатися трикутники можуть тільки по ребру
- Одне ребро може бути загальним тільки у двох трикутників, не більше
Наприклад, з трьох трикутників унікальних варіантів може бути всього два:
[[A B C], [A B D], [A C D]]
[[A B C], [A B D], [A C E]]
При тому, що всього варіантів склейок 120. Мені вдалося непогано оптимізувати процес перебору, який дозволив прорахувати майже всі варіанти аж до N = 11, але це все одно дуже мало.
Я розповім як оптимізував, може бути у поважної публіки з'являться ідеї як цей процес ще прискорити.
Наївний підхід
Розглянемо варіант при N = 3. Три трикутники, 9 вершин. Нумеруємо вершини 0... 8 і перебираємо всі від 000 000 000 до 888 888 888.
Як бачимо, це дуже дофіга навіть для трьох трикутників. Ну і повтори трикутників, які тут будуть постійно попадатися, нам тут ні до чого.
Підхід
Довгі вечори роздумів дозволили голові народити наступну думку:
Раз всі трикутники повинні бути склеєні один з одним хоча б одним руба, то максимальна кількість вершин, яка знадобиться для склейки з N трикутників, має бути менше, ніж N * 3
І дійсно, найдовша валідна склейка виглядатиме так:
І видно, що в ній всього 5 унікальних вершин замість 9. У загальному випадку кількість унікальних вершин виходить за формулою N + 2, де N - кількість трикутників. Якщо унікальних вершин буде більше, то один з трикутників обов'язково буде з'єднуватися з іншими лише однією вершиною, а це неправильно.
Отже. 5 унікальних вершин для трьох трикутників.
Всього комбінацій буде (згадуємо комбінаторику і біноміальний коефіцієнт) 5 !/( 3! (5 - 3)!) = 10
Це кількість унікальних трикутників, яку ми можемо отримати, генеруючи всі комбінації вершин.
Ну а тепер, вважаємо цей же біноміальний коефіцієнт для комбінацій з трьох трикутників
10! / (3!(10 — 3)!) = 120. Це скільки склейок треба перебрати щоб врахувати всі варіанти.
У загальному вигляді формула для кількості комбінацій виглядає наступним чином:
Бачите, скільки факторіалів? Наприклад, для N = 10 всього буде 59 473 554 359 599 446 комбінацій, це дуже багато, навіть якщо паралелити.
Коли я почав перебір з маленьких N (3,4,5..) то помітив, що програма досить швидко знаходить всі комбінації, а інше - це просто дублікати (вони відсіюються алгоритмом VF2, який перевіряє графи на ізоморфізм)
Досить швидко - це означає, що остання «хороша» склейка для, наприклад, N = 5 знайшлася на 2084 кроці з 324 632, що становить 0.642% від усього діапазону. Для N = 6 це 0.3644%. Останнє, що мені вдалося порахувати самому - для N = 8 це 0.1352%.
Тобто, в загальному випадку для N + 1 ми дивимося, скільки відсотків від попереднього діапазону було пораховано і рахуємо стільки ж, це буде гарантувати нам, що все перевірено. Правда для N = 9 це все одно забагато (270 485 377 680, якщо перевіряти 0.1352%)
Так що, треба було придумати щось ще.
Ітеративний підхід
Ще кілька довгих вечорів і чергова ідея:
А що, якщо генерувати всі склейки для N + 1 на основі всіх склеїв для N шляхом додавання одного трикутника всіма можливими комбінаціями?
Тобто, ми знаємо, що для трійок у нас їх всього дві
[[A B C], [A B D], [A C D]]
[[A B C], [A B D], [A C E]]
А четвірок шість
[[A B C], [A B D], [A C D], [B C D]]
[[A B C], [A B D], [A C D], [B C E]]
[[A B C], [A B D], [A C E], [A D E]]
[[A B C], [A B D], [A C E], [A D F]]
[[A B C], [A B D], [A C E], [B C F]]
[[A B C], [A B D], [A C E], [B D F]]
Видно, що всі четвірки вийшли з попередніх трійок (перестановки генеряться в лексикографічному порядку)
Все б добре, генері собі далі, АЛЕ! Коли перевірив цей підхід, виявилося, що таким чином генеруються не всі, наприклад, п'ятірки
[[A B C], [A B D], [A C D], [B C E], [B D E]]
[[A B C], [A B D], [A C D], [B C E], [B D F]]
[[A B C], [A B D], [A C D], [B C E], [B E F]]
[[A B C], [A B D], [A C E], [A D E], [B C F]]
[[A B C], [A B D], [A C E], [A D F], [A E F]]
[[A B C], [A B D], [A C E], [A D F], [A E G]]
[[A B C], [A B D], [A C E], [A D F], [B C G]]
[[A B C], [A B D], [A C E], [A D F], [C E G]]
[[A B C], [A B D], [A C E], [B D E], [C D E]]
[[A B C], [A B D], [A C E], [B D F], [C E G]]
Якщо уважно придивитися, то передостання п'ятірка вийшла відмінною від усіх четвірок не на один, а на два трикутники. У термінах топології це «стрічка меліуса». І якщо спробувати намалювати її без одного, будь-якого трикутника, то буде виходити ситуація, коли групи трикутників стикаються лише однією вершиною, що зовсім недобре.
Що ж, вихід все одно є. Беремо всі комбінації для N, відщипуємо по одному трикутнику з кінця, «догенеруємо» ще всі варіанти двох і перевіряємо. Все одно в купу разів швидше, ніж з комбінаторним перебором.
Ан ні, при N = 8 знайшлася триангуляція, яка відрізняється від усіх сімок вже не на 2, а на 3 трикутники.
Так що, починаючи з N = 9 відщипуються вже 2 трикутники, і «наздогенеруються» три. Це дозволило прорахувати майже всі варіанти аж до N = 11 і початок 12 (майже - тому, що скоріше за все там є склейки, що відрізняються на 3, а то і більше трикутників). При тому, що я розпаралелив всю цю справу. Один потік у мене виконує первинну перевірку склеїв, інші 3 займаються відсіканням дублікатів, оскільки перевірка графів на ізоморфність досить ресурсоємне заняття.
Загалом, якщо не потрібні всі варіанти, то можна відщипувати (або не відщипувати) і наздогенерувати решту, це буде звичайно погано, але якісь варіанти це спосіб точно дасть навіть для великих N. Тому, що абсолютно незрозуміло скільки і коли треба «відщипувати» щоб отримати весь набір валідних склеїв.
Але цікавий то весь!
Я вже і на тему перебору графів матеріал шукав, і чого тільки не думав, крутіше ітеративного методу поки немає ідей. Може бути у вас будуть думки на цю тему?
Наприклад, коли генерується комбінація трикутників, то перша завжди йде така приблизно склейка:
ABC ABD ABE ABF ABG…
Видно, що AB повторюється більше 2 разів. Якби генерувати варіанти, де спочатку таких випадків би не було, то по ідеї комбінаторному варіанту було б простіше, але у мене немає ідей як генерити такі послідовності.
P.S. це потрібно для наукової роботи з класифікації поверхонь. На мене звичайно не образяться, якщо я надам дані до N = 11, у них і таких немає (хоча, наприклад, тор можна побудувати з 14 трикутників, мені таке ще рік обраховувати). Але було б цікаво придумати спосіб який дозволив би це N відсунути подалі. Дякую за увагу.
UPD
Варто було доперти раніше, але доперло тільки зараз. Коли ми відщеплюємо пару трикутників від склейки з N, у нас виходить купа явних дублікатів, які можна прибрати ще до початку перебору для N + 1. Непоганий буст у швидкості виходить