есть фигура на клетчатой бумаге (фактически, двумерный массив из 0 и 1)
задача: разбить ее на минимальное количество непересекающихся клеточных прямоугольников

формулируется просто, но как решать?

Здравствуйте Painkiller, Вы писали:

P>есть фигура на клетчатой бумаге (фактически, двумерный массив из 0 и 1)
P>задача: разбить ее на минимальное количество непересекающихся клеточных прямоугольников

P>формулируется просто, но как решать?
Есть какие-то ещё ограничения, например, сложность алгоритма, сложность дальнейшего поиска, отношение ширины к высоте, прямоугольники примерно одинакового размера и пр. Нужен ли абсолютный минимум, или же задача формулируется разбить на желательно наименьшее количество прямоугольников?

Пока пришло в голову следующее (минимум не гарантирую):
Инициализация:

Каждая заполненная клетка становится прямоугольником.

Пока можно слить прямоугольник, так, чтобы образовался новый прямоугольник

Заместить оба прямоугольника на один.

Можно в цикле выбирать по критериям, например, выбирать такое сочетание, которое максимально увеличит площадь.

Вопрос: это как-то связано с картами Карно??? В любом случае, поищи сабж, должно помочь...

ЗЫ: Утро, голова не варит...

Здравствуйте fAX, Вы писали:

fAX>Есть какие-то ещё ограничения, например, сложность алгоритма, сложность дальнейшего поиска, отношение ширины к высоте, прямоугольники примерно одинакового размера и пр.

ограничений на прямоугольники нет — лишь бы это были прямоугольники
про сложнось алгоритма — см. ниже

fAX>Нужен ли абсолютный минимум, или же задача формулируется разбить на желательно наименьшее количество прямоугольников?

в принципе, абсолютный минимум не нужен, но было бы приятно построить быстрый точный алгоритм
хотя что-то мне подсказывает, что для подобных комбинаторных задач вряд ли это возможно
точный алгоритм с экспоненциальной трудоемкостью — сделать можно (но для фигуры ~1000x1000 на него можно не рассчитывать :crash:)

fAX>Пока пришло в голову следующее (минимум не гарантирую):
fAX>Инициализация:
fAX>

Каждая заполненная клетка становится прямоугольником.
fAX>

Пока можно слить прямоугольник, так, чтобы образовался новый прямоугольник
fAX>

Заместить оба прямоугольника на один.
fAX>Можно в цикле выбирать по критериям, например, выбирать такое сочетание, которое максимально увеличит площадь.

Есть еще лобовой метод — "жадный". Выдираем из фигуры прямоугольник максимальной площади, переходим к остаткам и т.д.
Рассматривались также некоторые похожие идеи на "укрупнение".

fAX>Вопрос: это как-то связано с картами Карно??? В любом случае, поищи сабж, должно помочь...
Никогда не сталкивался, посмотрим

fAX>ЗЫ: Утро, голова не варит... :shuffle:
Спасибо :up:

Здравствуйте Painkiller, Вы писали:

P>есть фигура на клетчатой бумаге (фактически, двумерный массив из 0 и 1)
P>задача: разбить ее на минимальное количество непересекающихся клеточных прямоугольников

P>формулируется просто, но как решать?

Для таким образом поставленной задачи — решение есть один многоугольник на всю матрицу

Здравствуйте 3.14159.., Вы писали:

...>Здравствуйте Painkiller, Вы писали:

P>>есть фигура на клетчатой бумаге (фактически, двумерный массив из 0 и 1)
P>>задача: разбить ее на минимальное количество непересекающихся клеточных прямоугольников

...>Для таким образом поставленной задачи — решение есть один многоугольник на всю матрицу

О многоугольниках вроде речи не было (?)
Клеточный прямоугольник — имеется в виду прямоугольник целиком состоящий из единиц.
Вроде остальное все прозрачно...

Здравствуйте Painkiller, Вы писали:

P>в принципе, абсолютный минимум не нужен, но было бы приятно построить быстрый точный алгоритм
P>хотя что-то мне подсказывает, что для подобных комбинаторных задач вряд ли это возможно
P>точный алгоритм с экспоненциальной трудоемкостью — сделать можно (но для фигуры ~1000x1000 на него можно не рассчитывать )
Потому и спросил. Вообще, первая идея, которая пришла в голову тогда, это максимально разбить фигуру, а потом — "утрясать", крутилось в голове simulated annealing, но как прикрутить — не придумал, может, глупость. Не помню откуда, но знаю, что приближение в 2 раза большее по кол-ву можно построить ОЧЕНЬ быстро (линейно???).

P>Есть еще лобовой метод — "жадный". Выдираем из фигуры прямоугольник максимальной площади, переходим к остаткам и т.д.
P>Рассматривались также некоторые похожие идеи на "укрупнение".
Можно и так, но думаю, будет хуже

XXXX
 XXXX

Будет 3 прямоугольника, а можно 2.

Здравствуйте fAX, Вы писали:

fAX>Потому и спросил. Вообще, первая идея, которая пришла в голову тогда, это максимально разбить фигуру, а потом — "утрясать", крутилось в голове simulated annealing, но как прикрутить — не придумал, может, глупость.

С укрупнением мне не удается построить внятного принципа выбора пррямоугольников под слияние

fAX>Не помню откуда, но знаю, что приближение в 2 раза большее по кол-ву можно построить ОЧЕНЬ быстро (линейно???).

Это было бы супер. Если вдруг вспомнится что, дайте мне знать.

P>>Есть еще лобовой метод — "жадный". Выдираем из фигуры прямоугольник максимальной площади, переходим к остаткам и т.д.
P>>Рассматривались также некоторые похожие идеи на "укрупнение".
fAX>Можно и так, но думаю, будет хуже
fAX>

fAX>XXXX
fAX> XXXX
fAX>

fAX>Будет 3 прямоугольника, а можно 2.

А иногда, наверно, будет лучше

Здравствуйте Painkiller, Вы писали:

P>есть фигура на клетчатой бумаге (фактически, двумерный массив из 0 и 1)
P>задача: разбить ее на минимальное количество непересекающихся клеточных прямоугольников

P>формулируется просто, но как решать?
Не судите строго за убогость реализации

#include <memory.h>
#include <iostream.h>
#include <conio.h>

void makecopy(int src[5][5],int dest[5][5])
{
    for (int i=0;i<5;i++){
        memcpy(dest[i],src[i],sizeof(int)*5);
    }
}

int numofzero(int matr[5][5])
{
    int nzero=0;
    for (int y=0;y<5;y++){
        for (int x=0;x<5;x++){
            nzero+=matr[y][x];
        }
    }
    return nzero;
}

int findmaxrect(int matr[5][5],int xstart,int ystart,int* xmax,int* ymax)
{
    bool nilfound=false;
    int size=1;
    int xsize,ysize,xbest=1,ybest=1;
    for (xsize=1;xsize<=5-ystart;xsize++){//перебор ширины
        for (ysize=1;ysize<=5-ystart;ysize++){//перебор высоты
            nilfound=false;
            for (int y=ystart;y<ystart+ysize && !nilfound;y++){//поиск 0
                for (int x=xstart;x<xstart+xsize;x++){
                    if (!matr[y][x]){
                        nilfound=true;
                        break;
                    }
                }
            }
            if (!nilfound && ysize*xsize>xbest*ybest){
                xbest=xsize;
                ybest=ysize;
            }
        }
    }
    *xmax=xbest+xstart;
    *ymax=ybest+ystart;
    return size;
}

int findbest(int matr[5][5])
{
    int copy[5][5];
    int xmax,ymax;
    int min=25,test;
    for (int y=0;y<5;y++){
        for (int x=0;x<5;x++){
            makecopy(matr,copy);
            if (copy[y][x]){
                test=1;
                //найти максимальный прямоугольник
                findmaxrect(copy,x,y,&xmax,&ymax);

                for (int yfill=y;yfill<ymax;yfill++){
                    for (int xfill=x;xfill<xmax;xfill++){
                        copy[yfill][xfill]=0;
                    }
                }
                if (numofzero(copy)) test+=findbest(copy);
                if (test<min) min=test;
            }
            if (min==1) return min;
        }
    }
    return min;
}

void main()
{
    int matr[5][5]={{0,0,1,0,0},
                    {0,1,1,1,0},
                    {1,1,1,1,1},
                    {0,1,1,1,0},
                    {0,0,1,0,0}};
    cout << findbest(matr) << endl;
    getch();
}

Решается через рекурсию. Суть алгоритма в том, чтобы в любой клеточной фигуре выделить прямоугольник максимальной площади.
1) находим прямоугольник
2) удаляем его
3) если остались ещё клетки перейти к 1
Вообщем решения в лоб, поэтому эффективность страдает

Здравствуйте Рома, Вы писали:

Р>Здравствуйте Painkiller, Вы писали:

Р>Решается через рекурсию. Суть алгоритма в том, чтобы в любой клеточной фигуре выделить прямоугольник максимальной площади.
Р>1) находим прямоугольник
Р>2) удаляем его
Р>3) если остались ещё клетки перейти к 1
Р>Вообщем решения в лоб, поэтому эффективность страдает :crash:

К сожалению это не гарантирует минимальность числа прямоугольников.
Пример:
У прямоугольника 5 * 5 ( размеры не сильно важны ) сдвинем центральный столбец на 1. При этом можно разбить на 3 прямоугольника, а алгоритм, приведенный выше должен дать 4.

Здравствуйте KonstantinA, Вы писали:

KA>Здравствуйте Рома, Вы писали:

Р>>Здравствуйте Painkiller, Вы писали:

Р>>Решается через рекурсию. Суть алгоритма в том, чтобы в любой клеточной фигуре выделить прямоугольник максимальной площади.
Р>>1) находим прямоугольник
Р>>2) удаляем его
Р>>3) если остались ещё клетки перейти к 1
Р>>Вообщем решения в лоб, поэтому эффективность страдает

KA>К сожалению это не гарантирует минимальность числа прямоугольников.
KA>Пример:
KA>У прямоугольника 5 * 5 ( размеры не сильно важны ) сдвинем центральный столбец на 1. При этом можно разбить на 3 прямоугольника, а алгоритм, приведенный выше должен дать 4.
Пример мне не очень ясен, но минимальность действительно не гарантируется . Для того, чтобы получить совершенно минимальное количесво прямоугольников необходимо перебирать все возможные значения размеров прямоугольников в ф-ии findmaxrect, что приведёт к ещё большей потере производительности . Если время будет подумаю над более эффективным решением.

Здравствуйте Рома, Вы писали:

Р>Решается через рекурсию. Суть алгоритма в том, чтобы в любой клеточной фигуре выделить прямоугольник максимальной площади.
Р>1) находим прямоугольник
Р>2) удаляем его
Р>3) если остались ещё клетки перейти к 1
Р>Вообщем решения в лоб, поэтому эффективность страдает

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

Здравствуйте Рома, Вы писали:


Р>Пример мне не очень ясен,

Пример:
__*__
*****
*****
*****
*****
**_**

Здравствуйте Painkiller, Вы писали:

P>есть фигура на клетчатой бумаге (фактически, двумерный массив из 0 и 1)
P>задача: разбить ее на минимальное количество непересекающихся клеточных прямоугольников

P>формулируется просто, но как решать?


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

Можно более просто построить граф по всем точкам и опять же искать циклы.

ИМХО должно работать но ручаться не буду.

P.S. Пмниться была эта задачка на одном из туров Московской олимпиады.

С Уважением Андрей.......

Здравствуйте Young, Вы писали:

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

Что-то я нынче туго соображаю :( Можно для начала немного поподробнее — какие точки выбираются, какие прямые проводятся. Лучше всего — на примерах

Y>P.S. Пмниться была эта задачка на одном из туров Московской олимпиады.

Вот это интересно. На какой именно и в каком году? Где нибудь в сети можно про это что-нибудь обнаружить?

Y>С Уважением Андрей.......

Спасибо :up:

Здравствуйте Young, Вы писали:

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

Что-то я нынче туго соображаю :( Можно для начала немного поподробнее — какие точки выбираются, какие прямые проводятся. Лучше всего — на примерах

Y>P.S. Пмниться была эта задачка на одном из туров Московской олимпиады.

Вот это интересно. На какой именно и в каком году? Где нибудь в сети можно про это что-нибудь обнаружить?

Y>С Уважением Андрей.......

Спасибо :up:

Здравствуйте Painkiller, Вы писали:

P>в принципе, абсолютный минимум не нужен, но было бы приятно построить быстрый точный алгоритм
P>хотя что-то мне подсказывает, что для подобных комбинаторных задач вряд ли это возможно
P>точный алгоритм с экспоненциальной трудоемкостью — сделать можно (но для фигуры ~1000x1000 на него можно не рассчитывать )

Задача явно многоэкстремальная и быстрого точного алгоритма для нее скорее всего не будет.

fAX>>Пока пришло в голову следующее (минимум не гарантирую):
fAX>>Инициализация:
fAX>>

Каждая заполненная клетка становится прямоугольником.
fAX>>

Пока можно слить прямоугольник, так, чтобы образовался новый прямоугольник
fAX>>

Заместить оба прямоугольника на один.
fAX>>Можно в цикле выбирать по критериям, например, выбирать такое сочетание, которое максимально увеличит площадь.

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

P>Есть еще лобовой метод — "жадный". Выдираем из фигуры прямоугольник максимальной площади, переходим к остаткам и т.д.
P>Рассматривались также некоторые похожие идеи на "укрупнение".

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

Здравствуйте Андрей Тарасевич, Вы писали:

АТ>Задача явно многоэкстремальная и быстрого точного алгоритма для нее скорее всего не будет.

К сожалению, похоже, Вы правы

АТ>Эта вариант. На самом деле можно начинать не с отдельных клеток, а с прямоугольников, на которые исходная фигура разрезается всевозможными горизоньтальными и вертикальными линиями, проходящими через все ее вершины. Несложно показать, что среди таких решений будут оптимальные.

Ну что все так запали на это разрезание? Это же очевидно, что полученная после такого разрезания задача эквивалентна исходной: объявляем каждый полученный прямоугольник "клеткой" — получаем ту же задачу, возможно с меньшим числом клеток. Только не в моем случае, потому что эта оптимизация очевидна и осуществляется при построении матрицы.

АТ>Это, наверное, будет слишком "жадный" метод. Да и задача выбора внутреннего прямоугольника макcимальной площади тоже многоэкстремальна. Как ты предлагаешь выбирать такой прямоугольник?

Например, любой. Или наиболее близкий к квадрату. Или еще как нибудь — все равно это уже не наука :shuffle:
В любом случае, пока никто ничего лучше не предложил

Здравствуйте Painkiller, Вы писали:

P>Здравствуйте Young, Вы писали:

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

P>Что-то я нынче туго соображаю :( Можно для начала немного поподробнее — какие точки выбираются, какие прямые проводятся. Лучше всего — на примерах


Попробую на примерах.

И так есть многоугольник.




Отмеченные точки находиться следующим образом
Для точки X,Y
If (Point[X-1,Y].Color != Point[X,Y].Color) and ((Point[X,Y-1].Color != Point[X,Y].Color) or (Point[X,Y+1].Color != Point[X,Y].Color))


Потом проводим горизонтальные (или вертикальные) прямые через эти точки – они разбивают многоугольник на прямоугольники. Ну а потом объединяем их методом который я предложил или другим.





Y>>P.S. Пмниться была эта задачка на одном из туров Московской олимпиады.

P>Вот это интересно. На какой именно и в каком году? Где нибудь в сети можно про это что-нибудь обнаружить?

Примерно лет пять-шесть назад. Я почему как раз и вспомнил – но в сети не нашел.



С Уважением Андрей.......

Здравствуйте Аноним, Вы писали:

А>Потом проводим горизонтальные (или вертикальные) прямые через эти точки – они разбивают многоугольник на прямоугольники. Ну а потом объединяем их методом который я предложил или другим.

А>

Такой саособ не гарантирует оптимальности. А автор вопроса, как я понял, хочет, в первую очередь, именно ее.

Здравствуйте Аноним, Вы писали:

А>Потом проводим горизонтальные (или вертикальные) прямые через эти точки – они разбивают многоугольник на прямоугольники. Ну а потом объединяем их методом который я предложил или другим.

А>


Что-то я не очень понимаю какие из этих прямоугольников можно объединить.