Міністерство освіти Республіки Білорусь
Установа освіти
"Гомельський державний університет ім.Ф. Скорини "
Математичний факультет
Кафедра МПУ
Реферат
Метод пріоритетів для задач розробки розкладів
Виконавець:
Студентка групи М-52
Ларченко А.Ю.
Науковий керівник:
Канд. фіз-мат. наук, доцент
Звенцова Т.Є.
Гомель 2004
Зміст
Введення
1. Про характері завдання
2. Чи можна її вирішити повним перебором
3. Безліч D
4. Прогноз тупика
Висновок
Література
Введення
Дана робота присвячена проблемі розробки математичної моделі складної задачі. Проблема неосяжна, існуючі методи на мій погляд настільки загальні, що в них мало сенсу. p> Тому я не буду займатися викладом загальних місць, а просто наведу приклад такої розробки, досить складний, щоб він був цікавий і досить зрозумілий.
Звичайно, описана нижче модель, ні в якому разі не претендує на повноту і точність, це всього лише (я сподіваюся вдалий) демонстраційний приклад.
Я спробую розібрати дуже популярну завдання, вирішити яку намагалися і нині намагаються дуже багато програмісти. Я маю на увазі завдання складання розкладів. p> Звичайно, це цілий клас задач, але ми далі будемо говорити тільки про одного представника цього класу - завданню складання розкладу навчальних занять. Однак цей представник дуже яскравий і нам його буде достатньо.
1. Про характер завдання
Грубо кажучи існує два крайніх типу завдань. Перші це хороші завдання для яких можна отримати гарне аналітичне рішення. Те є рішення може виражатися якимось компактним швидко рахувати твердженням, наприклад формулою. p> Елементарний приклад аналітичного рішення - це рішення квадратного рівняння. Складність одержуваних формул до уваги не беремо. Кубічне рівняння має більш складне рішення, але принципово воно нічим не відрізняється від рішення квадратного, це так само формула і не більше того.
Другий тип завдань - це погані завдання, для яких необхідний повний перебір. Ось приклад такої поганої завдання "Знайти найвищого китайця ". У цій задачі, як не крутись, а доведеться перебирати всіх китайців.
Перш ніж братися за завдання необхідно з'ясувати погана це завдання або хороша. Витратимо дві хвилини на аналіз. Рішення хорошою завдання закінчується формулою. Формула це зовнішній прояв внутрішньої закономірності притаманною даними завдання. p> А що таке закономірність? У найзагальнішому вигляді - закономірність це зв'язки між даними, якісь обмеження на них. У задачі про розклад вихідні дані можуть бути по суті якими завгодно і вони між собою неможливо пов'язані. p> Якщо ми наприклад знаємо, що у Івана Івановича є уроки математики в 10 класі, то це не дає нам жодної інформації про уроках російської в цьому ж класі. p> Тому ми навряд чи в праві чекати закономірності, і тому задача теорії розкладів це погана завдання.
2. Чи можна її вирішити повним перебором
Щоб відповісти на поставлене питання необхідно оцінити кількість виконуваних дій. Спробуємо зробити це. p> Для початку сформулюємо завдання більш точно.
Розклад це сітка уроків, по якій розподілені заняття. Осередки цієї сітки будемо називати надалі вакансіями, а заняття нехай залишать за собою свою назву.
Припустимо для спрощення, що кількість вакансій одно кількістю занять і запишемо якусь найпростішу структуру даних
понеділок
вівторок
середу
Перший урок
1
2
3
Другий урок
4
5
6
І нехай занять тільки шість. Порожні клітини це вакансії. Ми їх пронумерували, щоб побачити простий факт: хоча сітка вакансій і прямокутна вакансії можна вибудувати в простій ряд. Пронумеруємо також і заняття А1, А2, А3, А4, А5, А6. Тоді завдання пошуку необхідного варіанта розкладу полягає в отриманні всіх перестановок з 6 елементів. Відомо ж, що з N елементів можна отримати N! = 1 * 2 * 3 * 4 .... * N перестановок, тобто в нашому завданні 6! = 1 * 2 * 3 * 4 * 5 * 6 = 720. А для реального набору даних, наприклад в 50 занять число перестановок взагалі виходить астрономічним. Крім того, необхідно пам'ятати, що кількість вакансій у реа...
