Форум программистов, компьютерный форум 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++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
19.01.2010, 21:24     Покрытие множеств #2
Видимо, 1-9 - элементы множества
A - G -сами множества
Между ними - матрица инцендентности
А что означает столбец (a) ?
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
19.01.2010, 22:08  [ТС]     Покрытие множеств #3
извините, забыл указать, что последний столбец - цена множества. после нахождения покрытий также можно находить самое дешевое.
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
20.01.2010, 11:25     Покрытие множеств #4
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
#include <stdio.h>
 Для начала будем считать что мощность множества N < 32 = sizeof(long)
 Тогда полное множество делается так:
  long U = 0;
  for(i=0; i<N; i++) U |= (1L<<i);
 Для полного перебора тоже используем шкалу
  long P = 0;
  for(i=0; i<n; i++) P |= (1L<<i);  // n - Кол-во множеств
 Пусть множества заданы числами long A[n]
 ( A[i] & (1L << j)) = 1 тогда и только, когда i-тое множество
                         содержит j-тый элемент
  double a[n]; - Веса
  double s; // цена покрытия
  long X = 0; // X содержит множества, участвующие в пробном покрытии
  long Y;  // Частичное покрытие
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {  // Покрытие найдено
        s = 0;
        for (j=0; j<i; j++) { // Печать найденного покрытия и его цены
          if (X & (1L<<j)) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if (X & (1L<<i)) Y = (Y | A[i]);
    }
    X++;
  }
Это только идея. Возможны опечатки.
Перебор почти полный (отбрасываются остатнии множества, когда все покрыто).
Если N>=32, тогда надо находить другое представление множеств.
1) Как массива long и сделать маленькие фунциклюшки работы с битами
для массива (присвоение i-того бита, проверка i-того бита, сравнение
двух массивов и т.д.)
2) Как строки символов равных 1 или 0. Легче для программирования,
но неэкономно по памяти (в 8 раз)
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
20.01.2010, 15:30  [ТС]     Покрытие множеств #5
Цитата Сообщение от Day Посмотреть сообщение
Это только идея. Возможны опечатки.
Перебор почти полный (отбрасываются остатнии множества, когда все покрыто).
спасибо! я именно пример этого способа и искал)
буду признателен если подробнее поможете разобраться

U |= (1L<<i);
это битовый сдвиг влево на позицию "i" с доставкой "1" бита в конец?
таким образом у нас будет выходить
1
11
111
1111
и тд
тоесть
1
3
7
15
какой вид массива А[n] будет? я не совсем понял.. A[n]= { {1},{2},{3}, ... {n} } ?
Я так понял, что этот кусочек не есть кодом программы
( A[i] & (1L << j)) = 1 тогда и только, когда i-тое множество
содержит j-тый элемент
но как это выражение может быть равно 1? можно пример на числе каком-то.

пока что без осмысления этих вещей не могу пройтись далее по коду. =)
insideone
Модератор
Автор FAQ
 Аватар для insideone
3620 / 898 / 47
Регистрация: 10.01.2010
Сообщений: 2,421
20.01.2010, 15:39     Покрытие множеств #6
1011 0011 0000 1110 // A[i]
&
0000 0000 0000 1000 // ==
//0000 0000 0000 0001 << 3 // 1L << 3
Результат: 1&1 = 1

1011 0011 0000 1110 // A[i]
&
0000 0000 0001 0000 // ==
//0000 0000 0000 0001 << 4 // 1L << 4
Результат: 0&1 = 0

На самом деле & пробегает по всем битам, однако т.к. остальные биты нулевые в нашем 1L то результат тоже будет нулевым для других бит. Вроде так =))
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
20.01.2010, 15:49  [ТС]     Покрытие множеств #7
insideone, спасибо, это понял)

осталось понять формат массива A[n]
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
21.01.2010, 12:31     Покрытие множеств #8
U |= (1L<<j) - Да это так.
В U получается столько единиц, какова мощность всего множества

(A[j] & (1L<<j)) == 1 - Простите, ошибочка моя
Правильно
(A[j]&(1L<<j)) != 0
Или
((A[j]>>j) & 1) == 1
Для твоего примера
A = 10100010
B = 101001010
....
Рекомендация.
Осторожнее с битовыми операциями!
В C приоритеты не очень логично проставлены
На всякий случай заключайте их в скобки
У == приоритет больше, чем у &&
Но если скобок не жалеть - все будет хорошо
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
21.01.2010, 16:49  [ТС]     Покрытие множеств #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
46
int N=7,n=9,j,i=0;
 
// Togda polnoe mnojestvo delaetsya tak:
  long U = 0;
  for(i=0; i<7;i++ )
   {
   U |= (1L<<i);
 
    }
// Dlya polnogo perebora toje ispol'zuem shkalu
  long P = 0;
  for(i=0; i<n; i++)
  {
     P |= (1L<<i);
   }
 
 
  double a[9]; //vesa
  double s; // cena
  /// Pust' mnojestva zadany chislami long A[n]
  long A[7]={ {10100010}, {101001010}, {110011},
                 {100100100},{1010001},{1101},{10110101},};
  long X = 0; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  long Y;  // Chastichnoe pokrytie
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) { 
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )
       {
          Y = (Y | A[i]);
       }
    }
    X++;
  }
}

я правильно понял как должны задаться множества?
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
22.01.2010, 10:58     Покрытие множеств #10
Вроде, все правильно.
Только этот кусочек мы то с тобой понимаем, а транслятор может и не понять
long A[7]={ {10100010}, {101001010}, {110011},
{100100100},{1010001},{1101},{10110101},};
Лучше так
Код
long  A[7] = { 0xA2, 0x14A, 0x63, 0x124, 0x51, 0xD, 0xb5 };
Т.е записываем в 16-й системе
(Мог ошибиться в циферках)
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
22.01.2010, 16:06  [ТС]     Покрытие множеств #11
да, только 3ий елемент 0х33.


тестирую вот программу.
выводит:
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
C E F s=5.000000
странно, эти множества даже не создают покрытие...
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
22.01.2010, 18:14     Покрытие множеств #12
0x33 - Согласен
Будь добр, пришли исходник тестируемой проги
(в предпоследем твоем посте вариант явно не рабочий - даже a[j] не инициализированы)
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
22.01.2010, 18:32  [ТС]     Покрытие множеств #13
извините) я думал, что запостил)
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
#include <stdio.h>
#include <iostream.h>
#include <string.h>
#include <conio.h>
#include <alloc.h>
void main() {
clrscr();
int N=7,n=9,j,i=0;
 
// Togda polnoe mnojestvo delaetsya tak:
  long U = 0;
  for(i=0; i<7;i++ )
   {
   U |= (1L<<i);
 
    }
// Dlya polnogo perebora toje ispol'zuem shkalu
  long P = 0;
  for(i=0; i<n; i++)
  {
     P |= (1L<<i);
   }
 
 
  double a[9]={ {1}, {3}, {2}, {2}, {1}, {2}, {3} }; //vesa
  double s; // cena
  /// Pust' mnojestva zadany chislami long A[n]
 long  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xb5 };
 
  long X = 0; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  long Y;  // Chastichnoe pokrytie
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )
       {
          Y = (Y | A[i]);
       }
    }
    X++;
  }
}
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
23.01.2010, 00:08     Покрытие множеств #14
Основная ошибка - было перепутано N и n
Окромя того я все делал на чистом С, а он, дурачок, не понимает объявлений переменных
внутри функции, только в начале понимает
С++ и вся его мощь тут не нужны.
Так что переставил кой чего
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
#include <stdio.h>
// #include <iostream.h>
#include <string.h>
#include <conio.h>
// #include <alloc.h>
 
void main()
{
 int N = 7;  // kol-vo podmnogestv
 int n = 9;  // kol-vo elementov polnogo mnogestva
 int j, i;
 // double a[9]={ {1}, {3}, {2}, {2}, {1}, {2}, {3} }; // Eta stroka ne dolgna compilirovatsiy
 double a[7]={ 1, 3, 2, 2, 1, 2, 3 }; //vesa
  // Pust' mnojestva zadany chislami long A[n]
 long  A[7] = { 0xA2, 0x14A, 0x33, 0x124, 0x51, 0xD, 0xb5 };
 long U, P, X;
 long Y;  // Chastichnoe pokrytie
 double s; // cena
 
//  clrscr();
 
// Togda polnoe mnojestvo delaetsya tak:
  U = 0;
  for(i=0; i<n;i++ )   U |= (1L<<i);
// Dlya polnogo perebora toje ispol'zuem shkalu
  P = 0;
  for(i=0; i<N; i++)   P |= (1L<<i);
  X = 1; // X soderjit mnojestva, uchastvuyuschie v probnom pokrytii
  while(X!=P) {
    Y = 0;
    for(i=0; i<n; i++) {
      if (Y==U) {
        s = 0;
        for (j=0; j<i; j++) { // Pechat' naydennogo pokrytiya i ego ceny
          if ( (X & (1L<<j))!=0 ) {
            printf("%c ", 'A'+j);
            s += a[j];
          }
        }
        printf("s=%f\n", s);
        break;
      }
      if ( (X & (1L<<i))!=0 )  Y = (Y | A[i]);
    }
    X++;
  }
}
Что-то получается, но я не проверял, уж ты сам, будь добр, этим займись.
Если что-то будет не так - вставляй отладочные печати непонятных переменных
Если печатей этих будет слишком много: перенаправь стандартный вывод:
...exe >файл

ЗЫ. 1. Какова причина замена русских слов латиницей? Ты здесь не один такой -
так очень многие делают. Т.е. причина какая-то есть. Мне интересно - какая.
2. Пожалуйста! (и всем, кому сможешь, передай) Старайтесь делать грамотно отступы.
Чтобы операторы одного блока (между { ... } ) начинались друг под другом
Мучительно разбираться в проге с отступами в стиле шаляй-валяй. Ты и сам когда-нибудь
это поймешь.
Когда я вижу в коде этот раскардаш, как правило, тут же тему пропускаю.
Тебе повезло - задачка любопытная, и я нашел в ней новый ход.
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
23.01.2010, 00:31  [ТС]     Покрытие множеств #15
1. Borland C под Dos понимает русские слова только под утилитой keyrus =)
2. *позор* я понимаю это и сам часто одногрупникам обьясняю, но в таких программах, где мало кода частенько забываю об этом)

да, очень благодарен за то, что взялись помочь
сейчас буду проверять.

Добавлено через 7 минут
вставляй отладочные печати непонятных переменных
как?)

вот первое же покрытие выдало : A B C D, неправильное.
но второе A B D E правильное.
третим повторило A B C D
4 - A B C F, тоже правильное
5 - опять повторило A B C D
6 - A B E F, правильное
ну вот пока видно, что только на A B C D проштрафилось..
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
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
lego69
 Аватар для lego69
3 / 3 / 1
Регистрация: 19.01.2010
Сообщений: 26
23.01.2010, 17:47  [ТС]     Покрытие множеств #17
оо, вообще супер. правда выходит так, что оно все-таки делает повторы.
я имею ввиду с множествами, которые входят в предыдущие.
B G входит в A B E G
ну наверно с этим ничего не поделать, так что спасибо и за это
Веталька
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
23.01.2010, 18:29     Покрытие множеств #18
прошу прощения пост вышел совершенно случайно и был удален
Day
 Аватар для Day
1149 / 954 / 57
Регистрация: 29.10.2009
Сообщений: 1,384
23.01.2010, 18:36     Покрытие множеств #19
Но это РАЗНЫЕ покрытия!
Об оптимальности мы еще не говорили...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
23.01.2010, 18:53     Покрытие множеств
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
Веталька
0 / 0 / 0
Регистрация: 23.01.2010
Сообщений: 6
23.01.2010, 18:53     Покрытие множеств #20
оо, вообще супер. правда выходит так, что оно все-таки делает повторы.
я имею ввиду с множествами, которые входят в предыдущие.
B G входит в A B E G
ну наверно с этим ничего не поделать, так что спасибо и за это
ну так ето метод полного перебора и покрытия выводятся все....или я ошибаюсь?
Yandex
Объявления
23.01.2010, 18:53     Покрытие множеств
Ответ Создать тему
Опции темы

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