| Версия для печати темы
Нажмите сюда для просмотра этой темы в оригинальном формате |
| Форум программистов > Алгоритмы > Прямоугольное сжатие картинки |
| Автор: redNaks 11.11.2011, 10:18 |
| Задача: На вход программы подаётся квадратная 0-1 матрица М размера N x N. Матрица вводится в виде списка из N строк матрицы, где каждая строка — это список из N элементов матрицы. Затем задаётся положительное целое число K. Можно ли покрыть все единичные элементы матрицы М не более чем К прямоугольниками? Другими словами, существует ли такая последовательность четвёрок (ai, ci, bi, di) (1 <= i <= K, 1 <= ai,bi,ci,di <= N, ai <= bi, ci <= di), в которой ai,bi это номера строк матрицы, а ci,di — номера столбцов. Эта последовательность должна удовлетворять условию, что любой единичный элемент матрицы должен покрываться хотя бы одним прямоугольником, и любой прямоугольник должен состоять только из единичных элементов матрицы. Решить нужно с помощью генетического алгоритма. Есть ли у кого-нибудь идеи, как хотя бы считать веса выборок? |
| Автор: VictorTsaregorodtsev 11.11.2011, 15:39 |
| Ген.алг фиксированной длиной хромосомы. Длина равна 4К. Каждые четыре значения - это размеры конкретного прямоугольника (например, координаты верхнего левого угла и размеры вправо и вниз - чтобы не возиться с удовлетворением ограничений ai <= bi, ci <= di, т.е. bi и di будут вычисляться отдельно). Операция скрещивания - по границе четверок (так будет удобнее не нарушать ограничения ai,bi,ci,di <= N, ai <= bi, ci <= di). Мутация - так, чтобы ai, ci, bi, di не превысили размеров матрицы (т.е. если случайно сгенерированное значение или поправка к значению дают выход за размеры - генерим и пробуем новое значение до тех пор, пока не найдём устраивающую нас мутацию элемента хромосомы). Фитнес-функция - с переменным числом слагаемых. По каждому прямоугольнику с размером прямоугольника zi я бы добавлял +1/zi для каждого покрытого прямоугольником единичного элемента матрицы, и -1/zi для нулевого. Может, еще добавил бы -1/(N*N) для каждого непокрытого прямоугольниками элемента матрицы. Может, добавил бы какой-то небольшой штраф (отрицательные слагаемые) для перерытых несколькими прямоугольниками элементов (чтобы заставить прямоугольники не кучковаться где-то в углу матрицы, а разбежаться по всей матрице). В общем, тут надо начинать с чего-то простого и в ходе экспериментов смотреть, как быстро оптимизируется та или иная фитнес-функция. Проще было бы считать фитнес-функцию как число непокрытых элементов матрицы - но это даёт сильно уж большое огрубление. В моём случае можно более детально вычислить превосходство одного разбиения над другим. Пусть, например, оба сравниваемых разбиения не покрывают одно и то же число единичек - но одно из разбиений менее сильно накладывает свои прямоугольники друг на друга, значит, оно получше с точки зрения отсутствия "избыточности" покрытия. Либо, в этом же самом случае, можно сделать другой вывод - разбиение с более сильным наложением прямоугольников может более сильно двигать свои прямоугольники (есть ненужная избыточность покрытия), поэтому и стоит его предпочесть. В общем, тут можно напридумывать кучу разных эмпирик - поэтому если простейшая фитнес-функция в виде числа непокрытых элементов хорошо не сработает, то нужно будет переходить именно к более мелкодетальным способам сравнения разбиений (я возможные эмпирические идеи в предыдущем абзаце описал). |
| Автор: ole4901 12.11.2011, 15:58 |
| Большое спасибо вам!!! |