Эта идея говорит о том, как выбирать элемент а для очередного действия по составления расписания, но ещё остаётся проблема как выбирать в в пару элементу а. Если область определения Ва состоит из одного элемента, то такой проблемы нет, но скорее всего она будет содержатьнесколько вакансий. Вопрос, какую из них выбрать. Проведём небольшое рассуждение.
Предположим, что в области Ва содержится два элемента в1и в2 при этом Ав1 (область определения в1) содержит два элемента а и Ав2 содержит пять элементов а. Это означает, что если мы возьмём для очередной пары расписания элемент в1 то мы уменьшим на 1 область определения у двух элементов а, если же мы возьмём в2то мы уменьшим область определения у 5 элементов а. Думаю, критерий выбора в уже понятен и осталось записать общий алгоритм разработки расписания.
Рассчитать все области определения Ав
Рассчитать все области определения Ва
Пока А не пусто делать
Начало
Определить очередной а (элемент множества А с наименьшей областью определения)
В области определения а определить очередной в (элемент множества В с наименьшей областью определения)
Составить очередную пару расписания (очередной а, очередной в)
Вычеркнуть "очередной а" из областей определения всех в которые входят в область определения "очередного а"
Вычеркнуть "очередной в" из областей определения всех а которые входят в область определения "очередного в"
Конец
Последние два пункта алгоритма необходимы для учета изменений областей определений, а они изменяются каждый раз когда из А и из В выбирается очередной элемент.
Вроде бы интуитивно ясно, что если построенный алгоритм будет работать, то работать он будет лучше, чем полный перебор, но его краткость (в отношении к сложности задачи) наводит на мысль, что работать он как раз и не будет.
Это только начало, всего лишь основная идея. Ниже я опишу проблемы которые необходимо решить, что бы алгоритм стал действительно рабочим.
Первая проблема. Алгоритм построен с целью раннего прогнозирования тупиковых ситуаций, но совершенно очевидно, что он не может полностью исключить тупиков, а следовательно нужно либо усовершенствование модели, чтобы сделать прогноз точнее, либо нужна специальная процедура выхода из тупика.
Общую идею, выходя из тупика даёт построенный выше ориентированный граф. Если мы зашли в тупик, то необходимо сделать несколько шагов в обратном направлении, против направления стрелок.
Вторая проблема. Алгоритм вроде бы стремится к решению, но из его текста из описания модели совершенно не ясно, что он гарантирует нахождение решения.
Поэтому после того, как к нему будет добавлена процедура выхода из тупика, необходимо провести доказательство, что он действительно найдёт существующее решение.
Для доказательства можно будет например показать, что алгоритм в худшем случае гарантирует полный перебор вариантов или пользуясь нашей моделью можно сказать, что алгоритм гарантирует полный обход графа построенного на множестве D.
Третья проблема. Все рассуждения приведённые выше исходят из того, чтоб области определения элементов а могут только уменьшаться на 1. Но это не так. Приведём пример.
Пусть к расписанию предъявлено следующее требование "У десятого А класса в расписании не должно быть дыр". И пусть на некотором шаге для этого класса был поставлен урок "Понедельник 2 урок каб.11". Это означает, что все вакансии "Понедельник 4 урок" будут запрещены так как это создаст дырку.
Однако, если окажется заполненной вакансия "понедельник 3 урок" то вакансия "понедельник 4 урок" опять станет доступной. Из этого следует, что область определения может изменяться скачкообразно, как в сторону уменьшения так и в сторону увеличения.
Четвертая проблема. Ясно, что требования к расписанию обладают разной степенью значимости. Некоторые из них обязательно должны быть выполнены, а некоторыми можно и пожертвовать.
Но эти свойства требований к расписанию в модели описанной выше вообще никак не учтены.
И последнее. Мы пользовались этой моделью для решения некоторых частных задач на составление расписаний и могу сказать, что метод работает качественно.
1. Вострикова З.П. и др. "Программирование на языке "БЕЙСИК" для персональных ЭВМ". Машиностроение, 1993г.
2. Гохман А.В. и др. "Сборник задач по математической логике и алгебры множеств", издательство Саратовского Университета, 1969г.
3. Гусев В.В. Основы импульсной техники.М. Советское радио, 1975
4. Касаткин В.Н. "Информация, алгоритмы, ЭВМ", М. Просвещение, 1991г.
5. Машовцев В.А. Вступительные экзамены по информатике // Информатика. 1997, №13
6. Орлов В.А. О вступительных экзаменах по информатике // Информатика, 1997, №15
7. Яснева Г.Г. Логические основы ЭВМ // Информатика и образование, 1998, №2
8. Лыскова В.Ю., Ракитина Е.А. Логика в информатике, М. Информатика и образование 1999
9. Шауцкова Л.З. “Решение логических задач средствами алгебры логики”, газета Информатика 1999, №5.