ДИСКРЕТНАЯ МАТЕМАТИКА (1). В. А. Ломазов р рязанов, Ю. Д. Дискретная математика учеб пособие. Ю. Д. Рязанов е изд, доп. Белгород Издво бгту, 2016. 298 с
 Скачать 4.33 Mb.
|
|
2.11.3. Все разбиения множества Рассмотрим все разбиения множества M. Теорема 2.15. Количество всех различных разбиений элементного множества М определяется формулой n k n n k Ф Ф 1 ) ( Доказательство. элементное множество можно разбить на одно подмножество, на два подмножества итак далее, на n подмножеств, те. количество k непустых подмножеств, на которые можно разбить элементное множество, может быть от 1 до n, отсюда количество всех различных разбиений элементного множества М определяется формулой n k n n k Ф Ф 1 ) ( Исходя из доказательства теоремы 2.15 можно порождать все разбиения элементного множества, многократно используя алгоритм порождения разбиений элементного множества на k подмножеств. Рассмотрим алгоритм порождения всех разбиений элементного множества Мне использующий другие алгоритмы. Пусть сформировано разбиение R i-1 i – элементного множества {1..i – 1} на p подмножеств. Из этого разбиения можно получить разбиение элементного множества {1..i} путем добавления элемента i в каждое подмножество M j и создания нового M p+1 ={i} подмножества, содержащего только один элемент i. Начнем формирование разбиений элементного множества с создания разбиения одноэлементного множества {1}, состоящего из этого же множества. Далее последовательно формируем разбиения двух, трехэлементного множества. Схема формирования всех разбиений множества M = {1,2,3} показана на рис. Задать разбиение элементного множества можно элементным вектором S, в котором S i — номер подмножества, которому принадлежит элемент i. Формирование го разряда вектора S соответствует определению подмножества разбиения, в которое добавляется элемент i. После добавления элемента n водно из подмножеств вектор S сформирован и разбиение получено. Схема формирования векторов S, соответствующих разбиениям множества M = {1,2,3}, показана на рис. Рекурсивный алгоритм 2.11 порождения всех разбиений элементного множества представлен на рис. При первом обращении i = 2, p = 1 и S i = 1. 101 {{1,2,3}} {{1,2}} {{1,2},{3}} {{1}} {{1,3},{2}} {{1},{2}} {{1},{2,3}} {{1},{2},{3}} Рис. Схема формирования разбиений множества M={1,2,3} (1,1,1) (1,1,?) (1,1,2) (1,?,?) (1,2,1) (1,2,?) (1,2,2) (1,2,3) Рис. Схема формирования векторов S, соответствующих разбиениям множества M = {1,2,3} 102 Алгоритм 2.11 порождения разбиений элементного множества. Вход i — заполняемое место в векторе S; p — количество подмножеств в разбиении. Выход последовательность всех векторов S, задающих разбиения. Глобальные параметры S — формируемый вектор n — мощность множества. + Рис. Рекурсивный алгоритм порождения разбиений элементного множества 2.12. Использование алгоритмов порождения комбинаторных объектов при проектировании полнопереборных алгоритмов решения задач выбора Задачи, для которых существует конечное множество М объектов, содержащее решение задачи, относятся к классу задач выбора. Элементы множества М называются траекториями задачи. Каждой траектории можно поставить в соответствие некоторую, как правило, числовую характеристику, называемую функционалом, позволяющую распознать траекторию, являющуюся решением задачи. Разбиение (i, p) x {1..p+1} S i := x Конец Разбиение (i+1, x) S 103 В общем случаев постановке задачи выбора может потребоваться 1) определить, существует ли решение 2) найти все решения задачи 3) определить значение функционала лучшего решения 4) найти одно или все лучшие решения. Для того, чтобы решить задачу выбора, можно организовать полный перебор всех траекторий и выбрать из них траекторию (траектории, удовлетворяющую условию решения задачи. Такие алгоритмы называют полнопереборными. Одним из методов организации перебора всех траекторий является метод поиска с возвращением, который мы использовали для порождения комбинаторных объектов. Алгоритмы порождения комбинаторных объектов также могут быть использованы для перебора всех траекторий. В этом случае проектирование алгоритма решения задачи выбора заключается в следующем 1) определение класса комбинаторных объектов, содержащих решение задачи 2) определение способа вычисления функционала 3) определение способа распознавания решения по значению функционала. Алгоритм решения задачи выбора представляет собой порождение комбинаторных объектов, содержащих решение задачи, вычисление функционала для каждого объекта и определение принадлежности объекта множеству решений. Для того, чтобы преобразовать алгоритм порождения комбинаторных объектов в алгоритм решения задачи выбора, достаточно заменить блок вывода сформированного объекта на блок, в котором вычисляется значение функционала для полученного объекта и определяется принадлежность объекта множеству решений. Рассмотрим примеры задач выбора и способы их решения. Задача 2.1. Дана последовательность из n целых чисел (n > 1) и целое число m. Определить, можно ли между каждой парой чисел в последовательности расставить знаки ―+‖ или ―–‖ так, чтобы получилось выражение, значение которого равно m. Решение Всего необходимо поставить n – 1 знаков. Каждому варианту расстановки знаков можно поставить в соответствие двоичный вектор, в котором значение 1(0) в м разряде соответствует знаку ―+‖ (―–―) между мим числом в последовательности. Траекториями задачи будут являться все двоичные n – разрядные вектора. Функционалом будет являться значение выражения, полученного из 104 заданной последовательности чисел путем расстановки знаков, соответствующих двоичному вектору. Пусть Р — исходная последовательность чисел, а D — двоичный вектор. Тогда значение выражения S можно вычислить последующему алгоритму 1. S := P 1 2. Для всех i от 1 до n – 1 выполнить S := S + (2*D i – 1)*P i+1 или, более наглядно 1. S := P 1 2. Для всех i от 1 до n – 1 выполнить если D i = 1 то S := S + P i+1 иначе S := S – P i+1 Если значение выражения S будет равно m, то двоичный вектор соответствует требуемой расстановки знаков, ответ будет положительными на этом заканчивается решение задачи. Если жени один вектор не определил требуемую расстановку знаков, то ответ будет отрицательным. Задача 2.2. На предприятии работают n рабочих. В выездной бригаде должны находиться рабочие, которые все вместе владеют заданными специальностями. Множество специальностей, которыми владеет каждый рабочий — известно. Необходимо сформировать бригаду из минимального числа рабочих. Решение Бригада из минимального числа рабочих представляет собой подмножество множества всех рабочих, поэтому траекториями данной задачи являются подмножества выбранных рабочих. Учитывая то, что требуется сформировать бригаду из минимального числа рабочих, целесообразно порождать подмножества в порядке увеличения мощности. Это можно сделать, применяя алгоритм порождения сочетаний. Сначала будем порождать сочетания из n поможет быть, один из рабочих владеет всеми необходимыми специальностями, затем — сочетания из n пои так далее до порождения сочетаний из n по n. Функционалом будет являться множество М специальностей, которыми владеет множество из k выбранных рабочих. Обозначим М — множество заданных специальностей, S i — множество специальностей, которыми владеет й рабочий, С — сочетание из n по k, записанное в возрастающем порядке. Алгоритм вычисления функционала может быть следующим 1. MS := 2. Для всех i от 1 до k выполнить MS := MS S Ci Если при обработке очередного сочетания окажется, что M является 105 подмножеством MS, то бригада из минимального числа рабочих соответствует этому сочетанию, решение найдено. Если же M MS будет ложным для всех порожденных подмножеств, то это означает, что сформировать бригаду из имеющихся рабочих, владеющих совместно всеми заданными специальностями, невозможно, задача не имеет решения. Задача 2.3. Коммивояжер (агент по сбыту, отправляясь из своего города, должен ровно по одному разу посетить n – 1 заданных городов и вернуться назад, затратив при этом минимальную сумму на поездку. Какой маршрут ему выбрать, если затраты на проезд между городами заданы. Решение. Обозначим города 0, 1, … ,n–1, 0 — исходный город, C ij — стоимость проезда от города i до города j. Маршрут коммивояжера представляет собой последовательность (0, i, …, j, 0), состоящую из n + 1 элементов, причем первый и последний — 0 — фиксированный элемента остальные n – 1 — попарно неравные элементы. Эта часть последовательности, от второго элемента до предпоследнего, однозначно определяет маршрут коммивояжера и представляет собой перестановку множества {1..n – 1}, поэтому траекториями задачи будут всевозможные перестановки n – элементного множества. Функционалом будет являться стоимость маршрута, определяемого перестановкой P n – элементного множества. Алгоритм вычисления функционала может быть следующим 1. 0 , , 0 1 1 : n P P C C S 2. Для всех i от 2 до n-1 выполнить Обозначим стоимость маршрута, принятого за оптимальный — MinS, вначале это некоторое заведомо большое число. Если при обработке очередной перестановки получим S < MinS, то эту перестановку нужно запомнить как лучшую и MinS := S. Решение будет получено только после обработки всех (n – 1)! перестановок. 2.13. О неэффективности полнопереборных алгоритмов. Пример Полнопереборные алгоритмы решения задач выбора с использованием алгоритмов порождения комбинаторных объектов являются универсальными, достаточно простыми для проектирования и программирования, но время их выполнения может быть очень велико даже при небольших размерностях задачи (количестве исходных данных, причем настолько велико (может составлять годы или даже века, что о возможности их практического применения не может быть и речи. Поэтому, при проектировании таких алгоритмов, обязательно нужно теоретически оценивать время их работы на конкретных данных. Для решения некоторых задач выбора можно построить уникальные, быстрые алгоритмы, позволяющие быстро получить решение даже при больших размерностях задачи. Покажем это на примере. Рассмотрим задачу выбора, полнопереборный алгоритм ее решения и более эффективный алгоритм. Задача 2.4. Имеется n деталей. Каждая деталь должна быть обработана сначала на станке A, затем на станке B. Время обработки a i каждой детали на станке A задано в последовательности (a 1 ,a 2 ,…,a n ), а на станке B — в последовательности (b 1 ,b 2 ,…,b n ). Требуется определить такую последовательность обработки деталей, при которой время обработки всех деталей минимально. Решение Определим алгоритм вычисления времени обработки всех деталей при заданной последовательности обработки деталей. Пусть ak i-1 – время окончания обработки i – й детали на станке A. Следующую ю деталь можно начать обрабатывать на станке A в это же время и время окончания обработки й детали на танке A будет ak i = ak i-1 + Пусть bk i-1 – время окончания обработки i – й детали на станке B. Если это время больше времени ak i (риса) окончания обработки й детали на танке A, тов это же время bk i-1 можно начать обрабатывать ю детальна станке B и время окончания обработки й детали на танке B будет bk i = bk i-1 + b i . Если же время bk i-1 окончания i – й детали на станке B меньше ak i (рис.2.28,б), то начать обработку й детали на станке B можно только в ak i , а закончить — в bk i = ak i-1 + Станок A я деталь ak i-1 я деталь Станок B я деталь bk i-1 я деталь а) bk i-1 > Станок A я деталь ak i-1 я деталь Станок B я деталь bk i-1 я деталь простой б) bk i-1 < Рис. Определение времени окончания обработки й детали на станках A и B 107 Исходя из этого получаем простой алгоритм вычисления времени обработки последовательности деталей, представленный блок-схемой на рис, которое совпадает с окончанием обработки последней детали на станке B. + Рис. Алгоритм вычисления времени обработки последовательности деталей Естественно, это время зависит от порядка обработки деталей. Например, если рассматривать данные, приведенные в табл. 2.3, то время обработки последовательности деталей (1,2,3,4,5,6,7) будет 117. Время окончания обработки каждой детали на станках A и B для этой последовательности представлено в табл. 2.4. Таблица 2.3 Время обработки деталей на станках A и B Номер детали 1 2 3 4 5 6 7 Время обработки на станке А 20 16 8 6 14 14 20 Время обработки на станке B 21 18 12 10 10 8 18 i:=1,n ak:= Конец bk:=bk+b i ak:=0; bk:=0 Начало 108 Таблица 2.4 Время окончания обработки деталей на станках A и B Шаг обработки Номер детали Станок А Станок В 1 1 20 41 2 2 36 59 3 3 44 71 4 4 50 81 5 5 64 91 6 6 78 99 7 7 98 117 Если обрабатывать детали в последовательности (2,4,3,7,6,5,1), то время обработки всех деталей будет 119. Время окончания обработки каждой детали на станках A и B для этой последовательности представлено в табл. 2.5. Таблица 2.5 Время окончания обработки деталей на станках A и B Шаг обработки Номер детали Станок А Станок В 1 2 16 34 2 4 22 44 3 3 30 56 4 7 50 74 5 6 64 82 6 5 78 92 7 1 98 119 Для определения последовательности обработки деталей, при которой время обработки всех деталей минимально, можно использовать полнопереборный алгоритм решения задачи выбора. Траекториями задачи будут все перестановки деталей, в данном случае 7!=5040, функционал траектории – время обработки всех деталей в последовательности, соответствующей перестановки (траектории. Для решения задачи необходимо перебрать все траектории (5040), для каждой траектории вычислить функционал (алгоритм на рис) и выбрать траекторию с минимальным значением функционала. Для определения последовательности обработки 16-ти деталей на ЭВМ потребуется несколько лет. Можно предложить другой, более эффективный, алгоритм решения этой задачи 1. i1:=1 — номер наименьшего (по номеру) свободного места в решении Р i2:=n — номер наибольшего (по номеру) свободного места в решении Р. 109 2. Выполнить п n раз, n — количество деталей. 3. Найти минимум среди (a 1 ,a 2 ,…,a n ,b 1 ,b 2 ,…,b n ), где a i — время обработки й детали на станке A; b i — время обработки й детали на станке B. Если это a i , то P i1 := i (поставить ю детальна е место в решении) и i1 := i1+ 1, если же это b i , то P i2 := i и i2 := i2 + 1. Элементы и b i далее не рассматривать. Результат определения последовательности обработки 16-ти деталей этим алгоритмом на ЭВМ будет получен практически мгновенно. Поэтому алгоритму для данных (табл) получим последовательность. Время окончания обработки каждой детали на станках A и B для этой последовательности представлено в табл. 2.6. Таблица 2.6 Время окончания обработки деталей на станках A и Шаг обработки Номер детали Станок А Станок В 1 4 6 16 2 3 14 28 3 2 30 48 4 1 50 71 5 7 64 89 6 5 78 99 7 6 98 107 110 Практическое занятие 2.1 Алгоритмы порождения комбинаторных объектов Цель занятия изучить основные комбинаторные объекты, алгоритмы их порождения, программно реализовать и оценить временную сложность алгоритмов. Задания 1. Реализовать алгоритм порождения подмножеств. 2. Построить график зависимости количества всех подмножеств от мощности множества. 3. Построить графики зависимости времени выполнения алгоритмов п на вашей ЭВМ от мощности множества. 4. Определить максимальную мощность множества, для которого можно получить все подмножества не более чем за час, сутки, месяц, годна вашей ЭВМ. 5. Определить максимальную мощность множества, для которого можно получить все подмножества не более чем за час, сутки, месяц, годна ЭВМ, в 10 ив раз быстрее вашей. 6. Реализовать алгоритм порождения сочетаний. 7. Построить графики зависимости количества всех сочетаний из n по k от k при n = (5, 7, 9). 8. Реализовать алгоритм порождения перестановок. 9. Построить график зависимости количества всех перестановок от мощности множества. 10. Построить графики зависимости времени выполнения алгоритма п на вашей ЭВМ от мощности множества. 11. Определить максимальную мощность множества, для которого можно получить все перестановки не более чем за час, сутки, месяц, годна вашей ЭВМ. 12. Определить максимальную мощность множества, для которого можно получить все перестановки не более чем за час, сутки, месяц, годна ЭВМ, в 10 ив раз быстрее вашей. 13. Реализовать алгоритм порождения размещений. 14. Построить графики зависимости количества всех размещений из n по k от k при n = (5, 7, 9). 111 Практическое занятие 2.2 Разбиения множеств Цель занятия изучить различные разбиения множеств, алгоритмы их порождения, программно реализовать и оценить временную сложность алгоритмов. Задания 1. Реализовать алгоритм порождения всех упорядоченных разбиений элементного множества на k подмножеств. 2. Написать программу, формирующую таблицу Т (табл. 2.7), в которой строки соответствуют количеству n элементов в множестве, а столбцы — количеству k подмножеств в разбиении. Клетка таблицы Т n,k при k ≤ n должна содержать количество всех упорядоченных разбиений элементного множества на k подмножества при k > n клетка таблицы Т не заполняется. Таблица 2.7 Количество упорядоченных разбиений элементного множества на k |