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

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

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 30, средняя оценка - 4.77
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
19.01.2010, 18:22     Покрытие множеств #1
Добрый день, новичок на этом форуме =)
нуждаюсь в помощи с задачей на покрытия множеств.
Дано множество

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

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

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

пересечение множеств C++
Пересечение множеств C++
Пересечение множеств C++
Минимальное реберное покрытие графа C++
Булеан множеств C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
23.01.2010, 20:24  [ТС]     Покрытие множеств #21
Цитата Сообщение от Day Посмотреть сообщение
Но это РАЗНЫЕ покрытия!
Об оптимальности мы еще не говорили...
Ну тогда можно сказать, что A B C D E F тоже подходит, но его не выводит, так ведь?
тогда нужно или чтоб не было этих покрытий, которые уже были в других или же чтоб они все вывелись?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Веталька
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 я обяснить не могу
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
24.01.2010, 12:44     Покрытие множеств #23
lego69, ты совершенно прав!
Алгоритм еще очень груб и не оптимален.
Очень зависит от порядка записи (а значит и перебора) множеств.
Надо думать, как бы его оптимизировать.
Вообще, работа с множествами - штука очень нетривиальная!

{A B C D E F G } не получается, т.к. до него не доходит, алгоритм обрывается раньше,
т.е. раньше образуется полное покрытие.
Вот если б G содержала элемент, которого нет ни в одном из других множеств, тогда
это покртие выскочило бы обязательно и еще куча других таких же избыточных.
А вот если б G (с тем же свойством) стоял в начале, тогда покрытий было б найдено
поменьше.
Пока писал, подумал - а ведь эту штуку можно применить! Т.е. как-то пересортировывать
множества перед перебором! 100% гарантии оптимальности это не даст, но как эвристику
использовать то можно!
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
24.01.2010, 19:38  [ТС]     Покрытие множеств #24
Day, но ведь если их пересортировывать при полном переборе, то у нас будет очень много повторений покрытий, это как-то не очень радует)
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
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!
   }
}
/*****************/
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
26.01.2010, 01:23  [ТС]     Покрытие множеств #26
мой мозг взорван, но алгоритм таки работает)
спасибо, буду разбираться
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
26.01.2010, 15:11     Покрытие множеств #27
Прости, не жалею я твою бедную голову, но вот придумал новый вариант.
Если сил уже нет - не бери в голову, предыдущий вариант вроде работает,
ну и хорошо.
Суть нового варианта в том, что я переставляю исходные множества так,
чтобы дефицитные элементы были в самом начале.
И действительно, выбросов и генераций новых покрытий становится меньше.
Правда, обращений к функции Pokr остается столько же, но это -
или данные так подобрались, или я чего-то напортачил.
Задумано было так, чтоб многие варианты не рассматривались,
достигается это игрой с LMi.
Все в прикрепленном зипе

pok4.c, pok4.exe - предыдущий вариант, слегка дополненный (вывод статистики)
pok5.c, pok5.exe - новый вариант с сортировкой множеств
4.prn 55.prn - результаты

Но голову жалей - она тебе еще пригодится.
Просто задачка показалась интересной...
Вложения
Тип файла: zip POK.ZIP (41.9 Кб, 22 просмотров)
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
27.01.2010, 11:27     Покрытие множеств #28
Критерий того, что B является подмножеством множества A можно записать попроще:
(A|B) == A
или так
(A&B) == B
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
27.01.2010, 16:16  [ТС]     Покрытие множеств #29
а вот если например нужно вывести абсолютно все возможные покрытия? я про это как-то забыл, но суть задачки состояла именно в том, что уже сделано и "лишних" покрытиях.
можно конечно не менять суть алгоритма и уже с конечным результатом побаловаться, но это тупо)
Веталька
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
27.01.2010, 16:39     Покрытие множеств #30
вижу вас тоже Захарченко прижала, мути матрицу и ее перебирай, я так делоть буду

хотя действительно интирестно как в етом алгоритме вывести все переборы...
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
27.01.2010, 16:57  [ТС]     Покрытие множеств #31
Веталька, можно без оффтопа?
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
27.01.2010, 19:38     Покрытие множеств #32
Если нужны ВСЕ покрытия, то это так просто, что даже скушно.
Просматриваешь ВСЕ комбинации подмножеств.

M = (1L<<N);
for (long Q=1; Q<M; Q++) {
// Проверяешь, является ли набор подмножеств, определяемый
// шкалой Q покрытием
// И печатаешь покрытие
}
Веталька
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
27.01.2010, 20:29     Покрытие множеств #33
нужно не все покрытия а все варианты тоесть 2^n, тоесть
А
АБ
АБВ
АБВГ...
.....
БА
БВ
БГ
....
БАВГД
........
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
28.01.2010, 07:30     Покрытие множеств #34
Веталька, тогда еще проще - НЕ проверяешь, а просто печатаешь набор
множеств и элементы в него попавшие
M = (1L<<N);
for (long Q=1; Q<M; Q++) {
// И печатаешь
}

Добавлено через 35 минут
Вопрос понял.
Вот просплюсь, позавтракую, погуляю с собачкой по морозцу (кстати, зовут его "Байтик"),
и чего-нибудь придумаю...

Добавлено через 10 часов 9 минут
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
#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 int N = 7;  // kol-vo podmnogestv
static int n = 9;  // kol-vo elementov polnogo mnogestva
 
OutX(long X) // Вывод состава покрытия
{  int i; double s;
  s = 0;
  for(i=0; i<N; i++)
    if (X&(1L<<i)) {
      printf(" %c", 'A' + i);
      s += a[i];
    }
  printf(" (s=%.2f) : ", s);
}
/*********/
long Union(long X)  // Объединение всех множеств покрытия
{  long P = 0; int i;
  for(i=0; i<N; i++)
    if (X&(1L<<i)) P |= A[i];
  return(P);
}
/*********/
OutE(long P) // Вывод покрытого множества
{  int i;
  for(i=n-1; i>=0; i--)
    if (P&(1L<<i)) printf("1");
    else           printf("0");
}
/*********/
void main()
{ long X, M, P;
  M = (1L<<N);
  // Любой набор множеств A[i] называем по традиции "покрытием",
  // хотя они могут покрывать только часть всего множества - P
  for(X=0; X<M; X++) { // Перебор всех возможных комбинаций подмножеств
    OutX(X); // Вывод состава покрытия
    P = Union(X);  // Объединение всех множеств покрытия
    OutE(P); // Вывод покрытого множества
    printf("\n");
  }
}
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
28.01.2010, 15:02  [ТС]     Покрытие множеств #35
Day,
ABC (s=6.00) : 111111110
D (s=2.00) : 1110
AD (s=3.00) : 111110
BD (s=5.00) : 1111110
ABD (s=6.00) : 11111110
CD (s=4.00) : 1111110
ACD (s=5.00) : 11111110
BCD (s=7.00) : 111111110
ABCD (s=8.00) : 1111111110
ABCD (s=8.00) : 1111111110 а как это стало 1111111110, если там максимум девять единиц)
или я не про то подумал?
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
28.01.2010, 15:15     Покрытие множеств #36
Не знаю.
У меня все нормально.
См.вложение
Вложения
Тип файла: zip P.ZIP (19.3 Кб, 22 просмотров)
Веталька
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
28.01.2010, 15:47     Покрытие множеств #37
Цитата Сообщение от lego69 Посмотреть сообщение
Day,


ABCD (s=8.00) : 1111111110 а как это стало 1111111110, если там максимум девять единиц)
или я не про то подумал?
чтото у тебя совсем результат не верный вышел, вот сам посмотри внимательно на "D"
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
28.01.2010, 18:32     Покрытие множеств
Еще ссылки по теме:

C++ объединение множеств
C++ Определить, существует ли покрытие C' из C мощности не более K
C++ Найти покрытие полным перебором

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

Или воспользуйтесь поиском по форуму:
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
28.01.2010, 18:32     Покрытие множеств #38
В начальных условиях ошибка!
Все числа записаны справа налево (старший разряд - 9-й), а С - наборот,
оно должно быть не 0х33, а 0х198.
Но все равно - с 10-м нулем непонятно.
Yandex
Объявления
28.01.2010, 18:32     Покрытие множеств
Ответ Создать тему
Опции темы

Текущее время: 13:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru