Форум программистов, компьютерный форум CyberForum.ru
Наши страницы

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.77
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
#1

Покрытие множеств - C++

19.01.2010, 18:22. Просмотров 3772. Ответов 37
Метки нет (Все метки)

Добрый день, новичок на этом форуме =)
нуждаюсь в помощи с задачей на покрытия множеств.
Дано множество

http://img96.imageshack.us/img96/1008/mnoj.jpg

нужно двумя алгоритмами (полного и граничного переборов) вычислить полные покрытия и "лишние" покрытия.
как можно наиболее оптимально осуществить полный и граничный перебор? ведь это 2^n вариантов..
Думал еще над способом с битными масками, но нигде не нашел ничего подобного.
Буду очень благодарен за помощь.

Добавлено через 35 минут
я прошелся по разделу и понял, что может быть я не туда запостил?
если да, то пусть модераторы перенесут тему в раздел "С\С++", а то вроде не совсем "начинающая" задачка.
благодарю
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
19.01.2010, 18:22
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Покрытие множеств (C++):

Найти покрытие полным перебором - C++
Всем доброго времени суток. Программирование С++ изучаю недавно. Дали запрограммировать покрытие полным и граничным перебором. Загнал...

Минимальное реберное покрытие графа - C++
Господа, подскажите пожалуйста, как реализовать эту задачу. Я так понимаю суть ее заключается ее в том, что,s необходимо найти такое...

Покрытие шахматной доски ходом коня - C++
4. Покрытие шахматной доски ходом коня.

Определить, существует ли покрытие C' из C мощности не более K - C++
УСЛОВИЕ. Задано семейство C подмножеств конечного множества S и положительное целое число K <= |C|. ВОПРОС. Существует ли покрытие C' из...

Пересечение множеств - C++
Вход — два множества натуральных чисел. Выход — их пересечение (перечисление элементов через пробел в любом порядке без повторений)...

Пересечение множеств - C++
Есть такое задание: Создать класс- множество. Функции-члены реализуют добавление и удаление элемента, пересечение и размность множеств. ...

37
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
23.01.2010, 12:07 #16
как?)
printf("%..%...\n", сомнительные переменные);
В тех местах, где есть подозрения...

Добавлено через 8 часов 53 минуты
Все конечно, не очень хорошо.
Очень много повторов, и это естесственно для этого алгоритма.
Как их убрать?
Первое, что приходит в голову - запоминать сделанные покрытия и сравнивать, не перекрывает ли
текущее X его.
(Критерий того, что B есть подмножество множества A : ((A^B)^A)==0 )
Но это требует неизвестно сколько памяти...
Наверное, есть другой способ, через рекурсию, дайте немного подумать...

Добавлено через 21 минуту
Ошибся в критерии
Надо
( ((A^B) & (|A)) == 0)
^ - исключающее ИЛИ
|A - НЕ A

Добавлено через 1 час 42 минуты
Удалось таки сделать приличную прогу.
И без повторов и с отбрасыванием ненужного
Код
#include <stdio.h>
#include <string.h>

static double a[7]={ 1, 3, 2, 2, 1, 2, 3 }; //vesa
static long  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xB5 };
static long U;
static int N = 7;  // kol-vo podmnogestv
static int n = 9;  // kol-vo elementov polnogo mnogestva

void main()
{ int i;
  U = 0; // Togda polnoe mnojestvo delaetsya tak:
  for(i=0; i<n;i++ )   U |= (1L<<i);
//  printf ("U = %lx\n", U); // DEB
  Pokr(0, 0L, 0L);
}
/*****************/
// Y - pokrito  P - who ispol'zovan J - s kakovo nachinat'
Pokr(int J, long Y, long P)
{ long Q, Z; int i, j; double s;

   for(i=J; i<N; i++) {
     if (((Y^A[i]) & (Y^U))==0) continue; // A[i] nichego ne dobavit
     Z = (Y|A[i]);
     Q = (P|(1L<<i));
     if (Z==U) {
        // printf("Z=%lx i=%d\n", Z, i); // DEB
        s = 0;
        for (j=0; j<N; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (Q & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        continue;
     }
     Pokr(i+1, Z, Q); // Recursia!
   }
}
/*****************/
Вот такой результат
Код
A B C D s=8.000000
A B C F s=8.000000
A B C G s=9.000000
A B D E s=7.000000
A B D F G s=11.000000
A B D G s=9.000000
A B E F s=7.000000
A B E G s=8.000000
A B F G s=9.000000
A B G s=7.000000
A C D E F s=8.000000
A D E F s=6.000000
B C D G s=10.000000
B C F G s=10.000000
B C G s=8.000000
B D E G s=9.000000
B D F G s=10.000000
B D G s=8.000000
B E F G s=9.000000
B E G s=7.000000
B F G s=8.000000
B G s=6.000000
C D E F G s=10.000000
1
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
23.01.2010, 17:47  [ТС] #17
оо, вообще супер. правда выходит так, что оно все-таки делает повторы.
я имею ввиду с множествами, которые входят в предыдущие.
B G входит в A B E G
ну наверно с этим ничего не поделать, так что спасибо и за это
0
Веталька
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
23.01.2010, 18:29 #18
прошу прощения пост вышел совершенно случайно и был удален
0
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
23.01.2010, 18:36 #19
Но это РАЗНЫЕ покрытия!
Об оптимальности мы еще не говорили...
0
Веталька
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
23.01.2010, 18:53 #20
оо, вообще супер. правда выходит так, что оно все-таки делает повторы.
я имею ввиду с множествами, которые входят в предыдущие.
B G входит в A B E G
ну наверно с этим ничего не поделать, так что спасибо и за это
ну так ето метод полного перебора и покрытия выводятся все....или я ошибаюсь?
0
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
23.01.2010, 20:24  [ТС] #21
Цитата Сообщение от Day Посмотреть сообщение
Но это РАЗНЫЕ покрытия!
Об оптимальности мы еще не говорили...
Ну тогда можно сказать, что A B C D E F тоже подходит, но его не выводит, так ведь?
тогда нужно или чтоб не было этих покрытий, которые уже были в других или же чтоб они все вывелись?
0
Веталька
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
23.01.2010, 20:37 #22
Цитата Сообщение от lego69 Посмотреть сообщение
Ну тогда можно сказать, что A B C D E F тоже подходит, но его не выводит, так ведь?
тогда нужно или чтоб не было этих покрытий, которые уже были в других или же чтоб они все вывелись?

да покрытия разные, но пока делается полным перебором, что значит что должны вылезти все покрытия которые только возможные, чтоб их отсять нужно уже делать втором способом, кажись граничный перебор(могу и перепутать так как их куча) , почему не выводит покрытие A B C D E F я обяснить не могу
0
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
24.01.2010, 12:44 #23
lego69, ты совершенно прав!
Алгоритм еще очень груб и не оптимален.
Очень зависит от порядка записи (а значит и перебора) множеств.
Надо думать, как бы его оптимизировать.
Вообще, работа с множествами - штука очень нетривиальная!

{A B C D E F G } не получается, т.к. до него не доходит, алгоритм обрывается раньше,
т.е. раньше образуется полное покрытие.
Вот если б G содержала элемент, которого нет ни в одном из других множеств, тогда
это покртие выскочило бы обязательно и еще куча других таких же избыточных.
А вот если б G (с тем же свойством) стоял в начале, тогда покрытий было б найдено
поменьше.
Пока писал, подумал - а ведь эту штуку можно применить! Т.е. как-то пересортировывать
множества перед перебором! 100% гарантии оптимальности это не даст, но как эвристику
использовать то можно!
0
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
24.01.2010, 19:38  [ТС] #24
Day, но ведь если их пересортировывать при полном переборе, то у нас будет очень много повторений покрытий, это как-то не очень радует)
0
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
24.01.2010, 20:27 #25
Ничего другого не придумал, как только проверять не перекрывает ли
покрытия одно другое
Если у кого будут интересные идеи - дайте знать
динамический массив XXL для хранения неизвестно скольких чисел long
Наверное, вместо него можно использовать <vector>, но хотелось бы
все сделать в чистом C
XXL также можно использовать для организации вычисление с очень длинными
числами
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
#include <stdio.h>
#include <string.h>
#include <alloc.h>
 
typedef unsigned long LU;
typedef struct {
    LU *ss;    /* Массив LU */
    int ms;       /* Выделено памяти на ss */
    int ns;       /* Заполнено */
    int st;       /* Шаг приращения памяти для ss */
               }  XXL;
XXL *newXXL();        /* Генерация  */
addXXL (XXL *x, LU A);    /* Новый элемент */
cutXXL0(XXL *x, int k);  /* Удаление элемента k */
 
static double a[7]={ 1, 3, 2, 2, 1, 2, 3 }; //vesa
static LU  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xB5 };
static LU U;
static int N = 7;  // kol-vo podmnogestv
static int n = 9;  // kol-vo elementov polnogo mnogestva
static XXL *xx;
 
XXL *newXXL()           /* Генерация  */
{ XXL *x;
    x = (XXL *)malloc(sizeof(XXL));
    x->ss = NULL;
    x->ms = x->ns = 0;
    x->st = 20;
    return(x);
}
/*********/
locXXL (XXL *x)    /* Перераспределение памяти для добавки строки (если нужно) */
{
   if (x->ss==NULL) {
       x->ms = x->st;
       x->ss = (LU *)malloc( x->ms * sizeof(LU));
   }
   if (x->ns>=x->ms) {
       x->ms += x->st;
       x->ss = (LU *)realloc(x->ss,x->ms*sizeof(LU));
   }
}
/*********/
addXXL (XXL *x, LU A)    /* Новый элемент */
{
   locXXL(x);
   x->ns++;
   x->ss [x->ns - 1] = A;
}
/********/
cutXXL0(XXL *x, int k)  /* Удаление k-того элемента */
{  int j; LU *ss=x->ss;
 
  if (k<0) return;
  if (x==NULL || k<0 || k>=x->ns || n==0) return;
  for(j=k; j<x->ns-1; j++) ss[j] = ss[j+1];
  x->ns --;
}
/*******************/
void main()
{ int i, j; LU Q; double s;
  xx = newXXL();
  U = 0; // Togda polnoe mnojestvo delaetsya tak:
  for(i=0; i<n;i++ )   U |= (1L<<i);
//  printf ("U = %lx\n", U); // DEB
  Pokr(0, 0L, 0L);
  for(i=0; i<xx->ns; i++) {
    Q = xx->ss[i];
    s = 0;
    for (j=0; j<N; j++) { // Pechat' naydennogo pokrytiya i ego ceny
      if ( (Q & (1L<<j))!=0 ) {
        printf("%c ", 'A'+j);
        s += a[j];
      }
    }
    printf("s=%f\n", s);
  }
}
/*****************/
// Y - pokrito  P - who ispol'zovan J - s kakovo nachinat'
Pokr(int J, LU Y, LU P)
{ LU Q, Z; int i, ii;
 
   for(i=J; i<N; i++) {
     if (((Y^A[i]) & (Y^U))==0) continue; // A[i] nichego ne dobavit
     Z = (Y|A[i]);
     Q = (P|(1L<<i));
     if (Z==U) {
        for(ii=0; ii<xx->ns; ii++) {  // не всходит ли данное покрытие в предывгщие и наоборот
          if (((Q^xx->ss[ii]) & (Q^U))==0) break; // ii-тое из ранее полученных < Q
          if (((Q^xx->ss[ii]) & (xx->ss[ii]^U))==0) {  //
            cutXXL0(xx, ii);
            ii--;
            continue;
          }
        }
        if (ii == xx->ns) addXXL(xx, Q);
        continue;
     }
     Pokr(i+1, Z, Q); // Recursia!
   }
}
/*****************/
0
lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
26.01.2010, 01:23  [ТС] #26
мой мозг взорван, но алгоритм таки работает)
спасибо, буду разбираться
0
Day
1158 / 963 / 57
Регистрация: 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
Вложения
Тип файла: zip POK.ZIP (41.9 Кб, 22 просмотров)
Day
1158 / 963 / 57
Регистрация: 29.10.2009
Сообщений: 1,385
27.01.2010, 11:27 #28
Критерий того, что B является подмножеством множества A можно записать попроще:
(A|B) == A
или так
(A&B) == B
0
lego69
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
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
27.01.2010, 16:39
Привет! Вот еще темы с ответами:

пересечение множеств - C++
найти пересечение мнжества А и В. Результат вывести в другом множестве. заранее спс. извиняюсь если такое задание уже было

объединение множеств - C++
template&lt;class ValType, class FwdIt&gt; FwdIt copy ( FwdIt first, FwdIt last, FwdIt result ) { while (first!=last) *result++ =...

Калькулятор множеств - C++
Доброго всем утра, у меня есть лаба &quot;операции над множествами&quot;, там класс множество и методы работы с ним. На вход подаются две строки типа...

Булеан множеств - C++
В общем нужно в программе &quot;операции с множествами&quot; добавить операцию &quot;Булеан&quot; честно говоря вообще ничего в голову не лезет....может...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
30
Yandex
Объявления
27.01.2010, 16:39
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru