- •Проектирование полнопереборных алгоритмов
- •Содержание
- •1.1. Основные понятия и определения
- •1100, 1010, 1001, 0110, 0101, 0011.
- •1.2. Общие подходы к порождению комбинаторных объектов
- •1.3. Алгоритмы порождения подмножеств
- •1.4. Алгоритмы порождения сочетаний
- •1.5. Алгоритмы порождения перестановок
- •1.6. Алгоритм порождения размещений
- •1.7. Алгоритмы порождения композиций
- •1.8. Алгоритм порождения разбиений
- •2. Проектирование алгоритмов, основанных на полном переборе траекторий задачи выбора
- •2.1. Понятие задачи выбора
- •2.2. Комбинаторный поиск
- •Поиск с возвращением
- •Метод решета
- •2.3. Использование алгоритмов порождения элементарных комбинаторных объектов при проектировании полнопереборных алгоритмов решения задач выбора
- •3. Некоторые вопросы теории сложности
- •4. Задания для самостоятельной работы
- •4.1. Порождение подмножеств
- •4.2. Порождение перестановок
- •4.3. Порождение сочетаний и размещений
- •4.4. Порождение композиций и разбиений
- •4.5. Решение комбинаторных задач
- •4.6. Проектирование полно переборных алгоритмов
- •Список литературы
- •Генерация случайных чисел
- •Приложение 2 функции времени языка Turbo Pascal
- •Текст программы на языке Turbo Pascal реализующей точный алгоритм решения задачи о рюкзаке
- •Проектирование полнопереборных алгоритмов
- •308012, Белгород, ул. Костюкова, 46.
1100, 1010, 1001, 0110, 0101, 0011.
Таким образом, каждому сочетанию из m по n соответствует последовательность из n единиц и m-1 нулей. Число таких последовательностей равно числу способов, которыми можно выбрать m-1 мест для нулей из n+m-1 общего числа мест (), или то же самое числу способов выбораn мест для единиц из n+m-1 мест (). Равенство следует из равенства .
Композиции и разбиения. Пусть стоит задача порождения разбиения положительного числа n в последовательность неотрицательных целых чисел {p1,p2,…,pk}, так что p1+p2+…+pk=n причем на рi могут накладываться различные ограничения.
Если порядок чисел рi важен, то (p1,p2,…,pk) называется композицией n. Поиск композиций ведется с ограничением рi>0.
Если k фиксировано, то такие композиции называются композициями n из k частей. При их поиске ограничение рi>0 может сниматься, т.е. разрешается рi=0.
Если порядок рi не важен и рi>0, то {p1,p2,…,pk} является мультимножеством и называется разбиением n.
Поясним различие между композициями, композициями из k частей и разбиениями на следующем примере:
n=3,
композиции: (3), (1,2), (2,1), (1,1,1),
композиции из двух частей (рi>0): (1,2), (2,1),
композиции из двух частей (рi0): (0,3), (1,2), (2,1), (3,0),
разбиения: {3}, {1,2}, {1,1,1}.
Теорема. Число композиций n равно 2n-1.
Доказательство. Разделим отрезок длины n на n отрезков единичной длины с помощью (n-1) точки. Тогда композиции n взаимно однозначно соответствует пометка некоторых из точек разделения. Элементами композиции в этом случае будет расстояние между смежными точками. Например, композиция (2,2,1), n=5 представлена на рис.1.
Следовательно, каждая композиция nсоответствует способу выбора подмножества из (n-1) точек. То есть число композицийnравно 2n-1.
Теорема. Число композицийnизkчастей с ограничениемрi>0 равно.
Доказательство. Представим композицию также как при доказательстве предыдущей теоремы. Каждая композицияnизkчастей (рi>0) соответствует способу выбора (k-1)-элементного подмножества точек изn-1 точек. То есть число таких композиций равно.
Теорема. Число композиций n из k частей, если pi0 равно .
Доказательство. Каждой композицииnизkчастей прирi0 взаимно однозначно соответствует двоичный набор, такой, что первое слагаемое равно числу единиц, стоящих перед первым нулем в наборе, второе -числу единиц, стоящих перед первым и вторым нулями, и т.д. Пример такого представления композицииn=4,k=3 приведен в табл.1.
Длина набора равна n+k-1,число нулей равноk-1,следовательно, число наборов (искомых композиций) равно числу способов выбораk-1 мест для нулей изn+k-1 мест ()или тоже самое числу способов выбораnмест для единиц изn+k-1 мест ().
Таблица 1.
№ |
Композиция |
Двоичный набор |
Сочетание из 6 по 2 |
1 |
0+0+4 |
0 0 1 1 1 1 |
1 2 |
2 |
0+1+З |
0 1 0 1 1 1 |
1 3 |
3 |
0+2+2 |
0 1 1 0 1 1 |
1 4 |
... |
... |
... |
... |
13 |
3+0+1 |
1 1 1 0 0 1 |
4 5 |
14 |
3+1+0 |
1 1 1 0 1 0 |
4 6 |
15 |
4+0+0 |
1 1 1 1 0 0 |
5 6 |
Доказательство данной теоремы можно было также получить путем установки взаимно однозначного соответствия между данными композициями и множеством всех сочетания из k элементов по n с повторениями.