льних завданнях більше кількості занять, а стало бути навіть не дуже об'ємна задача теорії розкладу вимагає ресурсів суперкомп'ютера.
Невелике, але важливе доповнення.
Чому не можна взяти перший-ліпший варіант? А тому, що на розклад накладається ряд умов виконання яких неможливе при довільному варіанті (наприклад відсутність дірок у розкладі класу). Цих умов зазвичай дуже багато, і вони різко скорочують кількість допустимих варіантів. Фактично їх так мало, що ймовірність натрапити на допустимий варіант на самому початку перебору практично дорівнює нулю.
Що ж робити?
Сподіваюся, вище я досить ясно показав безнадійність нашого становища. Лобова атака на задачу нічого не дасть. Тому єдиний вихід - це змінити ставлення до задачі. Наприклад, ми можемо відмовитися від наміру отримати гарантовано ідеальне рішення за короткий час. А давайте сформулюємо наші наміри дещо інакше.
Тепер ми бажаємо просто максимально збільшити ймовірність виявлення досить гарного варіанта за обмежений час. Ми пом'якшили свої запити, і тепер можемо розраховувати на успіх. Але спочатку опишемо завдання в більш суворих термінах.
Позначення:
А - Безліч занять
а - Заняття
В - безліч вакансій
в - Вакансія
( а, в) - допустима пара розкладу, тобто пара не суперечить вимогам накладаються на розклад.
Цілком можливо, що для елемента а існує кілька допустимих пар розкладу. А якщо це можливо для елемента а, то отже можливо і для елемента в. Таким чином можна ввести ще два важливих поняття:
У а - безліч всі елементів в які можуть брати участь у допустимих парах розкладу з елементом а.
А в - безліч всі елементів а які можуть брати участь у допустимих парах розкладу з елементом в.
Тоді розкладом назвемо таке безліч допустимих пар розкладу в якому кожен елемента множини А присутній рівно один разів.
Таким чином, розклад це елемент множини всіх множин допустимих пар. А складання розкладу тоді математично зводиться до пошуку потрібного елемента серед уже згаданого безлічі всіх множин допустимих пар (позначимо його як D).
3. Безліч D
На перший погляд воно влаштоване безладно. Однак це не так: візьмемо небудь елемент цієї множини d. Він являє собою безліч допустимих пар. Цілком очевидно, що для даного елемента існує (і бути може не один) елемент d ' що відрізняється від d на одну пару і при цьому d> d '. скажімо тоді, що елементи d і d ' пов'язані між собою відношенням слідування d В® d '. Очевидно, що кожен елемент безлічі D пов'язаний ставленням хоча б з одним елементом. Якщо тепер, ми розташуємо елементи множини D на площині і ті елементи які знаходяться між собою щодо проходження з'єднаємо стрілками, то отримаємо зв'язний орієнтований граф. Це для тих хто знає, що таке зв'язний орієнтований граф. Якщо хто не знає, то нехай не засмучується, для нашої задачі не важно як це називається, важливо уявити собі цю картинку. А виглядає вона приблизно так. <В
Тоді процес пошуку елемента d є розкладом є ніщо інше як шлях вздовж стрілок ведучий до шуканого елементу.
Загалом це і є модель. Ми звели пошук розкладу до пошуку шляху на орієнтованому графі. А орієнтований граф це структура, про якої в математиці відомо досить багато і тепер ми можемо обрушити на задачу всю міць теорії графів. Але давайте припустимо, що більшість з нас оной теорією не володіють, і продовжимо пошук рішення.
Але дещо що з моделі графа ми візьмемо. Зауважимо, що кожен шлях на графі обов'язково закінчується вузлом, з якого не виходить жодна гілка. Тобто з цих вузлів продовжувати пошук розкладу не можна, а це означає, що має місце одна з двох ситуацій:
Розклад вже складено.
Розклад не складено, але для деяких елементів а немає жодного елемента в. Будемо називати далі цю ситуацію тупиком. p> Ми зможемо прискорити процес пошуку розкладу, якщо ми навчимося визначати тупиковий шлях чи ні не проходячи його, інакше кажучи ми повинні навчиться робити
4. Прогноз тупика
На початку шляху по графу кожен елемент а має непорожню область визначення У а інакше процес пошуку розкладу можна було б і не починати. Побудова чергової пари розкладу (перехід в наступний вузол графа) означає зменшення безлічі В на одну вакансію і зменшення областей визначення деяких елементів множини А . Припустимо на деякому кроці у а 1 область визначення складається з 10 елементів в,
