- •Проектирование полнопереборных алгоритмов
- •Содержание
- •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.
1.4. Алгоритмы порождения сочетаний
Без ограничения общности можно полагать, что элементами множества являются целые числа от 1 да n.
Рассмотрим алгоритм порождения сочетаний в возрастающем лексикографическом порядке, т.е. в порядке, когда в каждом сочетании элементы расположены в порядке возрастания слева направо. Например, сочетания из шести элементов по три (), в возрастающем лексикографическом порядке запишутся следующим образом:
123 135 234 256
124 136 235 345
125 145 236 346
126 146 245 356
134 156 246 456
Сочетания в лексикографическом порядке можно порождать следующим образом. Начиная с сочетания (1,2,...,k), следующее сочетание находится просмотром текущего сочетания справа налево с тем, чтобы определить место самого правого элемента, который не достиг еще своего максимального значения. Этот элемент увеличивается на единицу, и всем элементам справа от него присваиваются новые наименьшие возможные значения как показано в алгоритме 4.
Эффективный метод порождения случайных сочетаний из n по k осуществляют случайные перестановки на первых k местах множества, например, такие, как в алгоритме 5.5
1.5. Алгоритмы порождения перестановок
Также как и при генерации сочетания будем считать, что элементами множества являются целые числа от 1 до n.
Последовательность перестановок на множестве {1,2,...,n} представлена в лексикографическом порядке, если она записана в порядке возрастания получающихся чисел. Например, лексикографическая последовательность перестановок трех элементов имеет вид 123, 132, 213, 231, 312, 321.
Порождать такую последовательность можно следующим образом. Начиная с перестановки Р=(1,2,...,n), переходим к следующей, путем просмотра текущей справа налево с целью поиска самой правой позиции, в которой рi<рi+1. Найдя ее, ищем рj, наименьший элемент, расположенный справа от рi и больше его. Затем осуществляется транспозиция элементов рi и pj и отрезок рi+1,...,рn (элементы которого расположены в порядке убывания) переворачивается. Например, для n=8 имеем текущую перестановку p=(2,6,5,8,7,4,3,1), тогда рi=5 (i=3) и рj=7 (j=5). Меняя их местами и переворачивая p4,p5,p6,p7,p8, получаем следующую перестановку (2,6,7,1,3,4,5,8). Эту процедуру реализует алгоритм 6.
Рассмотрим еще один алгоритм порождения перестановок. Этот алгоритм генерирует перестановки в порядке минимального изменения, т.е. перестановка отличается от предшествующей транспозицией двух соседних элементов.
Такую последовательность перестановок можно построить рекурсивно. Для n=1 существует единственная перестановка (1). Предположим, что построена последовательность перестановок П1,П2,...,П(n-1)! на множестве {1,2,...,n-1} в порядке минимального изменения.
Расширим каждую из (n-1)! этих перестановок путем вставки элемента n на каждое из n возможных мест. Причем, элемент n добавляется к Пi последовательно во все позиции справа налево, если i нечетное, и слева направо, если i четное. Пример такого расширения представлен на рис .2.
Эту же последовательность перестановок можно порождать итеративно, получая каждую перестановку из предшествующей и добавочной информации. Это делается с помощью трех векторов: текущей перестановки Р=(р1,...,рn), обратной к ней перестановки0=(о1,...,оn)6(о1- индекс наименьшего элемента вР,о2- индекс следующего по величине элемента вРи т.д., следовательно,) и записи направленияD=(d1,...,dn), в котором сдвигаются элементы перестановки (di=-1, еслиpiсдвигается влево,di=1 - вправо,di=0 - не сдвигается). Элемент сдвигается до тех пор, пока не достигнет элемента большего чем он сам; в этом случае сдвиг прекращается. В этот момент направление сдвига данного элемента изменяется на противоположное и передвигается следующий меньший его элемент, который можно сдвинуть. Поскольку хранится перестановка, обратная кР, то вРлегко найти место следующего меньшего элемента. Эту процедуру реализует алгоритм 7.
Заметим, что в алгоритме 7 Р0 и Pn+1 инициализируются величиной n+1, чтобы прекратить передвижение n, и d1 инициализируется нулем, чтобы в тех случаях, когда m становятся равным единице во внутреннем цикле, остаток внешнего цикла был правильно определен.
Алгоритм порождения случайных перестановок (алгоритм 8) аналогичен алгоритму порождения случайных сочетаний (алгоритм 5).