![]() |
|
![]() ![]() ![]() |
|
redNaks |
|
|||
Новичок Профиль Группа: Участник Сообщений: 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 — номера столбцов. Эта последовательность должна удовлетворять условию, что любой единичный элемент матрицы должен покрываться хотя бы одним прямоугольником, и любой прямоугольник должен состоять только из единичных элементов матрицы. Решить нужно с помощью генетического алгоритма. Есть ли у кого-нибудь идеи, как хотя бы считать веса выборок? |
|||
|
||||
VictorTsaregorodtsev |
|
|||
Опытный ![]() ![]() Профиль Группа: Участник Сообщений: 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) для каждого непокрытого прямоугольниками элемента матрицы. Может, добавил бы какой-то небольшой штраф (отрицательные слагаемые) для перерытых несколькими прямоугольниками элементов (чтобы заставить прямоугольники не кучковаться где-то в углу матрицы, а разбежаться по всей матрице). В общем, тут надо начинать с чего-то простого и в ходе экспериментов смотреть, как быстро оптимизируется та или иная фитнес-функция. Проще было бы считать фитнес-функцию как число непокрытых элементов матрицы - но это даёт сильно уж большое огрубление. В моём случае можно более детально вычислить превосходство одного разбиения над другим. Пусть, например, оба сравниваемых разбиения не покрывают одно и то же число единичек - но одно из разбиений менее сильно накладывает свои прямоугольники друг на друга, значит, оно получше с точки зрения отсутствия "избыточности" покрытия. Либо, в этом же самом случае, можно сделать другой вывод - разбиение с более сильным наложением прямоугольников может более сильно двигать свои прямоугольники (есть ненужная избыточность покрытия), поэтому и стоит его предпочесть. В общем, тут можно напридумывать кучу разных эмпирик - поэтому если простейшая фитнес-функция в виде числа непокрытых элементов хорошо не сработает, то нужно будет переходить именно к более мелкодетальным способам сравнения разбиений (я возможные эмпирические идеи в предыдущем абзаце описал). |
|||
|
||||
ole4901 |
|
|||
Новичок Профиль Группа: Участник Сообщений: 9 Регистрация: 12.11.2011 Репутация: нет Всего: -1 |
Большое спасибо вам!!!
![]() |
|||
|
||||
![]() ![]() ![]() |
Правила форума "Алгоритмы" | |
|
Форум "Алгоритмы" предназначен для обсуждения вопросов, связанных только с алгоритмами и структурами данных, без привязки к конкретному языку программирования и/или программному продукту.
Если Вам понравилась атмосфера форума, заходите к нам чаще! С уважением, maxim1000. |
0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей) | |
0 Пользователей: | |
« Предыдущая тема | Алгоритмы | Следующая тема » |
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |