Реферат: Метод приоритетов для задач разработки расписаний - текст реферата. Скачать бесплатно.
Банк рефератов, курсовых и дипломных работ. Много и бесплатно. # | Правила оформления работ | Добавить в избранное
 
 
   
Меню Меню Меню Меню Меню
   
Napishem.com Napishem.com Napishem.com

Реферат

Метод приоритетов для задач разработки расписаний

Банк рефератов / Программирование

Рубрики  Рубрики реферат банка

закрыть
Категория: Реферат
Язык реферата: Русский
Дата добавления:   
 
Скачать
Архив Zip, 41 kb, скачать бесплатно
Заказать
Узнать стоимость написания уникального реферата

Узнайте стоимость написания уникальной работы

13 Реферат Метод приоритетов для задач разработки расписаний Соде ржание Введение 1. О ха рактере задачи 2. Мож но ли её решить полным перебором 3. Мно жество D 4. Про гноз тупика Закл ючение Лите ратура Введ ение Данная работа посвящена проблеме р азработки математической модели сложной задачи . Проблема необъятна, существующие методы на мой взгляд нас только общи, что в них мало смысла . Поэтому я не буду заниматься изложением общих мест, а п росто приведу пример такой разработки, достаточно сложный, чтобы он был интересен и достаточно понятный . Конечно, описанная ниже модель, ни в коем случае не пре тендует на полноту и точность, это всего лишь ( я надеюсь удачный ) демонс трационный пример . Я попробую разобрать очень популярную задачу, решить которую пытались и ныне пытаются очень многие программисты . Я имею ввиду задачу составления расписаний . Конечно, это целый класс задач, но мы далее будем говор ить только об одном представителе этого класса - задаче составления расписания учебных занятий . Однако этот представитель очень ярок и нам его будет достаточно . 1 . О характере задачи Грубо говоря существует два крайних типа задач . Первые это хорошие задачи для которых мо жно получить красивое аналитическое решение . То есть решение может выражаться каким-то компактным быстр о считаемым утверждением, например формулой . Элементарный пример аналитического решения - это решение квадратного уравнения . Сложность получаемых формул во внимани е не берём . Кубическое уравнение им еет более сложное решение, но принципиально оно ничем не отличается от р ешения квадратного, это так же формула и не более того . Второй тип задач - это плохие задачи, для которых необходим полный перебор . Вот пример такой плохой задачи " Найти самого высокого китайца ". В этой задаче, как ни крутись, а придётся перебирать все х китайцев . Прежде чем браться за задачу необходимо выяснить пло хая это задача или хорошая . Потрати м две минуты на анализ . Решение хоро шей задачи заканчивается формулой . Формула это внешнее проявление внутренней закономерности присущей дан ным задачи . А что такое закономерность ? В самом общем виде - зак ономерность это связи между данными, какие-то ограничения на них . В задаче о расписании исходные данные мо гут быть в сущности какими угодно и они между собой никак не связаны . Если мы к примеру знаем, что у Ивана Ивановича есть уро ки математики в 10 классе, то это не даёт нам никакой информации о уроках ру сского в этом ж классе . Поэтому мы вряд ли в праве ожидать закономерности, и по этому задача теории расписаний это плохая задача . 2 . Можно ли её решить полным перебором Чтобы ответить на поставленный вопрос необходимо оце нить количество выполняемых действий . Попробуем сделать это . Для начала сформулируем задачу более точно . Расписание это сетка уроков, по которой распределены занятия . Ячейки этой сетки будем на зывать в дальнейшем вакансиями, а занятия пусть оставят за собой свое на звание . Предположим для упрощения, что количество вакансий р авно количеству занятий и запишем какую-нибудь простейшую структуру да нных Понедельник Вторник Среда Первый урок 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 з анятий число перестановок вообще получается астрономическим . Кроме того, необходимо помнить, что количес тво вакансий в реальных задачах больше количества занятий, а стало быть даже не очень объёмная задача теории расписания требует ресурсов супер компьютера . Небольшое, но важное дополнение . Почему нельзя взять первый попавшийся вариант ? А потому, что на расписание накладываетс я ряд условий выполнение которых невозможно при произвольном варианте ( например отсутствие дырок в расписании класса ). Этих условий обычно очень м ного, и они резко сокращают количество допустимых вариантов . Фактически их так мало, что вероятность нат кнуться на допустимый вариант в самом начале перебора практически равн а нулю . Что же делать ? Надеюсь, выше я достаточно ясно показал безнадежност ь нашего положения . Лобовая атака н а задачу ничего не даст . Поэтому еди нственный выход - это изменить отно шение к задаче . Например, мы можем от казаться от намерения получить гарантированно идеальное решение за ко роткое время . А давайте сформулируе м наши намерения несколько иначе . Теперь мы желаем просто максимально увеличить вероят ность обнаружения достаточно хорошего варианта за ограниченное время . Мы смягчили свои запросы , и теперь можем рассчитывать на успех . Но сначала опишем задачу в более строгих терминах . Обозначения : А - Множество з анятий а - Занятие В - множество в акансий в - Вакансия ( а, в ) - допустим ая пара расписания, то есть пара не противоречащая требованиям налагаем ым на расписание . Вполне возможно, что для элемента а существует несколько допустимых пар расписания . А если это возможно для элемента а, то следовательно возможно и для элемента в . Та ким образом можно ввести ещё два важных понятия : В а - множество все элементов в которые могут участвовать в допустимых парах расписания с эле ментом а . А в - множество все элементов а которые могут участвовать в допустимых парах расписания с эле ментом в . Тогда расписанием назовём такое множество допустимы х пар расписания в котором каждый элемента множества А присутствует ровно один раз . Таким образом, расписание это элемент множества всех множеств допустимых пар . А составле ние расписания тогда математически сводится к поиску нужного элемента среди уже упомянутого множества всех множеств допу стимых пар ( обозначим его как D ). 3 . Множество D На первый взгляд оно устроено беспорядочно . Однако это не так : возьмём какой-либо элемент этого множества d . Он представля ет собой множество допустимых пар . Совершенно очевидно, что для данного элемента существует ( и быть может не один ) элемент d ' отличающийся от d на одну пару и при этом d > d ' . скажем тогда, что элементы d и d ' связаны между собой отношением следования d d ' . Очевидно, что каждый элемент множества D связан отношением хотя бы с одн им элементом . Если теперь, мы распол ожим элементы множества D на плоскости и те элементы которые находят ся между собой в отношении следования соединим стрелками, то получим свя зный ориентированный граф . Это для тех кто знает, что такое связный ориентированный граф . Если кто не знает, то пусть не расстр аивается, для нашей задачи не важно как это называется, важно представит ь себе эту картинку . А выглядит она п римерно так . Тогда процесс поиска элемента d являющегося р асписанием есть ничто иное как путь вдоль стрелок ведущий к искомому эле менту . В общем это и есть модель . Мы свели поиск расписания к поиску пути на ориентированном гра фе . А ориентированный граф это стру ктура, о которой в математике известно довольно много и теперь мы можем о брушить на задачу всю мощь теории графов . Но давайте предположим, что большинство из нас оной теорией не владеют, и продолжим поиск решения . Но кое что из модели графа мы возьмём . Заметим, что каждый путь на графе обязатель но заканчивается узлом, из которого не выходит ни одна ветка . То есть из этих узлов продолжать поиск расп исания нельзя, а это означает, что имеет место одна из двух ситуаций : Расписание уже составлено . Расписание не составлено, но для некоторых элементов а нет ни одного элемента в . Будем называть дальше эту ситуацию тупиком . Мы сможем ускорить процесс поиска расписания, если мы научимся определять тупиковый путь или нет не проходя его, иначе говоря мы должны научится делать 4 . Прогноз тупика В начале пути по графу каждый элемент а имеет непустую область определения В а иначе процесс поиска расписания можно было бы и не начинать . Построение очередной пары расписания ( переход в следующий узел графа ) означает уменьшение множества В на одну вакансию и уменьшение областей определения некоторых элементов множества А . Предположим на некотором шаге у а 1 область определения состоит из 10 элементов в, а у а 2 область определе ния состоит из одного элемента в . Если на следующем шаге область определения а 2 уменьшится на 1 то вес ь процесс зайдёт в тупик . То есть мож но сформулировать очевидное утверждение : Наибольшую угрозу завести процесс в тупик представляют те эле менты а у которых область определ ения наименьшая . А отсюда возникает хорошая и совершенно очевидная идея . Для того, чтобы минимизировать риск возникновения т упика необходимо на каждом шаге построения расписания выбирать такой э лемент а у которого область определения наименьшая . Эта идея говорит о том, как выбирать элемент а для очередного действия по составления ра списания, но ещё остаётся проблема как выбирать в в пару элементу а . Если область определения В а состоит из одного эл емента, то такой проблемы нет, но скорее всего она будет содержать несколько вакансий . Вопрос, какую из них выбрать . Проведём небольшое рассуждение . Предположим, что в области В а содержится два элемента в 1 и в 2 при этом А в1 ( область определения в 1 ) содержит два элемента а и А в2 содержит пять элементов а . Это означает, что если мы возьмём для очередной пары расписания элемент в 1 то мы уменьшим на 1 область опреде ления у двух элементов а, если же мы возьмём в 2 то мы уменьшим область определения у 5 элементов а . Думаю, критерий вы бора в уже понятен и осталось запи сать общий алгоритм разработки расписания . Рассчитать все области определения А в Рассчитать все области определения В а Пока А не пусто делать Начало Определить очередной а ( элемент множества А с наименьшей областью определения ) В области определения а определить очередной в ( элемент множества В с наименьшей областью определения ) Составить очередную пару расписания ( очередной а, оче редной в ) Вычеркнуть " очередно й а " из областей опре деления всех в которые входят в об ласть определения " очередного а " Вычеркнуть " очередно й в " из областей опре деления всех а которые входят в об ласть определения " очередного в " Конец Последние два пункта алгоритма необходимы для учета изменений областей определений, а они изменяются каждый раз когда из А и из В выбирается очередной элемент . Закл ючение Вроде бы интуитивно ясно, что если построенный алгори тм будет работать, то работать он будет лучше, чем полный перебор, но его к раткость ( в отношении к сложности задачи ) наводит на мысль, что работать он ка к раз и не будет . Это только начало, всего лишь основная идея . Ниже я опишу проблемы которые необходимо ре шить, что бы алгоритм стал действительно рабочим . Первая проблема . Алгоритм построен с целью раннего прогнозирования тупиковых ситуаций, но совершенно очевидно, что он не может полностью исключить ту пиков, а следовательно нужно либо усовершенствование модели, чтобы сдел ать прогноз точнее, либо нужна специальная процедура выхода из тупика . Общую идею, выходя из тупика даёт построенный выше ори ентированный граф . Если мы зашли в т упик, то необходимо сделать несколько шагов в обратном направлении, прот ив направления стрелок . Вторая проблема . Алгоритм вроде бы стремится к решению, но из его текста из описа ния модели совершенно не ясно, что он гарантирует нахождение решения . Поэтому после того, как к нему будет добавлена процеду ра выхода из тупика, необходимо провести доказательство, что он действит ельно найдёт существующее решение . Для доказательства можно будет например показать, чт о алгоритм в худшем случае гарантирует полный перебор вариантов или пол ьзуясь нашей моделью можно сказать, что алгоритм гарантирует полный обх од графа построенного на множестве D . Третья проблема . Все рассуждения приведённые выше исходят из того, чтоб области определения элементов а могут то лько уменьшаться на 1 . Но это не так . Приведём пример . Пусть к расписанию предъявлено следующее требование " У десятого А класса в расписании не долж но быть дыр ". И пусть на некотором шаге для этого класса был поставлен урок " Понеде льник 2 урок каб .1 1 ". Это означает, что все вакансии " Понедельник 4 урок " будут запрещены так к ак это создаст дырку . Однако, если окажется заполненной вакансия " понедельник 3 урок " то вакансия " понедельник 4 урок " опять станет доступной . Из этого следует, что область определения м ожет изменяться скачкообразно, как в сторону уменьшения так и в сторону увеличения . Четвертая проблема . Ясно, что требования к расписанию обладают разной степенью зна чимости . Некоторые из них обязатель но должны быть выполнены, а некоторыми можно и пожертвовать . Но эти свойства требований к расписанию в модели опис анной выше вообще никак не учтены . И последнее . Мы по льзовались этой моделью для решения некоторых частных задач на составл ение расписаний и могу сказать, что метод работает качественно . Лите ратура 1. Вострикова З .П. и др . " Программирование н а языке " БЕЙСИК " для персональных ЭВМ ". Машиностроение, 1993г . 2. Гохман А .В. и др . " Сборник задач по математической логике и ал гебры множеств ", издательство Сарат овского Университета, 1969г . 3. Гусев В .В. Основы импульсной техники .М. Советское радио, 1975 4. Касаткин В .Н. " Информация, алгоритмы, ЭВМ ", М . Просвещение, 1991г . 5. Машовцев В .А. Вступительные экзамены по инфор матике // Информатика . 19 97, №13 6. Орлов В .А. О вступительных экзаменах по информатике // Информатика, 1997, №15 7. Яснева Г .Г. Логические основы ЭВМ // Информатика и образование, 1998, №2 8. Лыскова В .Ю., Ракитина Е .А. Лог ика в информатике, М . Информатик а и образование 1999 9. Шауцкова Л .З. “Решение логических задач средствами алгебры логик и”, газета Информатика 1999, №5 .
1Архитектура и строительство
2Астрономия, авиация, космонавтика
 
3Безопасность жизнедеятельности
4Биология
 
5Военная кафедра, гражданская оборона
 
6География, экономическая география
7Геология и геодезия
8Государственное регулирование и налоги
 
9Естествознание
 
10Журналистика
 
11Законодательство и право
12Адвокатура
13Административное право
14Арбитражное процессуальное право
15Банковское право
16Государство и право
17Гражданское право и процесс
18Жилищное право
19Законодательство зарубежных стран
20Земельное право
21Конституционное право
22Конституционное право зарубежных стран
23Международное право
24Муниципальное право
25Налоговое право
26Римское право
27Семейное право
28Таможенное право
29Трудовое право
30Уголовное право и процесс
31Финансовое право
32Хозяйственное право
33Экологическое право
34Юриспруденция
 
35Иностранные языки
36Информатика, информационные технологии
37Базы данных
38Компьютерные сети
39Программирование
40Искусство и культура
41Краеведение
42Культурология
43Музыка
44История
45Биографии
46Историческая личность
47Литература
 
48Маркетинг и реклама
49Математика
50Медицина и здоровье
51Менеджмент
52Антикризисное управление
53Делопроизводство и документооборот
54Логистика
 
55Педагогика
56Политология
57Правоохранительные органы
58Криминалистика и криминология
59Прочее
60Психология
61Юридическая психология
 
62Радиоэлектроника
63Религия
 
64Сельское хозяйство и землепользование
65Социология
66Страхование
 
67Технологии
68Материаловедение
69Машиностроение
70Металлургия
71Транспорт
72Туризм
 
73Физика
74Физкультура и спорт
75Философия
 
76Химия
 
77Экология, охрана природы
78Экономика и финансы
79Анализ хозяйственной деятельности
80Банковское дело и кредитование
81Биржевое дело
82Бухгалтерский учет и аудит
83История экономических учений
84Международные отношения
85Предпринимательство, бизнес, микроэкономика
86Финансы
87Ценные бумаги и фондовый рынок
88Экономика предприятия
89Экономико-математическое моделирование
90Экономическая теория

 Анекдоты - это почти как рефераты, только короткие и смешные Следующий
В театре идет репетиция сцены группового секса. Режиссер (устало):
- Маша, не дрыгайте ногами. Ирина, не визжите. Это же Чехов!
Anekdot.ru

Узнайте стоимость курсовой, диплома, реферата на заказ.

Обратите внимание, реферат по программированию "Метод приоритетов для задач разработки расписаний", также как и все другие рефераты, курсовые, дипломные и другие работы вы можете скачать бесплатно.

Смотрите также:


Банк рефератов - РефератБанк.ру
© РефератБанк, 2002 - 2016
Рейтинг@Mail.ru