Пазл "Шаблон с начинкой"

Ответ 1

Для экземпляров с 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 x 10 составляет 13.

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

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

Для n-вершинного входного графа и разборки по ширине w существует алгоритм O (2 ^w n) -time для вычисления оптимального выбора плитки. Это время работы быстро растет в 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))

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

Поиск деформирования резьбы

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

Ответ 2

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

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

Ответ 3

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

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

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

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

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