Генерация подмножеств заданного множества

КОМБИНАТОРНЫЕ МЕТОДЫ РЕШЕНИЯ ОПТИМИЗАЦИОННЫХ ЗАДАЧ

Лекция 2

1:

1. Генерация подмножеств заданного множества:

- разработка генератора подмножеств на С++;

- решение задачи о рюкзаке.

2. Генерация сочетаний:

- разработка генератора сочетаний на С++;

- решение задачи об оптимальной загрузке.

3. Генерация перестановок:

- разработка генератора перестановок на С++;

- решение задачи о коммивояжере.

4. Генерация размещений:

- разработка генератора сочетаний на С++;

- решение задачи об оптимальной загрузке (с центровкой)

Особенность алгоритмов:

1. Невозможно использовать для задач большой размерности.

2. Применяются тогда, когда требуется:

- точное решение или достаточное решение;

- размерность задачи небольшая.

3. Сложность этих алгоритмов:

- является верхней оценкой сложности решения задач;

- не зависит от данных;

- улучшение возможно только в статистическом смысле.

2:

Комбинаторный анализ (комбинаторика, комбинаторная математика) – раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами.

Пусть – конечное множество мощности Множество всех подмножеств множества называется булеаном и обозначается Количество элементов булеана множества вычисляется по формуле

(1)

Алгоритм генерации множества всех подмножеств основывается на взаимно однозначном соответствии между элементами булеана множества и всеми целыми числами множества, записанными в двоичном виде. Следует сказать, что алгоритм имеет сложность и поэтому реально может применяться для множеств с небольшой мощностью. Например, генерация булеана множества мощностью на компьютере с тактовой частотой процессора 3 ГГц займет более 100 лет.

3:

Построение элементов булеана множества сводится к следующему алгоритму:

1. Пронумеровать элементы заданного множества начиная с нуля.

2. Сформировать битовую последовательность состоящую из двоичных нулей. Пронумеровать элементы этой последовательности справа налево, начиная с нуля.

3. Последовательно выполнить шаги 4 и 5 алгоритма раз.

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

5. Интерпретируя битовую последовательность как целое положительное число, увеличить это число на единицу.

4:

На рис. 1 представлен пример построения булеана для множества Во втором сверху прямоугольнике изображены элементы множества Над ними указаны их номера: для для для и для

Рис. 1. Генерация множества всех подмножеств

Под элементами множества изображен столбец битовых последовательностей. Каждая строка столбца соответствует состоянию последовательности при очередном прохождении шага 4 алгоритма. Слева от столбца указаны целые числа, которые являются интерпретацией битовых последовательностей как целых чисел в десятичной системе счисления.

Стрелки на рис. 2.1. указывают на строки другого столбца, который содержит элементы множества соответствующие битовым последовательностям. Каждая строка этого столбца содержит элементы одного из подмножеств множества

Разберем еще один пример: Требуется получить множество всех подмножеств:. По формуле 1 узнаем количество всех подмножеств – 2⁴ = 16.

5:

Порядковый номер	Запись в двоичном коде	Запись в общем виде

6:

Принципы реализации генератора на С++

1. Все генераторы должны иметь одинаковый интерфейс

2. Должна быть возможность применения нескольких генераторов одновременно.

3. Функции должны легко встраиваться в другие.

На рис. 2 и 3 представлена реализация генератора множества всех подмножеств на языке C++. Генератор реализован в виде структуры subset. Применение структуры позволяет создавать несколько экземпляров одного генератора и упростить его вызов в других программах.

7:

// Combi.h #pragma once namespace combi { struct subset// генератор множества всех подмножеств { short n,// количество элементов исходного множества < 64 sn,// количество элементов текущего подмножества *sset;// массив индексов текущего подмножества unsigned __int64 mask;// битовая маска subset(short n = 1);// конструктор(количество элементов исходного множества) short getfirst();// сформормировать массив индексов по битовой маске short getnext();// ++маска и сформировать массив индексов short ntx(short i);// получить i-й элемент массива индексов unsigned __int64 count();// вычислить общее количество подмножеств void reset();// сбросить генератор, начать сначала }; };

Рис. 2. Шаблон структуры генератора множества всех подмножеств

8-9:

// Combi.cpp #include "stdafx.h" #include "Combi.h" #include <algorithm> namespace combi { subset::subset(short n) { this->n = n; this->sset = new short[n]; this->reset(); }; void subset::reset() { this->sn = 0; this->mask = 0; }; short subset::getfirst() { __int64 buf = this->mask; this->sn = 0; for (short i = 0; i < n; i++) { if (buf & 0x1) this->sset[this->sn++] = i; buf >>= 1; } return this->sn; }; short subset::getnext() { int rc = - 1; this->sn = 0; if (++this->mask < this->count()) rc = getfirst(); return rc; }; short subset::ntx(short i) {return this->sset[i];}; unsigned __int64 subset::count() {return (unsigned __int64)(1<<this->n);}; };

Рис. 3. Реализация методов структуры subset

Структура subset имеет единственный конструктор, параметром которого является мощность исходного множества.

Для хранения текущего состояния генератора используются три переменные: n (мощность исходного множества, которая не должна превышать 63), sn (текущееколичество элементов массива индексов), sset (адрес нулевого элемента массива индексов) и mask (битовая последовательность). Первоначальное значение всех переменных инициализируются конструктором. Причем значения n и sset послеинициализацииостаются неизменными, а значения остальных переменных меняются в процессе работы генератора.

Помимо конструктора, структура содержит еще пять функций-членов.

Функция getfirst позволяет заполнить массив индексов в соответствии с текущим значением битовой последовательности mask. Функция устанавливает значение sn, равным количеству двоичных единиц в последовательности mask, а в массив sset,начиная с нулевого элемента, записывает номера единичных позиций (позиции нумеруются справа налево) в последовательности mask. Вызов функции сразу после создания структуры приводит к установке значения sn в нуль, что соответствует битовой последовательности mask, состоящей из одних нулей (конструктор инициализирует mask нулевым значением). Функция getfirst всегда возвращает значение sn. Обычно пользователь эту функцию вызывает один раз – для формирования первого (пустого) подмножества. Для получения остальных подмножеств применяется функция getnext.

Функция getnext увеличивает значение mask на единицу и вызывает функцию getfirst, которая формирует новый массив индексов и sn в соответствии с новым значением mask. Функция getnext возвращает значение sn, если массив индексов сформирован. Последний вызов функции возвращает значение – 1.

Функция ntx возвращает значение элемента массива индексов по индексу этого элемента и служит для сокращения записи при переборе элементов массива.

Функция count вычисляет и возвращает количество элементов булеана заданного множества.

Для перевода генератора в начальное состояние служит функция reset. После вызова reset снова могут вызываться getfirst и getnext.

На рис. 4 и 5 приведен пример применения генератора множества всех подмножеств и результат выполнения программы.

9-10:

// Main #include "stdafx.h" #include <iostream> #include "Combi.h" int _tmain(int argc, _TCHAR* argv[]) { setlocale(LC_ALL, "rus"); char AA[][2]= {"A", "B", "C", "D"}; std::cout<<std::endl<<" - Генератор множества всех подмножеств -"; std::cout<<std::endl<<"Исходное множество: "; std::cout<<"{ "; for (int i = 0; i < sizeof(AA)/2; i++) std::cout<<AA[i]<<((i< sizeof(AA)/2-1)?", ":" "); std::cout<<"}"; std::cout<<std::endl<<"Генерация всех подмножеств "; combi::subset s1(sizeof(AA)/2);// создание генератора int n = s1.getfirst();// первое (пустое) подмножество while (n >= 0)// пока есть подмножества { std::cout<<std::endl<<"{ "; for (int i = 0; i < n; i++) std::cout<<AA[s1.ntx(i)]<<((i< n-1)?", ":" "); std::cout<<"}"; n = s1.getnext();// cледующее подмножество }; std::cout<<std::endl<<"всего: " << s1.count()<<std::endl; system("pause"); return 0; }

Рис. 4. Пример применения генератора множества всех подмножеств

В качестве исходного множества в примере используется строковый массив, состоящий из четырех строк. Вначале этот массив распечатывается. Затем объявляется структура subset и ей в качестве параметра передается количество элементов исходного множества (значение).

Цикл формирования подмножеств начинается функцией getfirst,которая формирует первый (пустой) массив sset, соответствующий пустому подмножеству. Все остальные массивы индексов (для непустых подмножества) формируются функцией getnext. Выход из цикла происходит после того, как getnext возвращает отрицательное значение (получены все подмножества). Выбор элементов исходного массива осуществляется с помощью функции ntx.

11:

Рис. 5. Результат выполнения программы, представленной на рис. 4

Сложность:

12:

Дата добавления: 2014-01-20