Минимальное количество коробок покрытия для двоичной матрицы - PullRequest
Новая
       4

Минимальное количество коробок покрытия для двоичной матрицы

5 голосов
/ 16 марта 2011

У меня есть двоичная матрица n * m (0 и 1).Проблема состоит в том, чтобы покрыть все 1 неперекрывающимися прямоугольниками, элементы которых равны 1.

Пример: 

1111
0110
0110

Поле может быть представлено с координатами и длинами в каждой координате (x,y,lx,ly).Этот пример покрыт 2 коробками { (0,0,1,4), (1,1,2,2) }.

Я ищу, как найти обложку с минимальным количеством коробок.

Спасибо

Ответы [ 2 ]

1 голос
/ 20 мая 2011

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

а) генетические алгоритмы
http://en.wikipedia.org/wiki/Genetic_algorithm

б) моделируемый отжиг
http://www.gnu.org/software/gsl/
FTP: //ftp.alumni.caltech.edu/pub/ingber
http://www.taygeta.com/annealing/simanneal.html
http://www2.cs.uni -paderborn.de / CS / AG-monien / ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ / Парс /
http://www.codeproject.com/KB/recipes/SimulatedAnnealing.aspx

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

0 голосов
/ 23 августа 2014

Эта проблема называется разбиением прямолинейного многогранника.Есть хороший ответ на похожий вопрос biziclop, опубликованный в комментарии.

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

3D

Моей первоначальной проблемой была та же тема в 3D.Эта версия показана как NP-полная : - /

После некоторых исследований я реализовал решение на основе эвристики, описанной в статьях Ануджа Джайна:

...