РОЗДІЛ 2
УТВОРЕННЯ І ВПОРЯДКУВАННЯ КОМБІНАТОРНИХ КОНФІГУРАЦІЙ
У цьому розділі аналізуються властивості комбінаторних конфігурацій, які є
аргументом цільової функції в задачах комбінаторної оптимізації. Вводяться три
рекурентні комбінаторні оператори, завдяки яким утворюються різноманітні типи
цих об'єктів. Досліджується структура їхніх множин. Показано, що вони
складаються з підмножин ізоморфних комбінаторних конфігурацій. Знання структури
цих множин важливе при розв'язанні задач комбінаторної оптимізації, в яких
пошук оптимального значення цільової функції проводиться як на всій такій
множині, так і на їхніх підмножинах.
Проведений аналіз дає можливість виявити властивість періодичності, що
характерна для упорядкування різних типів комбінаторних конфігурацій [233–235].
Показано, що за одними і тими самими правилами упорядковуються різні типи
комбінаторних конфігурацій, а деякі з цих об'єктів генеруються різними
модифікаціями одного і того самого алгоритму.
На прикладі розбиття натурального числа і розбиття -елементної множини на
підмножини показано, що описану властивість періодичності можна
використо-вувати і для розв'язування перелічувальних задач.
2.1. Поняття комбінаторної конфігурації
Аргументом цільової функції в задачах комбінаторної оптимізації є комбінаторні
об'єкти (перестановки, сполучення, розбиття множини на підмножини та ін.). Для
побудови математичних моделей задач цього класу, які відображають їхню
комбінаторну природу важливо визначити тип цих об'єктів і знати їхні характерні
властивості. Як було оговорено вище, в таких задачах, як задача комівояжера,
розміщення, задача про призначення, аргументом цільової функції є перестановка.
В задачі про рюкзак, або задачах, які вимагають побудови блок-схем пошук
оптимального розв'язку проводиться на множині сполучень. Задачі про передачу
сигналів, які мають місце в теорії інформатики, оптимальне розподілення
оперативної пам'яті при організації обчислювального процесу вимагають знання
властивостей розбиття числа. Аргументом цільової функції задач теорії розкладу
або задач, зв'язаних з виконанням кінцевих або проміжних комплексів операцій,
виступає розміщення. Великий клас задач розбиття з'являється у самих
різноманітних постановках: розбиття множини, розрізування графів, мереж,
кластеризація, таксономія, класифікація. Вони полягають в упорядкуванні заданих
об'єктів у порівнянно однорідні групи, тобто за розробленими правилами
проводиться пошук розбиття заданої множини на підмножини. В задачах, що
вимагають знаходження оптимальної укладки електричних схем на одній або кількох
поверхнях, аргументом цільової функції виступає граф.
Комбінаторні об'єкти об'єднують поняттям комбінаторні конфігурації [3, 16]. Їх
ще називають рекурсивними функціями. В літературі комбінаторну конфігурацію
визначають таким чином [3]. Задано , . На заданий строгий лінійний порядок .
Відображення , що задовольняє деякому комплексу обмежень , називають
конфігурацією. Комплекс обмежень , якому задовольняє відображення , визначає
деякий клас конфігурацій, що відповідає умовам на комбінаторні конструкції в
задачі, що розглядається.
Нижче розглянемо деякі властивості комбінаторних конфігурацій і способи їхнього
утворення. Оскільки не існує загального підходу, за яким потрібно
кваліфі-кувати комбінаторні об'єкти, то деякі автори одну і ту ж комбінаторну
конфігурацію називають різними термінами або під одним поняттям об'єднують
декілька.
Наведемо найпростіші відомі комбінаторні конфігурації [1–11, 15, 17–24, 26, 41,
236–244] і уведемо оператори, за допомогою яких вони утворюються [234, 235,
245].
Вибірки. З поняттям вибірки зв'язують як саму операцію виділення підмножин
заданої множини, так і її результат: вибрану підмножину. В подальшому маємо на
увазі друге поняття.
Нехай задано множину . З неї одержимо -вибірку. Число називають об'ємом
вибірки. В -вибірках в залежності від умов задачі або ураховується порядок
розташування в них елементів (тоді їх називають -перестановками або
-розміщеннями) або не ураховують. У цьому випадку вони називаються
-сполученнями. Перестановкою називають упорядковану вибірку з елементів множини
по . Множина всіляких неупорядкованих вибірок (сполучень), яка містить одну
пусту, називають ще множиною всіх підмножин[4, 15]. Оскільки потужність множини
неупорядкованих вибірок без повторень дорівнює , то її порівнюють з бінарними
послідовностями.
Деякі автори поняття вибірка використовують лише при висвітленні прикладних
питань, інші вважають, що вибірка – це -сполучення і -перестановки [2], і
уводити поняття "розміщення" немає необхідності. В [31] уводиться -вибірка, яка
є підмультимножиною у мультимножині .
Отже існують такі типи вибірок: упорядковані і неупорядковані.
Неупорядковані – це сполучення без повторень і сполучення з повтореннями.
Упорядковані - це розміщення з повтореннями і розміщення без повторень. Вибірки
різних типів позначимо , де – кількість елементів у , а їх всіляку множину – як
.
Сполучення. Сполученням назвемо неупорядковану вибірку з елементів по, у якій
можна як допускати так і не допускати повторень, .
Розглянемо сполучення без повторень. Вважаємо, що в не існує , тоді кількість
усяких сполучень без повторень дорівнює .
Оскільки будь-яке сполучення утворюється вибиранням відповідних елементів із
початкової множини , то цю операцію назвемо операцією вибирання і позначимо її
, .
Сполучення як з повтореннями так і без повторень утворюються єдиною операцією –
вибиранням.
Перестановки. У комбінаторній оптимізації аргументом цільової функції багатьох
задач виступають перестановки. Цю комбіна
- Киев+380960830922