3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
|
|
1 | |
Покрытие множеств19.01.2010, 18:22. Показов 8306. Ответов 37
Метки нет (Все метки)
Добрый день, новичок на этом форуме =)
нуждаюсь в помощи с задачей на покрытия множеств. Дано множество нужно двумя алгоритмами (полного и граничного переборов) вычислить полные покрытия и "лишние" покрытия. как можно наиболее оптимально осуществить полный и граничный перебор? ведь это 2^n вариантов.. Думал еще над способом с битными масками, но нигде не нашел ничего подобного. Буду очень благодарен за помощь. Добавлено через 35 минут я прошелся по разделу и понял, что может быть я не туда запостил? если да, то пусть модераторы перенесут тему в раздел "С\С++", а то вроде не совсем "начинающая" задачка. благодарю
0
|
19.01.2010, 18:22 | |
Ответы с готовыми решениями:
37
Минимальное реберное покрытие графа Найти покрытие полным перебором Определить, существует ли покрытие C' из C мощности не более K Покрытие шахматной доски ходом коня |
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
|
|
23.01.2010, 20:24 [ТС] | 21 |
Ну тогда можно сказать, что A B C D E F тоже подходит, но его не выводит, так ведь?
тогда нужно или чтоб не было этих покрытий, которые уже были в других или же чтоб они все вывелись?
0
|
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
|
|
23.01.2010, 20:37 | 22 |
да покрытия разные, но пока делается полным перебором, что значит что должны вылезти все покрытия которые только возможные, чтоб их отсять нужно уже делать втором способом, кажись граничный перебор(могу и перепутать так как их куча) , почему не выводит покрытие A B C D E F я обяснить не могу
0
|
1179 / 989 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
|
|
24.01.2010, 12:44 | 23 |
lego69, ты совершенно прав!
Алгоритм еще очень груб и не оптимален. Очень зависит от порядка записи (а значит и перебора) множеств. Надо думать, как бы его оптимизировать. Вообще, работа с множествами - штука очень нетривиальная! {A B C D E F G } не получается, т.к. до него не доходит, алгоритм обрывается раньше, т.е. раньше образуется полное покрытие. Вот если б G содержала элемент, которого нет ни в одном из других множеств, тогда это покртие выскочило бы обязательно и еще куча других таких же избыточных. А вот если б G (с тем же свойством) стоял в начале, тогда покрытий было б найдено поменьше. Пока писал, подумал - а ведь эту штуку можно применить! Т.е. как-то пересортировывать множества перед перебором! 100% гарантии оптимальности это не даст, но как эвристику использовать то можно!
0
|
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
|
|
24.01.2010, 19:38 [ТС] | 24 |
Day, но ведь если их пересортировывать при полном переборе, то у нас будет очень много повторений покрытий, это как-то не очень радует)
0
|
1179 / 989 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
|
||||||
24.01.2010, 20:27 | 25 | |||||
Ничего другого не придумал, как только проверять не перекрывает ли
покрытия одно другое Если у кого будут интересные идеи - дайте знать динамический массив XXL для хранения неизвестно скольких чисел long Наверное, вместо него можно использовать <vector>, но хотелось бы все сделать в чистом C XXL также можно использовать для организации вычисление с очень длинными числами
0
|
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
|
|
26.01.2010, 01:23 [ТС] | 26 |
мой мозг взорван, но алгоритм таки работает)
спасибо, буду разбираться
0
|
1179 / 989 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
|
|
26.01.2010, 15:11 | 27 |
Прости, не жалею я твою бедную голову, но вот придумал новый вариант.
Если сил уже нет - не бери в голову, предыдущий вариант вроде работает, ну и хорошо. Суть нового варианта в том, что я переставляю исходные множества так, чтобы дефицитные элементы были в самом начале. И действительно, выбросов и генераций новых покрытий становится меньше. Правда, обращений к функции Pokr остается столько же, но это - или данные так подобрались, или я чего-то напортачил. Задумано было так, чтоб многие варианты не рассматривались, достигается это игрой с LMi. Все в прикрепленном зипе pok4.c, pok4.exe - предыдущий вариант, слегка дополненный (вывод статистики) pok5.c, pok5.exe - новый вариант с сортировкой множеств 4.prn 55.prn - результаты Но голову жалей - она тебе еще пригодится. Просто задачка показалась интересной...
0
|
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
|
|
27.01.2010, 16:16 [ТС] | 29 |
а вот если например нужно вывести абсолютно все возможные покрытия? я про это как-то забыл, но суть задачки состояла именно в том, что уже сделано и "лишних" покрытиях.
можно конечно не менять суть алгоритма и уже с конечным результатом побаловаться, но это тупо)
0
|
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
|
|
27.01.2010, 16:39 | 30 |
вижу вас тоже Захарченко прижала, мути матрицу и ее перебирай, я так делоть буду
хотя действительно интирестно как в етом алгоритме вывести все переборы...
0
|
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
|
|
27.01.2010, 16:57 [ТС] | 31 |
Веталька, можно без оффтопа?
0
|
1179 / 989 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
|
|
27.01.2010, 19:38 | 32 |
Если нужны ВСЕ покрытия, то это так просто, что даже скушно.
Просматриваешь ВСЕ комбинации подмножеств. M = (1L<<N); for (long Q=1; Q<M; Q++) { // Проверяешь, является ли набор подмножеств, определяемый // шкалой Q покрытием // И печатаешь покрытие }
1
|
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
|
|
27.01.2010, 20:29 | 33 |
нужно не все покрытия а все варианты тоесть 2^n, тоесть
А АБ АБВ АБВГ... ..... БА БВ БГ .... БАВГД ........
0
|
1179 / 989 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
|
||||||
28.01.2010, 07:30 | 34 | |||||
Веталька, тогда еще проще - НЕ проверяешь, а просто печатаешь набор
множеств и элементы в него попавшие M = (1L<<N); for (long Q=1; Q<M; Q++) { // И печатаешь } Добавлено через 35 минут Вопрос понял. Вот просплюсь, позавтракую, погуляю с собачкой по морозцу (кстати, зовут его "Байтик"), и чего-нибудь придумаю... Добавлено через 10 часов 9 минут
1
|
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
|
|
28.01.2010, 15:02 [ТС] | 35 |
Day,
или я не про то подумал?
0
|
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
|
|
28.01.2010, 15:47 | 37 |
чтото у тебя совсем результат не верный вышел, вот сам посмотри внимательно на "D"
0
|
1179 / 989 / 83
Регистрация: 29.10.2009
Сообщений: 1,385
|
|
28.01.2010, 18:32 | 38 |
В начальных условиях ошибка!
Все числа записаны справа налево (старший разряд - 9-й), а С - наборот, оно должно быть не 0х33, а 0х198. Но все равно - с 10-м нулем непонятно.
0
|
28.01.2010, 18:32 | |
28.01.2010, 18:32 | |
Помогаю со студенческими работами здесь
38
Минимальное покрытие отрезка отрезками. Рекурсия и динамическое программирование Доказать равенство множеств с помощью основных законов алгебры множеств Поменять местами значения множеств a и b без использования дополнительных множеств Составить программу, меняющую местами значения множеств A и B без использования дополнительных множеств Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |