У меня есть двоичная матрица n * m (0 и 1). Проблема заключается в том, чтобы охватить все 1 с неперекрывающимися коробками, элементы которых все 1.Минимальное количество защитных коробок для двоичной матрицы
Пример:
1111
0110
0110
коробка может быть представляет с координатами и длинами в каждых координатах (x,y,lx,ly). Этот пример покрыт 2 ящиками { (0,0,1,4), (1,1,2,2) }.
Я ищу, как найти покрытие с минимальным количеством ящиков.
Благодаря
Эта проблема называется разбиением прямолинейного многогранника. Существует хороший answer по аналогичному вопросу biziclop, размещенному в комментарии.
Идея алгоритма заключается в уменьшении проблемы до максимального согласования двудольного графа (вершины возможны порезы.)
3D
Моя исходная задача была такая же тема в 3D. Эта версия Показано, что NP-complete: -/
После некоторых исследований, я реализовал решение на основе эвристики, описанной в работах Ануй Джейна:
Моя проблема домен вычислительной химии, и мы будем решать огромные многомерные проблемы. Существует два алгоритма глобальной оптимизации общего случая, который может быть применен здесь, которые также были успешно применен к системам, содержащих несколько десятков тысяч атомов:
а) генетических алгоритмы
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/SOFTWARE/PARSA/
http://www.codeproject.com/KB/recipes/SimulatedAnnealing.aspx
Оба алгоритма хорошо уважают реализации общедоступного домена и хорошо понимают свойства оптимальности.
являются коробки разрешено перекрываться? –
@Jeff: для указанной проблемы вы не получите никакой пользы путем перекрытия. –
Возможно, вам это будет полезно: http://stackoverflow.com/questions/4701887/find-the-set-of-largest-contiguous-rectangles-to-cover-multiple-areas/4701966#4701966 – biziclop