Содержание к диссертации
Введение
ГЛАВА 1. Разбиения в задачах дефрагментации 10
1.1. Формулировка задачи 10
1.2. Вычислительная сложность задачи ДМ-01 13
1.3. Подходы к решению задачи дефрагментации 17
1.4. Дефрагментация матриц класса Р 22
ГЛАВА 2. Разбиение множеств 24
2.1. Перечисление" ближайших" разбиений 24
2.2. Разбиение множества на т подмножеств с ограничениями 30
2.3. Множества со структурированными элементами 33
2.4. Поиски "нетрадиционных" алгоритмов разбиения 36
ГЛАВА 3. Дефрагментация строк таблицы расписания .39
3.1. Дефрагментация матриц класса р 39
3.2. Дефрагментация матрицы класса рп\\11Х 47
3.3. Дефрагментация матрицы класса рп'А 55
3.4. Дефрагментация матриц класса М2' 62
ГЛАВА 4. Применение результатов 65
4.1. Обзор задач, сводимых к задаче дефрагментации 65
4.2. Минимизация "окон" преподавателей в учебном расписании 68
4.3. Оптимальное размещение TSR - программ в UMB 70
ГЛАВА 5. Аспекты программирования базовых алгоритмов 75
5.1. Потоковые методы. Максимальный и допустимый потоки 75
5.2. Взаимодействие приложения с внешними программами 89
Литература 95
- Вычислительная сложность задачи ДМ-01
- Разбиение множества на т подмножеств с ограничениями
- Дефрагментация матрицы класса рп\\11Х
- Минимизация "окон" преподавателей в учебном расписании
Введение к работе
ВВЕДЕНИЕ
Актуальность проблемы. В предлагаемой работе рассматривается комплекс взаимосвязанных задач комбинаторного и теоретико-графового характера, важнейшими из которых являются: а) задачи дефрагментации матриц различных классов - непрерывного расположения ненулевых элементов в каждой строке матрицы с сохранением множеств элементов в каждой линии матрицы; б) задачи разбиения множеств со структурированным элементами; в) задача о дефрагментации 0-1 матрицы без1 ограничения допустимых операций только перестановками столбцов.
Трудность для исследования ряда приведенных в работе задач, возникающих в различных областях науки, носит объективный характер, является результатом труднорешаемости соответствующих математических моделей. В качестве модели, объединяющей в себе характерные черты этих задач, рассматривается задача дефрагментации матриц.
Первым толчком к рассмотрению задач дефрагментации матрицы явились работы Фалкерсона и Гросса, которые ввели понятие связности единиц для строк матрицы с элементами 0-1. Впервые был поставлен вопрос о существовании перестановки столбцов, позволяющей расположить все единицы в каждой строке рядом. Первый полиномиальный алгоритм решения этой задачи был предложен в [16]; классическим решением считается довольно громоздкий алгоритм Буса и Люкера [8] с линейной временной сложностью. Более простые алгоритмы были предложены в работах [26], [19].
Симметричная задача может быть рассмотрена о перестановке строк.
Заметим, что задача дефрагментации матрицы является частным случаем задачи нахождения подматрицы со свойством связности единиц [46], NP-полнота которой доказана в [7]. На некоторые замечания (см. [20]) к приведенному в [7] доказательству было указано автору данной работы проф. Са-лий В.Н.
Принятого в литературных источниках
Введение
Задачи дефрагментации матриц находят применение в теории графов [13], вычислительной биологии [2], в файловой структуре ЭВМ [25], в проблеме минимизации простоев при маршрутизации [19], [62] и везде, где преследуется цель неразрывного расположения объектов со свойством связности в некотором подклассе наборов.
Специалистами НИИ ПМА КБНЦ РАН был указан нам ряд областей, где находят применение частные случаи сформулированной проблемы (соответствующие задачи приведены в [38] под названиями "Создание генома", "Информационная сеть", "Кристаллы", "Дублирование опытов").
Целый класс матриц, интуитивно относимых в разряд дефрагменти-руемых, оставался за рамками исследований из-за ограничения множества допустимых для дефрагментации операций лишь перестановками столбцов. В работах Магомедова A.M. [61, 63, 68] и Альрашайда А. [37, 38] вопрос вытеснения нулевых элементов на крайние позиции строк матрицы - начальные и/или концевые - рассматривался без ограничений на используемые в преобразованиях операции; единственным требованием являлось сохранение множества элементов в каждой линии.
Предложенные нами модификации потоковых методов и результаты, полученные для задач разбиения множеств, позволили рассмотреть задачу дефрагментации для классов матриц, содержащих до семи столбцов, количество строк при этом не ограничено. Для матриц с большим количеством столбцов возникает переборная задача, которая делает использование этих методов нерациональным; перенести часть результатов на матрицы с неограниченным числом столбцов удалось лишь для некоторых частных случаев.
Отметим множественные пересечения с классическими труднорешае-мыми задачами - как основной для работы задачи дефрагментации матрицы, так и ряда задач сопровождения. Перечислим некоторые из этих трудноре-шаемых задач [46].
Введение "Разбиение" - исследуется возможность разбиения конечного множества элементов с заданными целочисленными стоимостями на два подмножества с равными суммами стоимостей. "Дополнение до матрицы со свойством связности" - исследуется преобразование (0-1)- матрицы к матрице, обладающей свойством связности единиц, путем замены не более К ненулевых элементов. "Многопроцессорное расписание" - для заданных множества заданий, числа процессоров и длительности каждого задания требуется выяснить существование такого расписания обработки, которое удовлетворяет заданному директивному сроку. "Целочисленный поток в сети с гомологичными дугами" - в задаче нахождения максимального потока приходится учитывать дополнительное условие равенства потоковых значений для каждой пары "гомологичных" дуг.
В связи с этим становится актуальной проблема поиска существенных частных случаев, допускающих решение за полиномиальное время.
Цель работы. Основной целью работы является исследование необходимых и достаточных условий разрешимости задачи дефрагментации для матрицы из семи столбцов, содержащей в каждом столбце, кроме нулей, некоторую перестановку первых чисел натурального ряда, и разработка полиномиального алгоритма преобразования исходной матрицы к виду с непрерывным расположением ненулевых элементов в строках матрицы. Некоторые из ряда незапланированных вначале задач, - о разбиении матрицы на две дефрагментируемые матрицы меньших размеров, разбиение на ближайшие подмножества, сведение задачи разбиения множества структурированных элементов к задаче разбиения множества из неделимых элементов, - также стали целью изучения. Полученные при этом результаты (относящиеся к задачам разбиения множеств со структурированными элементами) существенно повлияли на достижение основной цели.
Структура работы и краткая характеристика результатов по главам и параграфам. Работа состоит из введения и пяти глав, первые две из которых
Введение содержат по четыре, две следующие - по три, последняя - два параграфа, разбитых на пункты. Как параграфы, так и пункты имеют структурированную нумерацию, соответствующий стиль поддерживается также и для рисунков и таблиц.
Введенные в 1.1 обозначения и определения имеют для работы сквозной характер. Основная проблема - исследование условий дефрагментации строк матрицы М, содержащей в каждом столбце, кроме нулей, некоторую перестановку чисел /, 2, ...«, с сохранением множества элементов в каждой линии - сформулирована в виде задачи распознавания. В 1.2 рассмотрена матрица Sign (М), разрешимость которой является необходимым условием дефрагментации матрицы М. В процессе доказательства полиномиальной сводимости известной NP-потюй задачи "Разбиение" к задаче дефрагментации матрицы Sign (М) получена простая схема структуры дефрагментирован-ной матрицы, что для дальнейших исследований оказалось существенно более благотворным, чем сознательно поставленная цель установить NP-полноту задачи дефрагментации 0-1 матрицы. Рассмотрение в 1.3 дефрагментации простого класса матриц послужило введением в методику использования потоковых методов в задачах дефрагментации, незагроможденность многочисленными деталями дальнейших рассмотрений способствовала также выявлению роли трансверсалей в проверке условий дефрагментации. Примененный в 1.3 теоретико-графовый инструментарий исследования получил некоторое развитие в 1.4, где основу процесса преобразования матрицы составляет набор совершенных паросочетаний в двудольном графе, инициированный допустимым потоком в транспортной сети.
Из нескольких сопутствующих вопросам дефрагментации проблем для подробного изучения во второй главе выбраны проблемы разбиения. Некоторые рассмотренные здесь проблемы являются традиционными, часть из них сформулирована впервые.
В 2.1 сформулирована и решена задача разбиения множества на два подмножества, ближайшие по суммам весов, рассмотрена задача перечисле-
Введение ния разбиений. После изложения в 2.2 схемы решения задачи разбиения множества на п подмножеств мы решили опустить непринципиальный и громоздкий текст ее дополнения до множественного разбиения на ближайшие подмножества. Такого же подхода мы придерживались, например, и воздерживаясь от неизбежно пространного изложения процесса дефрагментации для случая, когда строка матрицы порядка кхт содержит 1 или т-1 ненулевых элементов, т.к. такое изложение не привносит принципиальных дополнений в алгоритм, приведенный в 3.2 для случая т=7. Базовым для последующего в Главе 3 исследования задач дефрагментации является 2.3, где приведен ряд утверждений комбинаторного и теоретико-графового характера о разрешимости задач разбиения множеств со структурированными элементами.
Намеченные в 2.4 варианты "нетрадиционных" подходов к разработке алгоритмов разбиения множеств со структурированными элементами нам показались перспективными, однако развить их до эффективного аппарата не удалось.
В третьей главе рассматриваются условия дефрагментации матриц класса pfk,7'n]. Необходимые и достаточные условия дефрагментации сформулированы в 3.1-3.3 в терминах потоков в транспортных сетях.
В 4-ой главе указаны некоторые применения результатов предыдущих глав - сформулирован ряд задач из разных предметных областей науки и техники, которые могут быть интерпретированы как задачи дефрагментации, несколько подробнее обсуждается одна из них - задача дефрагментации учебного расписания, показывается применение алгоритма разбиения для решения задачи из области системного программирования.
В пятой главе рассмотрены некоторые аспекты разработки программного комплекса на основе полученных в предыдущих главах результатов.
Методы исследований. В диссертационной работе использованы понятия и методы теории графов, комбинаторики и теории NP-полноты. В числе наиболее интенсивно используемых укажем полиномиальное сведение к из-
Введение вестной NP-полной задаче, потоковые методы, поиск трансверсалей, аппарат паросочетаний в двудольных графах, метод динамического программирования.
Научная новизна. Впервые исследованы условия дефрагментации для класса р[к'7'"^ показана связь рассматриваемой задачи с известными трудно-решаемыми задачами, выделены подзадачи, допускающие разрешимость за полиномиальное время, получен ряд результатов для разбиения множеств различных типов.
Теоретическая и практическая ценность. Диссертация носит теоретический характер. Полученные в работе результаты и разработанные методы будут полезны в задачах из разных областей, где суть проблемы сводится к преобразованию таблицы с целью беспробельного в строках расположения элементов, удовлетворяющих заданным условиям.
Достоверность полученных результатов. Все представленные в диссертационной работе теоремы строго доказаны. Предложенные алгоритмы сопровождаются доказательством правильности, а также компьютерными вычислительными экспериментами.
Компьютерная поддержка работы в основном осуществлялась с использованием среды Дельфи. Для перекрестной проверки полученных результатов на заключительном этапе выполнения работы автор воспользовался пакетом DiscreteMath известной системы компьютерной математики Mathematica 4 [96] (например, функцией NetworkFlow - для вычисления максимального потока в сети, Contract, GridGraph - для построения графов) и пакетом networks системы Maple 6 [97] (функциями flow, draw - аналогичными вышеупомянутым, и др.).
Научные положения, выносимые на защиту: - теоремы о необходимых и достаточных условиях дефрагментации \к,7,п] \к,7,п] \к,т,п] \к,т,п] матриц классов п\ 0 К1т,п\^ , п\, рп ' ,,рп ' ', ^ г{1,2,5,6,1} ^{3,4,7} У{\,т-1,т} г {2,т-2,т} - полиномиальные алгоритмы дефрагментации.
Введение результаты о разбиении множеств со структурированными элементами; теорема об NP-полноте задачи дефрагментации; - оптимизация расположения резидентных программ в блоках памяти. Публикации и апробация работы. По теме диссертации опубликованы 9 работ. Основные результаты диссертации докладывались на годичных итоговых конференциях Дагестанского госуниверситета (1996г. - 2002г.), на 2-й научной сессии ДО международной академии информатизации (1996 г.), на семинаре посвященном проблемам математической кибернетики ДНЦ РАН (2002 г.), на семинаре лаборатории вычислительного эксперимента Ростовского госуниверситета под рук. д.ф.-м.н. Крукиера Л.А. (2003 г.), на научном семинаре Дагестанского регионального центра новых информационных технологий под рук. д.т.н. проф. Ахмедова С.А. (2000 г.), на совместном семинаре кафедр факультета КН и ИТ Саратовского госуниверситета (2002).
Объем работы. Содержание работы изложено на 101 страницах, список использованной литературы содержит 97 наименований.
Вычислительная сложность задачи ДМ-01
Полиномиальное сведение NP-полной задачи Разбиение к задаче ДМ-01. Для положительного ответа на вопрос задачи ДМ необходимо иметь положительный ответ на вопрос следующей задачи. Задача "Дефрагментация матрицы из 0-1" (ДМ-01). Условие. Даны натуральные k, т, п (ksai) и матрица М кхт, каждый столбец которого содержит п единиц и к-п нулей. Вопрос: Существует ли матрица М кхт, где сохранено соотношение нулей и единиц в каждой строке и каждом столбце, причем единицы в каждой строке располагаются рядом? Покажем, что задача ДМ-01 является NP-полной (причем она остается NP- полной и при п=2). Принадлежность задачи ДМ-01 классу NP следует из того, что недетерминированному алгоритму необходимо угадать лишь набор значений элементов строк М и проверить за полиномиальное время, что а) соотношение нулей и единиц сохранено в каждой линии таким же, что и в исходной матрице М; б) для каждого нулевого элемента матрицы выполнено условие - либо все элементы в строке левее рассматриваемого являются нулями, либо нуля ми являются все элементы в строке правее рассматриваемого элемента. Укажем полиномиальное сведение ([46], с.52) известной Л Р-полной задачи «Разбиение» к задаче "ДМ-01", сформулированной для случая п=2. Пусть ah а2, ..., а - элементы, участвующие в формулировке задачи "Разбие-ние", S{ai), Sfaz), ..., S(ak) - их целочисленные стоимости", т = (S(a])+ S(a2)+ ...+S(ak))/2. Рассмотрим матрицу М кхт из нулей и единиц, где количество единиц в / - ой строке составляет S(cij), а каждый столбец содержит в точности 2 единицы (все остальные элементы таблицы равны нулю). Докажем, что матрица М дефрагментируема тогда и только тогда, когда ответ на вопрос задачи "Разбиение" положителен. В самом деле, пусть сначала ответ на вопрос задачи "Разбиение" положителен, и А - такой набор і ii ,..., і, из номеров строк, что сумма стоимостей S(a() для ІЄА равна т.
Тогда матрица М в задаче "ДМ-01 " может быть получена с помощью следующей процедуры. В строке ц все единицы расположим в начале строки, пусть их расположение завершилось в позиции к\. В строке /г единицы расположим рядом, начиная с позиции X,i+1, пусть их расположение завершилось в позиции Х2 Продолжая этот процесс, расположим единицы в строке /,, начиная с позиции X,t.j+1. Поскольку количество единиц в і - ой строке составляет S(cij), расположение единиц в строке it завершится в позиции т. Таким образом, мы получили одно лестничное расположение единиц. Затем выполним аналогичную работу для набора, остающегося после удаления А из множества строк матрицы М. В результате получим искомую дефрагментированную матрицу М. Докажем теперь, что имеет место и обратное: если матрица М дефрагментируема, то ответ на вопрос задачи «Разбиение» положителен. Пусть М -дефрагментированный вариант матрицы М. Докажем прежде всего, что если в некоторой строке матрицы М в позиции і располагается 7, а в і+1 -ой позиции - значение 0 (другими словами, единицы расположены в позициях 1..Г), то найдется строка матрицы М, у которой в позиции і+1 располагается значение 1, а в предыдущей, і -ой позиции, - значение 0 (другими словами, размещение единиц начинается с позиции і+1). Допустим противное: пусть такой строки не существует. Заметим, что при этом, очевидно, имеются строки, содержащие в і+1 - ой позиции значение 1, т.к. исходная матрица М содержит по две единицы в каждом столбце, в том числе и в столбце с номером і+1 (а матрица М , по определению, сохраняет количество единиц в каждом столбце). Наше допущение об отсутствии строки, содержащей в /+7-ой позиции 1, а в предыдущей позиции - 0, равно Глава 1. Разбиения в задачах дефрагментации. 1.2. Вычислительная сложность задачи ДМ-01 сильно тому, что каждая строка матрицы М, имеющая в позиции i+I значение 1, имеет значение 1 и в предыдущей позиции, т.е. в позиции і. Но отсюда следует, что в столбце і матрицы М количество единиц больше, чем в столб-це і+1, что противоречит определению матрицы М .
Таким образом, утверждение доказано. 1.2.2. Структура дефрагментированной матрицы. На самом деле мы не только доказали NP-полноту задачу "ДМ-01", но также установили следующее важное для дальнейшего свойство дефрагментированных матриц. Лемма 1.1.1 (О структуре дефрагментированной матрицы). Дефрагментированная матрица, содержащая в каждом столбце в точности п ненулевых элементов, всегда представлена набором из п "лестниц". Из сказанного вытекает, что задача ДМ-01 для матрицы М kxm , является, по существу, задачей разбиения множества элементов а] а2 , ..., а с заданными целочисленными стоимостями элементов S(aj) Sfa),, ..., S(ajJ на п подмножеств с равными т суммами стоимостей элементов, где п - количество единиц в каждом столбце матрицы М. Поскольку даже в частном случае, когда количество единиц в каждом столбце матрицы равно 2, задача ДМ-01 является Л -полной, практическая эффективность алгоритмов решения задачи, на первый взгляд, представляет Глава 1. Разбиения в задачах дефрагментации. 1.2. Вычислительная сложность задачи ДМ-01 ся сомнительной. В последующем, однако, мы покажем, что существует вполне эффективный алгоритм решения задачи для случая, когда п - количество единиц в каждом столбце - сравнительно невелико. Какие особенности данной JVP-полной задачи позволяют надеяться на существование такого алгоритма? Прежде всего, следует иметь в виду, что задача "Разбиение" [46] может быть решена полиномиальным алгоритмом при некотором вполне естественном в прикладных задачах ограничении на величину участвующих в формулировке индивидуальной задачи чисел (подробнее см. 2.1). В [7] и [1] рассмотрены следующие две NP-полные задачи о дефрагментации 0-1 матриц, основным отличием которых от рассмотренной выше является ограничение на допустимые операции. Формулировки этих задач мы приводим в редакции [46], с.291. Задача "Подматрица со свойством связности". Условие. Заданы (кхт)-матрица А с элементами 0 и 1 и положительное целое число L. Вопрос. Существует ли в матрице А подматрица В порядка kxL, обладающая свойством "связности единиц" (т.е. подматрица В, столбцы которой можно так переставить, что в каждой строке все единицы идут подряд)? Задача может быть решена за полиномиальное время, если L=m, другими словами, если спрашивается: "Верно ли что сама матрица А перестановкой столбцов может быть приведена к виду, где в каждой строке все единицы идут подряд?" В следующей задаче также исследуется возможность достижения связности единиц в каждой строке, ограничиваясь лишь операциями перестановки столбцов. Задача "Разбиение на подматрицы со свойством связности". Условие. Задана (0-1)- матрица А порядка кхт. Вопрос. Можно ли так разбить строки матрицы на две подгруппы, чтобы получившиеся в результате матрицы порядков к}хт и к2хт (к і + к2 -к) обладали свойством связности единиц? В 3.4 нами рассмотрена задача, текстуально близкая к задаче о разбиении на подматрицы со свойством связности.
Разбиение множества на т подмножеств с ограничениями
Если в дефрагментированнои матрице М рассмотренного в 3.1 класса (с (ненулевыми элементами в позициях 1 -2) строку из М с "выровненной вправо" (с расположением ненулевых элементов в позициях 3-4-5-6-7) строкой из М (5), аналогично: выровненную вправо строку из М(2) со строкой из М (5) , выровненной влево, получим "упакованный" вариант М матрицы изображенного на рис. 3.2.1 вида, где горизонтальной штриховкой указаны не-нулевые элементы строки множества М , ненулевые элементы строки из М (5) выделены диагональной штриховкой; а элементы строки из М (7) оставлены светлыми. Рассмотрение в 3.1 по существу использовало тот факт, что каждая строка упакованной дефрагментированнои матрицы представлена в средних трех столбцах тремя (ненулевыми) элементами. мы рассмотрим условия дефрагментации для случая, когда множество строк матрицы распадается на множества , и при этом выполняется первое из равенств (3.1.1): М = \А 5\ Это условие, строго говоря, перестает быть необходимым для дефрагментации матрицы класса ту и сохранено лишь для облегчения рассмотрения. Замена данного условия на условие не является принципиальной. Соответст вующая схема упакованного варианта дефрагментированной матрицы, как выяснится из дальнейшего, будет соответствовать приведенному на рис.3.2.3 виду, где ненулевые элементы каждой строки выровнены к левой или правой границам. Затруднение поиска условий дефрагментации без предварительных ограничений вида: конфигурацией упаковки, когда, ненулевые элементы, например, строки из М или Ы необязательно выровнены к границе. Найти необходимые и достаточные условия дефрагментации в общем виде нам не удалось.
Пусть сначала рассматриваемая матрица М принадлежит классу р и выполнено условие Л/7/) = Л/ . Приведенное ниже построение транспортной сети Т(М) мало отличается от аналогичного построения в предыдущем параграфе. Вершины. Множество вершин составляют Т] - источник, Т2 - сток; п вершинX], х2,..., х„, соотнесенные элементам множества {1, 2, ... п); Х= I А/ и Мч вершин уі, у2,...,ух, последовательно соотнесенных строкам множества Л/ u Л/7/) функцией г/ От источника Т} к каждой из вершин xs проведена дуга с потоковыми ограничениями [5, 5]; от вершины xs (s=l,2,...,п) к вершинеyt дуга проведена тогда и только тогда, когда соответствующая строка rj(yt) содержит число s, при этом дуге (xs, yt) приписываются потоковые ограничения [0,1]; от каждой вершины у, к стоку Т2 проведена дуга с ограничениями [5, 5]. Легко видеть, что в случае существования дефрагментированного варианта матрицы М ненулевые элементы строк множества М( могут начинаться только с первой или второй позиций. Теорема 3.2 Для дефрагментации матрицы Мкласса Лк f для кото г {1,6,7} рой имеет место равенство \M J) = \М \ необходимо и достаточно существование допустимого потока в транспортной сети Т(М). Необходимость. Предположим, что исходная матрица допускает деф-рагментацию и М - ее дефрагментированный вариант. Требуется доказать существование допустимого потока в транспортной сети Т(М). Позиции 2-3-4-5-6 каждой строки из М иМ заняты ненулевыми элементами. Пусть Му-произвольная строка матрицы М. Если Mj принадлежит множеству М (б)иМ (7 , то через ш2, тЗ, т4, т5 и тб обозначим соответственно (ненулевые) элементы строки в позициях 2, 3, 4, 5 и 6 соответственно. Пусть дан-ной строке соответствует вершина yt транспортной сети Т(М), т.е. ц (М7) =yt. Тогда положим поток по дугам (xm2, yj, (хт3, yt), (хт4, у J, (хт5, у,), (хтб, yt) равным единице. Продолжив поток с соблюдением свойства непрерывности, получим искомый допустимый поток в Т(М). Достаточность. Предположим, что в транспортной сети Т(М) существует допустимый поток/
Построим дефрагментацию матрицы М. Рассмотрим однородный степени 5 двудольный граф G(X\J У, Е), образованный дугами {(xs, yt):f(xs, у =1). Представим граф в виде прямой суммы пяти совершенных паросочетаний G, (ХиУ; EJ, 1=2,3,4,5,6. Выберем, как и прежде, пустую таблицу размеров кхгп , обозначим ее М и положим все ее элементы равными нулю. Последовательно рассмотрим Еь 1=2,3,4,5,6, и для \k,l,n\ Глава 3. Дефрагментация строк таблицы расписания. 3.2. Дефрагментация матриц класса П г {1,2,5,6,7} каждого ребра (xs, yt) из Et поместим элемент xs в ячейку матрицы М на пересечении строки ц (yt) и столбца /, тут же удаляя xs из соответствующей строки исходной матрицы М. по два ненулевых элемента; совокупность этих ненулевых элементов образует множество {1,1, 2,2, ..., п,п). Расположение каждого из этих элементов (в "своих" строках) в позициях 1 или 7 таким образом, чтобы получить в первом и шестом столбцах бесповторный набор {1,2,..., п}, не вызывает затруднений.
Остается обозначить полученный дефрагментированный вариант матрицы М через М. Теорема доказана. Рассмотрение условий дефраг ментации матрицы класса ту " без ограничения также не представляет труда. Для формулировки соответствующего результата построим транспортную сеть Г (М), отличающуюся от построенной выше добавлением в множество {yt} вершин, соответствующих строкам множества м , а также введением трех вершин zj, z6 и z7, соответствующих множествам От источника Г/ к каждой из вершин xs проведена дуга (Ті, xs) с потоковыми ограничениями [5, 5],s=l,2,..., п; от вершины xs (s=l,2,...,n) к вершине yt (t=l,2,...,k) дуга проведена тогда и только тогда, когда соответствующая вершине yt строка матрицы М содержит число s, при этом дуге (xs, yt) приписываются потоковые ограничения [0,1]; от каждой вершины yt: г/ (уJ є А к вершине zq проведена дуга (yt ,zq) с ограничениями: [5,5] -при qG{6,7} и [1,0] -при q=l; от вершин zq к стоку Т2. проведены дуги с ограничениями: [5/лЛ, 5/лЛ ]при q G{6, 7} и \5(n-/l q)/), 5(n-/b4q)I) ] - при q=l. Справедлива \k 7 ri\ Теорема 3.2.2. Для дефрагментации матрицы Миз класса гг необходи г {1,6,7} мо и достаточно выполнение условий13: а) Л/;; \}Л\
Дефрагментация матрицы класса рп\11Х
Рассмотрение в 3.1 по существу использовало тот факт, что каждая строка упакованной дефрагментированнои матрицы представлена в средних трех столбцах тремя (ненулевыми) элементами. мы рассмотрим условия дефрагментации для случая, когда множество строк матрицы распадается на множества , и при этом выполняется первое из равенств (3.1.1): М = \А 5\ Это условие, строго говоря, перестает быть необходимым для дефрагментации матрицы класса ту и сохранено лишь для облегчения рассмотрения. Замена данного условия на условие не является принципиальной. Соответст вующая схема упакованного варианта дефрагментированной матрицы, как выяснится из дальнейшего, будет соответствовать приведенному на рис.3.2.3 виду, где ненулевые элементы каждой строки выровнены к левой или правой границам. Затруднение поиска условий дефрагментации без предварительных ограничений вида: конфигурацией упаковки, когда, ненулевые элементы, например, строки из М или Ы необязательно выровнены к границе. Найти необходимые и достаточные условия дефрагментации в общем виде нам не удалось. Пусть сначала рассматриваемая матрица М принадлежит классу р и выполнено условие Л/7/) = Л/ . Приведенное ниже построение транспортной сети Т(М) мало отличается от аналогичного построения в предыдущем параграфе. Вершины. Множество вершин составляют Т] - источник, Т2 - сток; п вершинX], х2,..., х„, соотнесенные элементам множества {1, 2, ... п); Х= I А/ и Мч вершин уі, у2,...,ух, последовательно соотнесенных строкам множества Л/ u Л/7/) функцией г/ От источника Т} к каждой из вершин xs проведена дуга с потоковыми ограничениями [5, 5]; от вершины xs (s=l,2,...,п) к вершинеyt дуга проведена тогда и только тогда, когда соответствующая строка rj(yt) содержит число s, при этом дуге (xs, yt) приписываются потоковые ограничения [0,1]; от каждой вершины у, к стоку Т2 проведена дуга с ограничениями [5, 5]. Легко видеть, что в случае существования дефрагментированного варианта матрицы М ненулевые элементы строк множества М( могут начинаться только с первой или второй позиций. Теорема 3.2 Для дефрагментации матрицы Мкласса Лк f для кото г {1,6,7} рой имеет место равенство \M J) = \М \ необходимо и достаточно существование допустимого потока в транспортной сети Т(М). Необходимость. Предположим, что исходная матрица допускает деф-рагментацию и М - ее дефрагментированный вариант.
Требуется доказать существование допустимого потока в транспортной сети Т(М). Позиции 2-3-4-5-6 каждой строки из М иМ заняты ненулевыми элементами. Пусть Му-произвольная строка матрицы М. Если Mj принадлежит множеству М (б)иМ (7 , то через ш2, тЗ, т4, т5 и тб обозначим соответственно (ненулевые) элементы строки в позициях 2, 3, 4, 5 и 6 соответственно. Пусть дан-ной строке соответствует вершина yt транспортной сети Т(М), т.е. ц (М7) =yt. Тогда положим поток по дугам (xm2, yj, (хт3, yt), (хт4, у J, (хт5, у,), (хтб, yt) равным единице. Продолжив поток с соблюдением свойства непрерывности, получим искомый допустимый поток в Т(М). Достаточность. Предположим, что в транспортной сети Т(М) существует допустимый поток/ Построим дефрагментацию матрицы М. Рассмотрим однородный степени 5 двудольный граф G(X\J У, Е), образованный дугами {(xs, yt):f(xs, у =1). Представим граф в виде прямой суммы пяти совершенных паросочетаний G, (ХиУ; EJ, 1=2,3,4,5,6. Выберем, как и прежде, пустую таблицу размеров кхгп , обозначим ее М и положим все ее элементы равными нулю. Последовательно рассмотрим Еь 1=2,3,4,5,6, и для \k,l,n\ Глава 3. Дефрагментация строк таблицы расписания. 3.2. Дефрагментация матриц класса П г {1,2,5,6,7} каждого ребра (xs, yt) из Et поместим элемент xs в ячейку матрицы М на пересечении строки ц (yt) и столбца /, тут же удаляя xs из соответствующей строки исходной матрицы М. по два ненулевых элемента; совокупность этих ненулевых элементов образует множество {1,1, 2,2, ..., п,п). Расположение каждого из этих элементов (в "своих" строках) в позициях 1 или 7 таким образом, чтобы получить в первом и шестом столбцах бесповторный набор {1,2,..., п}, не вызывает затруднений. Остается обозначить полученный дефрагментированный вариант матрицы М через М. Теорема доказана. Рассмотрение условий дефраг ментации матрицы класса ту " без ограничения также не представляет труда. Для формулировки соответствующего результата построим транспортную сеть Г (М), отличающуюся от построенной выше добавлением в множество {yt} вершин, соответствующих строкам множества м , а также введением трех вершин zj, z6 и z7, соответствующих множествам
От источника Г/ к каждой из вершин xs проведена дуга (Ті, xs) с потоковыми ограничениями [5, 5],s=l,2,..., п; от вершины xs (s=l,2,...,n) к вершине yt (t=l,2,...,k) дуга проведена тогда и только тогда, когда соответствующая вершине yt строка матрицы М содержит число s, при этом дуге (xs, yt) приписываются потоковые ограничения [0,1]; от каждой вершины yt: г/ (уJ є А к вершине zq проведена дуга (yt ,zq) с ограничениями: [5,5] -при qG{6,7} и [1,0] -при q=l; от вершин zq к стоку Т2. проведены дуги с ограничениями: [5/лЛ, 5/лЛ ]при q G{6, 7} и \5(n-/l q)/), 5(n-/b4q)I) ] - при q=l. Справедлива \k 7 ri\ Теорема 3.2.2. Для дефрагментации матрицы Миз класса гг необходи г {1,6,7} мо и достаточно выполнение условий13: а) Л/;; \}Л\ б) существует допустимый поток в транспортной сети Т (М). Для практических целей нам представляется более удобным использование теоремы 3.2.3, доказательство которой получается очевидной модификацией доказательства теоремы 3.2.1. Проиллюстрируем соответствующую вычислительную схему на примере. Для матрицы М, изображенной на рис.3.2.5, транспортная сеть Т (М) представлена на рис.3.2.6. 13 На самом деле условие а) является избыточным, оно является следствием б). [k,7,n] Глава 3. Дефрагментация строк таблицы расписания. 3.2. Дефрагментация матриц класса Г) - {1,2,5,6,7} Рис.3.2.6. Транспортная сеть Т (М). ,2,5,6,7} В сети T (М) существует допустимый поток. Построим двудольный граф G(Xu У, Е), образованный вершинами xs,yt и дугами (xs, yt), вдоль которых поток равен 1 (рис.3.2.7). Полное паросочетание X в У показано утолщением дуг. 1 лава 3. Дефрагментация строк таблицы расписания. 5.1. Дефрагментация матриц класса п Рис.З.2.7. Двудольный граф G(XKJ У, Е), образованный дугами (х5, у,), вдоль которых поток равен 1. Выделено полное паросочетание X в У. Последовательно удаляя выделенное полное паросочетание и вычисляя полное паросочетание в оставшемся двудольном графе, представим граф в виде прямой суммы пяти совершенных паросочетаний G, (Х У, Ej), i=2,3,4,5,6. Выберем пустую таблицу размеров 21x7 , обозначим ее М и положим все ее элементы равными нулю. Последовательно рассмотрим Еь 1=2,3,4,5,6, и для каждого ребра (xs, у J из Et поместим элемент xs в ячейку матрицы М на пересечении строки г] (yt) и столбца /, тут же удаляя xs из соответствующей строки исходной матрицы М. В результате в каждой строке множества -A/7" сохранится не более одного ненулевого элемента, в строке из М 6) - в точности один ненулевой элемент, а в каждой строке из М (7) - по два ненулевых элемента; совокупность этих ненулевых элементов образует множество {1,1, 2,2, ..., п,п). Результат расположения каждого из этих элементов (в "своих" строках) в позициях 1 или 7
Минимизация "окон" преподавателей в учебном расписании
В качестве модели, объединяющей в себе характерные черты сформулированных выше и близких к ним задач, рассматривается задача дефрагментации учебного расписания, другими словами - Оптимизации учебного расписания (ОУР) по одному из критериев - уменьшению окон преподавателей. В следующей формулировке под сохраняющим преобразованием матрицы понимается преобразование, сохраняющее множество элементов в каждой линии. Задача оптимизации учебного расписания. Дано: Матрица учебного расписания М кхт, каждый столбец которого содержит некоторую перестановку чисел 1, 2, ..., п, к п, и к-п нулей, где п-число различных учебных групп, к- количество преподавателей, т- количество уроков в каждой учебной группе. Равенство Му=Ь при L 0 рассматривается как наличие у-ого урока /-го преподавателя в учебной группе с номером L. Равенство Му=0 является признаком отсутствия у преподавателя у -го урока, и если при этом найдутся s, t такие, что l s j t m, Mis?0, Mit 0, то My называется окном для преподавателя /. Требуется: Найти необходимые и достаточные условия существования сохраняющего преобразования матрицы М к виду, где ненулевые элементы в каждой строке располагаются рядом. В случае существования такого преобразования указать эффективный алгоритм его реализации. Таким, образом, термин учебное расписание понимается в смысле, отличном от вкладываемого в него в следующей «классической» формулировке [46] известной NP-полной задачи: УСЛОВИЕ. Заданы множество Н "рабочих часов", множество С "преподавателей", множество Т "учебных дисциплин", для каждого сєС дано подмножество A(c)czH, называемое "допустимыми часами для преподавателя с", для каждой дисциплины teT- подмножество B(t)czH, называемое "допустимыми часами для дисциплины t, и для каждой пары (c,t)eCxT - число R(c,t)eZ?0, называемое "требуемой нагрузкой». ВОПРОС.
Существует ли учебное расписание, обслуживающее все дисциплины? Другими словами, существует ли функция/ СхТхН — {0, 1} (где f(c,t,h)=l означает, что преподаватель с занимается дисциплиной t в момент h), удовлетворяющая следующим условиям: (\)f(c,t,h)= 1 только тогда, когда кєА(с) п B(t), (2) для каждого he Ни сєС существует не более одного te.T, такого, что f(c,t,h)=l, (3) для каждого пеНи tGТсуществует не более одного сеС, такого, что/(сД,/г)=/, (4) для каждой пары (с, t)eCx. Т существует ровно R(c, t) значений h, для которых (c,t,h)= 11 Известно, что последняя задача остается NP-полной, даже если Н\ =3, B(t)=H для te Т и все Я(с,і)є{0,1}. Общая задача разрешима за полиномиальное время, если \А(с) I 2 для всех сеС или если A(c)=B(t)=H для всех сеСи teT. Исследование задачи приведено в [38]. Несмотря на все различия между сформулированными выше задачами, их объединяет некоторая «категоричность» условия: требуется с соблюдением определенных условий получить расположение некоторых элементов без пробелов, а не исследовать наименьшее возможное количество пробелов и Подход, предпринятый в следующем параграфе, отличается от названного. Несмотря на появление современных операционных систем с развитой моделью памяти, вопрос предоставления приложениям MS/DOS возможно большего места в традиционной для них области памяти до 640К остается актуальным. Одним из подходов к решению является расположение драйверов устройств и TSR-программ в блоках верхней памяти. Первая часть данного параграфа является введением в проблему оптимизации такого размещения, во второй предлагается схема решения проблемы (см. [71]). Использованная в параграфе терминология соответствует [48]. 4.3.1. Проблема размещения TSR-программ в верхней памяти. Создание и использование UMB. После установки himem.sys в файле конфигурации драйвер emm386.exe идентифицирует незанятые области адресного пространства в пределах от 640К до 1М и использует возможности страничной адресации для отображения расширенной памяти на эти области. Эти области преобразуются в блоки верхней памяти (сокращенно UMB), доступные после директивы DOS=UMB в файле конфигурации14 для размещения в них TSR-программ (называемых также и резидентными) и драйверов устройств путем выполнения включенных в файл автозапуска команд loadhigh и device-high соответственно. Для удовлетворения требованиям аппаратного обеспечения драйверу emm386.exe обычно приходится расщеплять создаваемое им ОЗУ в верхней памяти на несколько непрерывных UMB.
Если система не использует адап-терные ОЗУ и ПЗУ в сегментах COOOh и DOOOh, то создается единственный непрерывный UMB длиной 128К; если же, например, в сегменте C800h со держится ПЗУ контроллера жесткого диска объемом 32К, то Emm386.exe создаст два UMB: один от COOOh до C7FFh, другой - от DOOOh до DFFFh с общей длиной 96К [21]. К созданию нескольких UMB может привести также установка драйвера emm386.exe со специальным ключом, блокирующим доступ к тем или иным областям (содержащим, например, ПЗУ, которое драйвер не может обнаружить) с целью предотвращения отказа системы. Приближенные алгоритмы. Пусть созданы два или более UMB. При размещении в них резидентных программ/драйверов команды loadhigh/devicehigh следуют примитивному правилу: «загрузить очередную программу/драйвер в наибольший свободный участок». В результате полученное размещение далеко от оптимального, и качество использования UMB не удовлетворяет пользователей ПЭВМ. Мы укажем здесь на алгоритмы, пригодные для решения проблемы. Заметим прежде всего, что в зависимости от выбранного критерия оптимальности и
