8.5. Работа системы ALICE

Нам осталось рассмотреть следующее: внутреннее представление задач, обработку алгебраических ограничений, процедуры выбора.

8.5.1. Представление задач

Обычно программа разрабатывается для решения одного типа задач и используется одно представление. В данном случае необходимо уметь представлять произвольные задачи с конечными множествами и произвольными ограничениями. В идеальном случае, как в примере 3, все формулировки надо выражать в компактной форме, предусматривающей предварительную компиляцию, хотя для выражений типа

не существует другого представления, кроме приведенного классического алгебраического. Для системы ALICE наиболее подходящим является представление в форме “изображений” (графов и гиперграфов) во всех случаях, когда это допустимо, т. е. при наличии простых ограничений, связывающих не более двух переменных и при сохранении всех остальных в алгебраической форме.

Графическое представление

На рис. 8.6 а приведено общее представление организации информации. Для этого используется в основном двухчастичный граф: все точки слева, принадлежащие множеству являются начальными объектами, значения которых должны быть

Рис. 8.6а. (см. скан) Схема двухчастичного графа внутреннего представления задачи.

найдены. Точки справа, принадлежащие множеству I, являются возможными изображениями этих объектов.

Если в формулировке задачи нет других указаний, возможно существование всех дуг, исходящих из каждой точки и приходящих в каждую точку дугами и точками связана определенная информация — значения коэффициентов и других величин. В процессе решения задачи некоторые, значения могут оказаться запрещенными. Постоянно доступной является важная информация: возможные предельные значения переменных, число преемников для всех и из число предшественников для всех из I.

Когда искомые функции принадлежат особому типу — инъекции или сюръекции, опции “вынужденная степень” минимального или максимального числа точек изображения, — то. такая информация выражается локально: два вектора, связанные с точками множества указывают на минимальное (соответственно максимальное) число разрешенных предшественников. Например, для биекции они оба принимают значение 1.

Что касается гиперграфа, то он строится на вершинах множества если он существует, то выражает разъединение, или, что то же самое, ограничения, которые требуют, чтобы одно семейство точек представляло собой совершенно различные изображения (задачи перестановок, окрашивания, планирования). Эти семейства (или гиперграни: они связаны с произвольным числом вершин) запоминаются. В завершение интерпретации формулировки с помощью специальной процедуры отыскивается наиболее экономичное множество разъединений, для того чтобы охватить множество максимальными семействами. Такого рода “собирание крошек” служит, в частности, для того, чтобы затем быстрее выполнять выводы при наличии разъединяющих ограничений.

Формальное представление

Другие ограничения обрабатывают с помощью алгоритма унификации. Выражения могут быть, в частности, нормализованы с помощью правил перезаписи, приведенных в табл. 8.3. Начальные связи всегда выражаются с помощью символов Ф, или а второй член всегда равен 0.

С помощью табл. 8.3 можно осуществить некоторые типы унификаций второго порядка (над операторами). Например, символ в действительности означает или модуль; означает или означает или означает или (перезапись самого себя); означает произвольную функцию.

Предусмотрены фильтры для уменьшения числа попыток унификации. С каждым выражением связан характеристический вектор, учитывающий головной оператор, наличие числовой константы в первом члене, частоту появления каждой переменной. В зависимости от этого вектора выбираются соответствующие правила. Наличие кода указывает, что при унификации вызывается процедура численных вычислений.

Передача информации между двумя представлениями

• Все ограничения, содержащие единственную переменную, исключаются из пакета алгебраических ограничений и запоминаются в графе. Таким образом, соотношения означают соответственно назначение, исключение дуги, перемещение указателя в графе.

• В графе представляются также линейные соотношения между переменными типа неравенства типа разъединения типа

Таким образом, чем дальше продвигается решение задачи, тем большее число ограничений упрощается и большим

(кликните для просмотра скана)

Продолжение табл. 8.3 (см. скан)

становится их число, непосредственно представленное в графе. В конце решения вся информация содержится только в графе.

В процессе каждой модификации графа специальные процедуры выполняют выводы, связанные с контекстом:

• при назначении для всех объектов, находящихся в разъединении с а, запрещено изображение Если достигнута максимальная степень то все предшественники запрещены;

• при запрещении дуги производится проверка оставшихся возможных изображений. Если осталось только одно из них, выполняется соответствующее назначение. То же происходит, если одна из вершин множества I достигает минимальной степени;

• при выражении равенств типа одна вершина исключается, вычисляются и запоминаются грани разъединения и пересечения изображений.

В определенных случаях в процессе рекурсивного обращения к этим процедурам может быть обнаружена невозможность дальнейшего выполнения обработки, связанная с противоречиями, пустым множеством преемников, неудовлетворительной экстремальной степенью. Это сообщается монитору, который берет управление на себя, возвращается в решении задачи назад, восстанавливая состояние графа и ограничений, которое было перед последним выбором. Отметим, что теперь в графе содержится информация, на основе которой производится локальный анализ ограничений.

8.5.2. Обработка алгебраических ограничений

Общая процедура анализа ограничений

Эта процедура применяется ко всем ограничениям вида

в которых все члены со знаком сгруппированы в а остальные — в

Когда или содержит не более одного члена, обработка ограничений происходит специальным образом, описание которого приведено ниже.

Рис. 8.66. Алгоритм общего анализа.

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

По структуре эти ограничения оказываются более простыми, а содержащуюся в них информацию можно непосредственно использовать. Основная информация связана с интервалами изменений двух вершин Для выполнения ограничения необходимо, чтобы оба интервала имели относительное расположение в соответствии с основным соотношением

Установлено стандартом, что всегда использует положительные переменные. Тогда процедура анализа легко записывается с помощью обозначений этих интервалов, как и их пересечений. Обозначим эти интервалы через для и

для а также

Тогда алгоритм общего анализа принимает вид, приведенный на рис. 8.66.

Специальные случаи

1) В первом случае член или является нулевым, при этом очевидно, что соотношение является истиной или ложью. Если одна из этих сумм содержит только один член, то процедура упрощается и порождает столько ограничений, сколько членов содержится в другой сумме. Если содержит один член, то ALICE записывает для каждого из новое ограничение:

Пример. Из ограничения

при следует

и ничего нового для

2) Случай диофантовых уравнений вида обрабатывается отдельно с помощью классической процедуры конгруэнции. В данном случае особенно полезны значения, которые отмечены в графе как запрещенные. Во всех ограничениях на равенство отыскиваются общие целые коэффициенты и здесь тоже приходим к уравнениям конгруэнции.

Пример. Ограничение

приводит к что сразу отражается в графе исключением дуг, которые не удовлетворяют этим соотношениям.

3) Равенства позволяют исключить переменные. Тем не менее это исключение предпринимается только в линейном случае и когда каждая переменная появляется не менее двух раз в совокупности ограничений (в противном случае подобные подстановки не приводят к получению дополнительной информации).

Пример. Из системы

приходим к

и, следовательно,

4) Неявные ограничения, в которых неизвестно точное имя объекта. Например,

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

где запись обозначает множество объектов которые удовлетворяют свойству Если на данный момент существует такой объект для которого известно, что

то не удовлетворяет свойству

Пример. В предыдущем случае в процессе каждого назначения неравенство (1) проверяется для значения Стоимость объектов, для которых является изображением, подсчитывается следующим образом:

Для каждого удовлетворяющего условию свойство не может быть выполнено. Соответствующая дуга исключается из графа.

Порядок обработки ограничений

Множество ограничений в системе ALICE является динамическим с двойным заголовком. На первом месте, как мы уже видели, постоянно находятся ограничения, связанные с добавлением или отсечением, переходами из одного представления в другое. Этим система отличается от классических Программ в области операционных исследований или численного программирования. Во вторую очередь в данный момент времени система обрабатывает ограничение, которое она считает наиболее интересным, в соответствии с процедурой, описанной ниже.

Прежде всего отметим, что приоритет отдается графу. Создается записная книжка задания, и до тех пор, пока она не исчерпана, единственной выполняющейся работой являются процедуры вывода на графе. Когда управление передается алгебраической обработке, исследуются ограничения» получившие наибольшее количество информации со времени последнего анализа. В частности, приоритетными являются такие, у которых по крайней мере одна из неизвестных получила значение.

Рис. 8.7. Функция Грунди.

Если таковые не имеются, вступает в игру число исключенных значений с помощью графа.

Для определения порядка работы с этими ограничениями ALICE распределяет их по трудности. Чем с большим трудом поддается удовлетворению какое-либо ограничение, том более стеснительным оно является и тем большую информацию из него можно получить.

Трудность любого алгебраического ограничения С вида можно представить в виде эмпирической формулы

где — постоянный член и — сумма коэффициентов положительных членов, поделенных на степени членов. Чем больше и меньше тем легче найти набор значений для неизвестных, удовлетворяющий ограничению

Система использует также тот факт, что каждая переменная из несет информацию о переменной из а имен-. но верхняя граница значений переменной из ограничивает верхнюю границу значений переменной из и наоборот.

На рис. 8.7 приведена схема, дающая практическое представление о функции Грунди. Последняя отражает логический порядок, в котором информация об этих граничных значениях может изменяться допустимым образом.

Сначала рассматриваютсянижние границы, затем верхние. Сначала изучаются ограничения в значениях переменных, от которых не ожидается получить никакой дополнительной

информации. Затем новые вычисленные границы переносятся на те переменные, которые зависят только от уже известных.

Покажем это для случая линейных ограничений. Предположим, что в системе в числе прочих рассматриваются три следующих ограничения:

На рисунке стрелками указаны зависимости между нижними и верхними границами для различных значений неизвестных, которые соответствуют дугам, соединяющим вершины принадлежащие члену в том же ограничении

Рис. 8.8. Общая схема управления системы ALICE.

Допустим, известно, что нижняя граница несет информацию о нижних границах Одна из вершин — -ничего не получает от вершин она не имеет предшественников. В этом случае ALICE обрабатывает сначала наиболее простое ограничение, в котором в части присутствует т. е. ограничение

Предположим, что реальная нижняя граница равна 5. Тогда из ограничения следует, что Таким образом, следующим обрабатывается ограничение так как его члены больше не содержат неизученных предшественников. Из него следует

Предположим также, что из графа следует Тогда Таким образом, все ограничения учтены в правильном порядке и с получением максимальной информации. Из последнего оставшегося ограничения следует, что и окончательно получаем С помощью графа и подобного анализа можно получить верхние границы и извлечь новую информацию. Система ALICE в фазе вывода

остается максимально долгое время, переходя попеременно от графа к алгебраическим процедурам, максимально откладывая выбор. Однако, когда уже невозможно получить никакой новой информации, необходимо сделать какое-либо предположение, вводящее дополнительные небольшие ограничения в задачу и позволяющее продвинуться в ее решении. Система ALICE непременно должна сделать выбор (рис. 8.8).

8.5.3. Процедура выбора

В системе предусмотрены семь различных типов выбора. Приведем их в приоритетном для системы порядке.

1. Выбрать одну из альтернативных ветвей в ограничении типа ИЛИ.

2. Зафиксировать нижнюю или верхнюю границу значения переменной.

3. Установить предел стоимости назначения.

4. Ввести локальную нумерацию для уравнений двух или трех переменных.

5. Ввести глобальную нумерацию, когда размер задачи превышает фиксированный порог.

6. Назначить предшественника для точки из представляемого множества.

7. Выбрать изображение точки исходного множества.

Выбор типа выбора

Тип I. Выбрать одну из альтернативных ветвей в ограничении типа ИЛИ. ALICE выбирает его всякий раз, когда одна из ветвей ограничения типа ИЛИ содержит не более двух переменных.

Тип 2. Зафиксировать нижнюю или верхнюю границу значения переменной. В выборе этого типа используется переменная, которая участвует в максимальном числе ограничений и имеет наибольшее множество изображений. Затем это множество делится на два. Выбор имеет смысл только тогда, когда множество изображения является числовым множеством.

Тип 3. Установить предел стоимости назначения. Этот выбор является оптимистическим. Он осуществляется на втором этапе, когда, уже найдено очевидное решение. Друг за другом исключаются максимальные стоимости до тех пор, пока для каждой точки множества D множество дуг не будет уменьшено наполовину.

Типы 4 и 5. Ввести локальную нумерацию для уравнений двух или трех переменных. Ввести глобальную нумерацию, когда размер задачи превышает фиксированный порог. Эти

типы зависят от производительности ЭВМ. Бесполезно производить сложную формальную обработку, если задача стала небольшой по размеру. Чем меньше ограничений и чем меньше дуг из множества к множеству тем более выражено стремление ALICE останавливаться на этих типах выбора. ALICE всегда знает, что она умеет делать, и это принимается в расчет при оценке предельного размера. Ограничения равенства связаны с наибольшим числом формальных средств анализа, и наоборот, ограничения неравенства, а тем более ограничения типа ИЛИ, не принадлежащие к типу 1, требуют меньшего числа средств. Чем большее число ограничений принадлежит к двум последним типам, тем быстрее достигается предельный размер, инициирующий нумерацию.

Типы 6 и 7. Назначить предшественника для точки из представляемого множества. Выбрать изображение точки исходного множества. В данном случае речь идет об определении пары (объект из изображение из Эти процедуры применимы только к последнему состоянию, когда пространство поиска уже достаточно уменьшено. Типу 6 отдается предпочтение во всех случаях, когда множество должно быть получено целиком, существует хотя бы одна точка множества 1, у которой меньше предшественников, чем минимальное число преемников у точек множества или ALICE отдает предпочтение точке с наибольшими ограничениями. В обоих случаях ALICE использует набор критериев для выбора пары (исходная точка, точка изображения), которая даст наибольшее количество информации при последующем решении задачи.

На различных стадиях решения задачи каждый критерий применяется только в том случае, когда для этого имеется несколько причин. Обозначим через цену наилучшего кандидата по этому критерию. ALICE считает данный критерий выделенным тогда и только тогда, когда менее четверти кандидатов имеют цену, превышающую Таким образом, эта процедура исключает критерии с плоской зависимостью (все. цены имеют близкие значения) или слабые критерии (слишком много высоких цен). Подмножество кандидатов, отобранных с помощью одного критерия, затем фильтруется с помощью второго критерия и так до тех пор, пока не останется один кандидат (рис. 8.9).

Список критериев, используемых системой ALICE, приведен в табл. 8.4. Они работают и в графическом, и в алгебраическом представлениях. Затем будут приведены продукционные правила, определяющие стратегию, т. е. порядок, в котором эти критерии рассматриваются в системе.

Трудность ограничения была определена в рязд. 5.2.3. Глобальная трудность ограничений на переменную из множества представляет собой сумму элементарных трудностей.

Рис. 8.9. Значения трех критериев для 4 переменных. Выбор системы — переменная 3.

Целью всех критериев является выделение наиболее трудных точек. Таким образом, критерий (6) принимает во внимание точки с наибольшей минимально возможной стоимостью.

Таблица 8.4 (см. скан)

Критерий (7) оказывает влияние на проблемы оптимизации.

Отрыв точки — разность между наиболее низкой стоимостью и стоимостью, которая следует непосредственно за ней. Чем выше отрыв, тем более критической является точка.

Критерий (8) относится к алгебраическим ограничениям. Значимость переменной х определяется суммой изменений трудностей при изменении х от минимального до максимального значения. Сумма берется по множеству тех ограничений, в которых присутствует переменная х. Значимость х возрастает, когда глобальная трудность ограничений по переменной х уменьшается.

Критерий (9) относится к предшественникам и, и и также возможен для каждой точки из тогда как реальными предшественниками из критерия (10) являются точки и из для которых точки являются изображением.

Упорядочивание критериев и стратегия ALICE

Порядок, в котором располагаются критерии, выбирается самой системой. Он зависит, с одной стороны, от типа решаемой задачи (уже по формулировке ALICE знает, что определенные критерии не подходят для данного случая), а с другой — от стадии, на которой находится решение задачи.

Два метаэвристических правила, имеющие весьма общий характер, используются для выбора стратегии;

1) сделать наиболее информативный набор;

2) сделать выбор наименьшей стоимости.

Вытекающий из них порядок критериев определяется следующими продукционными правилами:

(см. скан)

(см. скан)

(см. скан)

Таким образом, по мере пёрехода от одного этапа к Другому программа сначала является «подозрительной», затем, как только найдено решение, “оптимистичной” и снова “подозрительной” при увеличении числа неудачных выборов, когда число ограничений возрастает. Подчеркнем, что хотя сами критерии и их упорядочивание являются всего лишь эвристическими правилами, но ALICE находит безупречно оптимальные решения. Другими словами, у нее не возникает противоречия между эвристикой и строгостью решения. Перейдем к рассмотрению средств, используемых в системе ALICE для доказательства оптимальности решения, полученного с помощью этих эвристических правил.

Доказательства оптимальности

Как только получено решение, полная стоимость которого равна добавляется ограничение ко всем задачам минимизации, для которых является функцией стоимости. Если функция имеет полиномиальный вид, это ограничение добавляется к исходным алгебраическим ограничениям. Доказательство оптимальности производится в том случае, когда встречается неразрешимая задача.

Рассмотрим два часто встречающихся частных случая, обработка которых выполняется по-разному. Один из них относится к функции стоимости вида

который встречается каждый раз, когда определены дуги (в частности, в задачах о коммивояжере, о вращений, о распределении), а для другого функция стоимости имеет вид

и он относится к задачам, в которых играет роль только наиболее высокая стоимость с учетом весового коэффициента а (задачи упорядочивания, окрашивания, разрезания).

Случай 1. На этапе обычным образом добивается уменьшения стоимости. Каждая точка и из приводит к минимальной стоимости, равной

Эта величина разделяется между всеми стоимостями дуг, исходящих из и таким образом, чтобы минимальная стоимость для каждой точки была нулевой. Если в последующем соответствующая дуга исключается, то ALICE осуществляет новое уменьшение стоимостей. Полученная таким образом полная сумма принимается за текущую нижнюю границу решения. Оптимальность доказывается исключением дуг со стоимостью, превышающей до тех пор, пока одна из точек не будет иметь преемника.

Случай 2. Для получения решения, лучшего в строгом смысле, чем известное решение для величины для всех и из изображения должны удовлетворять следующему соотношению:

Это неравенство настолько же уменьшает множество возможных изображений в каждой точке. Более того, нижняя граница оптимального значения вычисляется, исходя из всех ограничений вида

как в случае I.

Если для точек изображения устанавливаются максимальные степени то ALICE уменьшает также нижнюю границу где представляет собой ближайшее целое такое, что сумма

превышает число точек в каждая из которых должна иметь изображение.

Вычисления границ имеют важное значение лишь в том случае, если они позволяют на достаточно раннем этапе прекратить дальнейший поиск и доказательства оптимальности. Отметим, что они всегда основываются на необходимых условиях, которым должно удовлетворять каждое решение, т. е. они выполняются с помощью погружения пространства поиска в более обширное пространство с меньшим числом ограничений (рис. 8.10).

Рис. 8.10. Ограничения пространства поиска.

Таким образом, по построению каждое решение из является по крайней мере таким же хорошим, как и лучшее решение из Е.

Вычисление нижней границы является двойственной задачей по отношению к процессу выбора и ограничивает снизу реальное значение