Поиск:

Ответ в темуСоздание новой темы Создание опроса
> Прямоугольное сжатие картинки 
:(
    Опции темы
redNaks
Дата 11.11.2011, 10:18 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 1
Регистрация: 11.11.2011

Репутация: нет
Всего: нет



Задача:
На вход программы подаётся квадратная 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 — номера столбцов. Эта последовательность должна удовлетворять условию, что любой единичный элемент матрицы должен покрываться хотя бы одним прямоугольником, и любой прямоугольник должен состоять только из единичных элементов матрицы. 

Решить нужно с помощью генетического алгоритма. Есть ли у кого-нибудь идеи, как хотя бы считать веса выборок?
PM MAIL   Вверх
VictorTsaregorodtsev
Дата 11.11.2011, 15:39 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Опытный
**


Профиль
Группа: Участник
Сообщений: 274
Регистрация: 28.7.2006

Репутация: 3
Всего: 8



Ген.алг фиксированной длиной хромосомы. Длина равна 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) для каждого непокрытого прямоугольниками элемента матрицы. Может, добавил бы какой-то небольшой штраф (отрицательные слагаемые) для перерытых несколькими прямоугольниками элементов (чтобы заставить прямоугольники не кучковаться где-то в углу матрицы, а разбежаться по всей матрице). В общем, тут надо начинать с чего-то простого и в ходе экспериментов смотреть, как быстро оптимизируется та или иная фитнес-функция.

Проще было бы считать фитнес-функцию как число непокрытых элементов матрицы - но это даёт сильно уж большое огрубление. В моём случае можно более детально вычислить превосходство одного разбиения над другим. Пусть, например, оба сравниваемых разбиения не покрывают одно и то же число единичек - но одно из разбиений менее сильно накладывает свои прямоугольники друг на друга, значит, оно получше с точки зрения отсутствия "избыточности" покрытия. Либо, в этом же самом случае, можно сделать другой вывод - разбиение с более сильным наложением прямоугольников может более сильно двигать свои прямоугольники (есть ненужная избыточность покрытия), поэтому и стоит его предпочесть. В общем, тут можно напридумывать кучу разных эмпирик - поэтому если простейшая фитнес-функция в виде числа непокрытых элементов хорошо не сработает, то нужно будет переходить именно к более мелкодетальным способам сравнения разбиений (я возможные эмпирические идеи в предыдущем абзаце описал). 
PM MAIL WWW   Вверх
ole4901
Дата 12.11.2011, 15:58 (ссылка) | (нет голосов) Загрузка ... Загрузка ... Быстрая цитата Цитата


Новичок



Профиль
Группа: Участник
Сообщений: 9
Регистрация: 12.11.2011

Репутация: нет
Всего: -1



Большое спасибо вам!!! smile 
PM MAIL   Вверх
  
Ответ в темуСоздание новой темы Создание опроса
Правила форума "Алгоритмы"

maxim1000

Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.


Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000.

 
1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема | Алгоритмы | Следующая тема »


 




[ Время генерации скрипта: 0.0613 ]   [ Использовано запросов: 20 ]   [ GZIP включён ]


Реклама на сайте     Информационное спонсорство

 
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности     Powered by Invision Power Board(R) 1.3 © 2003  IPS, Inc.