Минимальное точное покрытие сетки с квадратами; дополнительные сокращения

Эта проблема появилась в challenge, но поскольку она теперь закрыта, должно быть хорошо спросить об этом.

Проблема (не этот вопрос сам по себе, это просто справочная информация) можно визуально описать так, заимствуя их собственный образ:

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

Существует очевидная модель ILP: генерировать все возможные квадраты (квадрат возможен, если он охватывает только ячейки сетки, которые присутствуют), ввести двоичную переменную x_i для каждого квадрата, указывающую, используем мы ее или нет, затем

minimize sum x_i

subject to:
1) x_i is an integer
2) 0 ≤ x_i ≤ 1
3) for every cell c
       (sum[j | c ϵ square_j] x_j) = 1

Ограничение 3 говорит, что каждая ячейка покрывается ровно один раз. Ограничения 1 и 2 делают x_i двоичным. Минимальное решение дает оптимальное решение исходной задачи.

Линейная релаксация этого (т.е. игнорирование ограничения 1) является наполовину приличной, но она делает такие вещи (это сетка 6x6 с отсутствием верхнего левого угла):

$fractional solution$

Здесь 13 квадратов были выбраны "наполовину" (давая объективное значение 6,5), размеров (чтобы вы могли быстрее найти их)

1 из 4x4
3 из 3x3
6 из 2x2
3 из 1x1

Оптимальное решение для этого экземпляра имеет объективное значение 8, например:

Линейная релаксация наполовину приличная, но я не совсем ей доволен. Разрыв иногда превышает 10%, что иногда приводит к очень медленной целочисленной фазе.

Что там, где возникает реальный вопрос, существуют ли дополнительные ограничения, которые я могу добавить (лениво) в виде разрезов, чтобы улучшить дробное решение?

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

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

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

Я также пытался что-то сделать с квадратными числами (площадь каждого квадрата, ну, квадрат) и различия квадратных чисел, но это также не закончилось ничем полезным.

Ответ 1

Ограничения на значение целевой функции

Всякий раз, когда целевое значение функции не является неотъемлемым, например, потому что у вас есть нечетное число квадратов с 0,5 весовыми коэффициентами в дробном решении, вы можете добавить разрез "прямо на целевую функцию", чтобы заставить его следующее более высокое интегральное значение: например, в вашем примере дробное решение с 13 квадратами, каждый из которых имеет вес 0,5 для общего целевого значения функции 6.5, вы можете добавить ограничение, что сумма всех x_i >= 7.

Более общие сокращения

Это приводит к более общему правилу, которое будет работать всякий раз, когда у вас есть дробное решение, в котором некоторое подмножество C ячеек "точно покрывается" некоторым подмножеством S квадратов, имеющих нецелый общий вес w. Под "точно покрытым" я имею в виду, что квадраты в S имеют ненулевой вес и вместе обеспечивают общий вес 1 для каждой ячейки в C и не перекрывают любые ячейки вне C. Вы можете легко найти эти подмножества ячеек создавая граф с вершиной для каждой ячейки и ребро между двумя вершинами всякий раз, когда они (частично) покрываются одним и тем же квадратом в дробном решении: каждая связанная компонента этого графа является (минимальным) таким подмножеством.

Учитывая дробное решение с некоторым точно покрываемым подмножеством C и квадратным подмножеством S, как указано выше, пусть T - множество всех квадратов, перекрывающих только клетки в C (очевидно, T является надмножеством S). Мы знаем, что любое оптимальное решение X подзадачи LP, состоящее только из подмножества C ячеек (и соответствующего подмножества T квадратов кандидатов), должно иметь одинаковый общий вес по S, так как если бы это не противоречило бы оптимальности дробное решение для оригинального LP: вы можете просто заменить S на X и получить лучшее решение.

Теперь исходная задача состоит из двух наборов решений (любой из которых может быть пустым): те решения, в которых ни один квадрат не охватывает как ячейку в C, так и ячейку вне C, и те решения, в которых по крайней мере некоторые квадрат делает. Мы хотим запретить растворы в первой категории, имеющие общий вес < Раундап (ш). Пусть U - множество всех квадратов, перекрывающих по крайней мере одну ячейку в C и по меньшей мере одну ячейку вне C. Мы можем достичь этого, добавив ограничение

Sum_{square_i in T}(x_i) + RoundUp(w) * Sum_{square_j in U}(x_j) >= RoundUp(w)

Эффект умножения второго члена на LHS на RoundUp (w) заключается в том, что если даже один квадрат, который охватывает как ячейку в C, так и некоторую другую ячейку, включен в решение, ограничение эффективно "уходит". Это необходимо, потому что S и C ничего не говорят нам о таких решениях исходной проблемы, и поэтому мы не можем позволить себе их исключить. Заметим, что исходное решение, содержащее подмножество квадратов S, будет запрещено этим ограничением, так как каждый квадрат в U должен иметь вес 0 в этом решении.

Нет панацеи

Второй подход более мощный, чем первый, поскольку может случиться так, что, например, граф содержит две компоненты, каждая из которых имеет нечетное число квадратов, все из которых имеют вес 0,5: это будет означать, что есть в целом четное число квадратов, что означает, что общая целевая функция является интегральной, что предотвращает возможность добавления разреза на целевую функцию. Но даже применение этих разрезов снова и снова не гарантирует, что в конечном итоге будет найдено приемлемое решение: в качестве конкретного примера, когда вся сетка сама по себе горизонтально и/или вертикально симметрична, но может быть покрыта асимметричным набором квадратов, то его можно так же легко покрыть горизонтально и/или вертикально перевернутой версией этого набора квадратов - и, что более раздражающе, любой "аффинной комбинацией" этих двух квадратных множеств (т.е. любой комбинацией с суммированием весов до 1). В общем, может быть много одинаково хороших возможных решений, и описанные здесь сокращения не дают возможности остановить решателя LP от решения, содержащего "суперпозицию" всех k из них, причем все квадраты назначают вес 1/к.

[EDIT 1/7/2015]

Яркая сторона!

Хотя, как я уже упоминал выше, нет способа заставить решателя LP "изолировать" одно конкретное возможное покрытие от дробной "суперпозиции" нескольких симметричных оптимальных обложек, есть хорошие новости: в случае, если вы действительно получаете такая суперпозиция, на самом деле очень легко восстановить единственное оптимальное, возможное покрытие от него. Все, что вам нужно сделать, это жадно выбирать квадраты с ненулевым весом, каждый раз вычеркивая любые квадраты, которые перекрывают квадрат, который вы только что выбрали. Это гарантированно будет работать, если решение представляет собой суперпозицию, как я описал, и, что также важно: если эта процедура работает на дробном решении (то есть, если повторение этого жадного шага в конечном итоге охватывает все ячейки), то решение, которое вы get должен быть оптимальным! (Предположим, что это не так: пусть X - оптимальное дробное решение, возвращаемое решателем LP, пусть F - допустимое решение, которое вы просто извлекли из него жадно, и пусть y - наименьший вес любого квадрата в F. Обратите внимание, что каждый квадрат в F вносит по крайней мере y значение охвата каждой ячейки, поэтому, поскольку F является субоптимальным по предположению, вычитая y из веса каждого квадрата в F и масштабируя все остальные веса в X вверх на 1/(1-y), будет дать другой (возможно, еще дробный) раствор с более низким весом, что противоречит оптимальности X.)

Было бы очень полезно доказать, что любое дробное решение либо (i) имеет некоторую компоненту в "покрывающем графе" с нецелым общим весом, либо (ii) состоит из такой суперпозиции: это означало бы, что вы могли бы продолжайте применять мои "общие" порезы, пока не получите суперпозицию, которую вы могли бы затем решить жадно. Но в его нынешнем виде могут быть дробные решения вне этих двух категорий.

Ответ 2

Я использовал метод ветки и цены для хорошего эффекта по аналогичной проблеме (ITA Strawberry Fields; прокрутить вниз). Вот мой код, который (без комментариев), вероятно, хорош только как доказательство нулевого знания, что я знаю, о чем говорю. Он был на порядок быстрее, чем коммерческий решатель (который я не буду называть).

Ключом была стратегия ветвления. Вместо того, чтобы напрямую взаимодействовать с переменными x_i, которые, скорее всего, вы решаете, решаете на более высоком уровне. Тот, который я использовал для Strawberry Fields, должен был решить, будут ли покрыты две клетки одной и той же площадью. Если вы нацеливаете пары, что дробное решение больше всего на заборе, то структура решения кажется довольно быстрой.

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

Ответ 3

Динамическое программирование: выберите ячейку (любая ячейка будет делать), вычислите все допустимые квадраты, которые ее покрывают (то есть, только для текущей ячейки и других ячеек в сетке). Для каждого такого квадрата рекурсивно получаем минимальное значение покрытия для оставшейся области (сетка минус квадрат), а затем выбираем минимальное значение из них (результатом является это значение + 1). Чтобы ускорить работу, попробуйте выбрать ячейку с наименьшим допустимым квадратом покрытия на каждом уровне рекурсии (таким образом, уменьшив количество рекурсивных вызовов на каждом уровне).

Простой действительно.

Ответ 4

Я бы использовал поиск, например A*, чтобы найти решение. Важно отметить, что A * похож на Greedy Best-First-Search, поскольку он может использовать эвристический вести себя. Предполагая, что у вас есть правильная эвристика, он найдет оптимальное решение (~ 0.95) в разумные сроки.

Примерное решение использует 18 блоков вместо 19, как показано в примере. В дополнение к эвристическому вы можете использовать предварительную компиляцию , чтобы повысить эффективность алгоритма. Например, я вычислил, что я называю градиентом свободы для каждого местоположения. Например, ваша начальная карта становится этапом:

У вас может быть ваша собственная эвристика, которая может быть одинаково хороша или даже лучше. Я использовал это только потому, что нашел, что это тривиально. Номера этапов имеют следующий смысл: более высокий номер - скорее, он будет в большой коробке (есть больше ограничений, которые вы можете заключить, но это начало).

Значение этапа - это сумма 4 правил автоматизации подвала.

Например верхний левый

cell(x,y) := min(cell(x,y-1) ?? 0, cell(x-1,y) ?? 0, cell(x-1,y-1) ?? 0) + 1

оператор называется нуль-коалесцирующим оператором. Он возвращает левый операнд, если операнд не равен нулю; в противном случае он возвращает правый операнд.

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

Сам алгоритм повторяется:

Заказать ячейки и принять наивысшие
Результаты правила автоматизации заказов и максимальные значения
Найдите тривиальные срезы

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

Например, у вас может быть шаблон (верхняя левая часть)

--+++
+-+++
+++++

Вы можете сгенерировать его хэш и добавить его в hashmap/dictionary со значением 4 (это означает, что для покрытия + требуется минимум 4 прямоугольника). Тогда у вас есть диапазон 5x3 с тем же хешем, который вы знаете, это тривиальный срез со стоимостью 4.

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

В качестве альтернативы существует способ загипнотизировать, действительно ли мы ищем какое решение. Используя функцию Wolfram Mathematica FindMinimum, она будет выглядеть примерно так:

FindMinimum[{
  a + b + c + d + e + f + g, 
  (a 1^2 + b 2^2 + c 3^2 + d 4^2 + e 5^2 + f 6^2 + g 7^2) == 119 &&
  a >= 0 && b >= 0 && c >= 0 && d >= 0 && e >= 0 && f >= 0 && g >= 0 &&
  a \[Element] Integers &&
  b \[Element] Integers &&
  c \[Element] Integers &&
  d \[Element] Integers &&
  e \[Element] Integers &&
  f \[Element] Integers &&
  g \[Element] Integers
}, {a,b,c,d,e,f,g}]

Это основано на предположении, что мы имеем сетку 12x12 с 119 ячейками, и это даст нам оптимальное решение с подсчетом размера сетки.

Печально wolfram alpha поисковая система не интерпретирует это, возможно, в будущем.

Ответ 5

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