> а у
а 2 область визначення складається з одного елемента
в. Якщо на наступному кроці область визначення а 2 зменшиться на 1 то весь процес зайде в глухий кут. Тобто можна сформулювати очевидне твердження: Найбільшу загрозу завести процес у глухий кут представляють ті елементи а у яких область визначення найменша. А звідси виникає хороша і абсолютно очевидна ідея.
Для того, щоб мінімізувати ризик виникнення тупика необхідно на кожному кроці побудови розкладу вибирати такий елемент а у якого область визначення найменша.
Ця ідея говорить про те, як вибирати елемент а для чергового дії по складання розкладу, але ще залишається проблема як вибирати в в пару елементу а. Якщо область визначення У а складається з одного елемента, то такої проблеми немає, але швидше за все вона міститиме кілька вакансій. Питання, яку з них вибрати. Проведемо невелике міркування.
Припустимо, що в області У а міститься два елементи в 1 і в 2 при цьому А в1 ( область визначення в 1 ) містить два елементи а і А в2 містить п'ять елементів а. Це означає, що якщо ми візьмемо для чергової пари розкладу елемент в 1 то ми зменшимо на 1 область визначення у двох елементів а, якщо ж ми візьмемо в 2 то ми зменшимо область визначення у 5 елементів а. Думаю, критерій вибору в вже зрозумілий і залишилося записати спільний алгоритм розробки розкладу.
Розрахувати всі області визначення А в
Розрахувати всі області визначення У а
Поки А не порожньо робити
Початок
Визначити черговий а ( елемент множини А з найменшою областю визначення)
В області визначення а визначити черговий в ( елемент безлічі В з найменшою областю визначення)
Скласти чергову пару розкладу (черговий а, черговий в )
Викреслити "черговий а " з областей визначення всіх в які входять в область визначення "чергового а "
Викреслити "черговий в " з областей визначення всіх а які входять в область визначення "чергового в "
Кінець
Останні два пункти алгоритму необхідні для обліку змін областей визначень, а вони змінюються кожного разу коли з А і з В вибирається черговий елемент.
Висновок
Начебто інтуїтивно ясно, що якщо побудований алгоритм буде працювати, то працювати він буде краще, ніж повний перебір, але його стислість (у відношенні до складності завдання) наводить на думку, що працювати він якраз і не буде. p> Це тільки початок, всього лише основна ідея. Нижче я опишу проблеми які необхідно вирішити, що б алгоритм став дійсно робочим.
Перша проблема. Алгоритм побудований з метою раннього прогнозування тупикових ситуацій, але цілком очевидно, що він не може повністю виключити тупиків, а отже потрібно або удосконалення моделі, щоб зробити прогноз точніше, або потрібна спеціальна процедура виходу з глухого кута. p> Загальну ідею, виходячи з глухого кута дає побудований вище орієнтований граф. Якщо ми зайшли в глухий кут, то необхідно зробити кілька кроків у зворотному напрямку, проти напрямку стрілок.
Друга проблема. Алгоритм начебто прагне до рішенням, але з його тексту з опису моделі абсолютно не ясно, що він гарантує знаходження рішення. p> Тому після того, як до нього буде додана процедура виходу з глухого кута, необхідно провести доказ, що він дійсно знайде існуюче рішення. p> Для доказу можна буде наприклад показати, що алгоритм у гіршому випадку гарантує повний перебір варіантів або користуючись нашою моделлю можна сказати, що алгоритм гарантує повний обхід графа побудованого на безлічі D.
Третя проблема. Всі міркування наведені вище виходять з того, щоб області визначення елементів а можуть тільки зменшуватися на 1. Але це не так. Наведемо приклад. p> Нехай до розкладу пред'явлено наступну вимогу "У десятого А класу в розкладі не повинно бути дірок ". І нехай на деякій кроці для цього класу був поставлений урок "Понеділок 2 урок каб.11". Це означає, що всі вакансії "Понеділок 4 урок" будуть заборонені оскільки це створить дірку. p> Однак, якщо виявиться заповненої вакансія "Понеділок 3 урок "те вакансія" Понеділок 4 урок "знову стане доступною. З цього випливає, що область визначення може змінюватися стрибкоподібно, як в бік зменшення так і у бік збільшення.
Четверта проблема. Ясно, що вимоги до розкладу володіють різним ступенем значущості. Деякі з ни...
