Я полагаю, что для экземпляров из 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), а константа 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))
В конце мы можем использовать таблицы для определения оптимального решения.
Нахождение резного разложения
Существуют сложные алгоритмы для нахождения хороших резьбовых разложений, но они могут вам не понадобиться. Попробуйте простую схему разбиения двоичного пространства.