“Заполнение шаблона с мозаиками” загадка

Я полагаю, что для экземпляров из 100 ячеек динамическая программа, основанная на резьбовом разложении входного графа, может соответствовать всем требованиям.

Резьбовое разложение

В теории графов резное разложение графа является рекурсивным бинарным разбиением его вершин. Например, вот график

1--2--3
|  |
|  |
4--5

и одно из его резьбовых разложений

     {1,2,3,4,5}
     /         \
  {1,4}        {2,3,5}
  /   \        /     \
{1}   {4}  {2,5}     {3}
           /   \
         {2}   {5}.

Ширина резного разложения - это максимальное количество ребер, выходящих из одного из его разбиений. В этом случае {2,5} имеет исходящие ребра 2--1, 2--3 и 5--4, поэтому ширина равна 3. Ширина разбиения в стиле дерева kd сетки 10 × 10 равна 13.

Ширина резьбы графа является минимальной шириной разложения резьбы. Известно, что планарные графы (в частности, подграфы сеточных графов) с n вершинами имеют ширину резьбы O (√n), а константа big-O относительно мала.

Динамическая программа

При заданном входном графе n-вершин и резьбовом разложении ширины w существует O (2 ^{w n) -время алгоритм для расчета оптимального выбора плитки. Это время работы быстро растет в w, поэтому вы должны попытаться вручную разложить некоторые входные данные, чтобы понять, какую производительность ожидать.}

Алгоритм работает на дереве декомпозиции снизу вверх. Пусть X - разбиение, и пусть F - множество ребер, покидающих X. Мы составим таблицу, отображающую каждую из 2 ^{| F | возможностей для наличия или отсутствия ребер в F в оптимальную сумму на X при указанных ограничениях (-Infinity, если решения не существует). Например, с разделом {1,4} у нас есть записи}

{} -> ??
{1--2} -> ??
{4--5} -> ??
{1--2,4--5} -> ??

Для конечных разделов только с одной вершиной подмножество F полностью определяет плитку, поэтому легко заполнить количество соединений (если плитка действительна) или -Infinity в противном случае. Для других разделов, при вычислении записи таблицы, попробуйте все различные шаблоны подключения для ребер, которые идут между двумя дочерними элементами.

Например, предположим, что у нас есть части

                       |
.    .-    .-    -.    .
     |                 

Таблица для {1} равна

{} -> 0
{1--2} -> 1
{1--4} -> -Infinity
{1--2,1--4} -> 2

Таблица для {4} равна

{} -> 0
{1--4} -> 1
{4--5} -> 1
{1--4,4--5} -> -Infinity

Теперь давайте вычислим таблицу для {1,4}. Для {}, без ребра 1--4 мы имеем оценку 0 для {1} (запись {}) плюс оценку 0 для {4} (запись {}). С краем 1--4 мы имеем счет -Infinity + 1 = -Infinity (записи {1--4}).

{} -> 0

Для {1--2} баллы: 1 + 0 = 1 без 1--4 и 2 + 1 = 3 с.

{1--2} -> 3

Продолжение.

{4--5} -> 0 + 1 = 1 (> -Infinity = -Infinity + (-Infinity))
{1--2,4--5} -> 1 + 1 = 2 (> -Infinity = 2 + (-Infinity))

В конце мы можем использовать таблицы, чтобы определить оптимальное решение.

Нахождение резного разложения

Существуют сложные алгоритмы для нахождения хороших резных разложений, но они могут вам не понадобиться. Попробуйте простую схему разбиения двоичного пространства.

В качестве основы посмотрите на более ранний ответ, который я дал по поводу поиска. Программы поиска с восхождением на холм - это инструмент, который должен иметь в своем арсенале каждый программист, поскольку они работают намного лучше, чем простые решатели, работающие методом грубой силы.

Здесь даже относительно плохой алгоритм поиска имеет преимущество в том, что он не будет генерировать недопустимые платы, что значительно сокращает ожидаемое время выполнения.

Думаю, у меня есть идея получше. Я не проверял ее, но я уверен, что она будет быстрее, чем чисто силовое решение для больших зон.

Во-первых, создайте пустое множество ("множество" - это коллекция, содержащая только уникальные объекты) узлов. Эта коллекция будет использоваться для определения того, какие тайлы имеют нарушенные связи, которые необходимо исправить.

Заполните структуры данных для представления доски имеющимися фигурами, используя те, которые вы считаете наиболее подходящими, исходя из ваших личных критериев без учета правильности решения. Это почти наверняка приведет вас к недопустимому состоянию, но пока все в порядке. Пройдитесь по доске и найдите все плитки, у которых есть соединения, ведущие в никуда. Добавьте их в набор сломанных плиток.

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

Как только набор разорванных соединений станет пустым, у вас должен получиться красивый узор. Заметим, однако, что у этого метода есть важная оговорка: он может иметь тенденцию к чрезмерному упрощению узоров, поскольку на этапе "исправления" всегда будет предприниматься попытка уменьшить количество соединений. Возможно, вам повезет, и вы получите интересные узоры, так как на это может сильно повлиять первая деталь, которую вы положите на каждую плитку.