8.8. Эффективность системы и общие замечания

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

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

8.8.1. Пример 1

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

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

(см. скан)

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

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

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

от каждой операции и может быть найден только с использованием точных результатов символьной обработки ограничений. Число предпринимаемых попыток зависит от числа независимых букв-операндов, которых в данном случае шесть: и Таким образом, число попыток, которые нужно будет сделать равно примерно 101/4! или 151200. В отличие от этого ALICE полностью решает задачу с использованием шести конечных узлов.

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

Буквы должны соответствовать (биекция) целым числам в интервале [0,9].

Первые выводы (в порядке, определяемом системой):

Из ограничения (1) следует, что Т является четным.

Из ограничения (5) следует, что

Из ограничения (2) следует, что (по модулю 2).

Из ограничения (3) следует, что (по модулю 2).

1 Кроме того, все переносы не превышают 1, так как сумма двух букв не может превышать 17.

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

Выбор следовательно, и

При этом изменился вид трех ограничений, а ограничение (5) становится тривиальным.

Следствия. Из ограничения следует, что является четным, следовательно, Изображение 0 уже

связано с Е. Тогда граф дает, что и ограничение исключается.

Из ограничения следует, что так как и должны быть различны и отсюда и подставим вместо в ограничение и с помощью арифметического модуля (описанного в разд. 4.3.2) выведем два новых ограничения:

так как минимальный набор из трех различных значений в пространстве изображений дает сумму, равную 6. Из неравенства в свою очередь следует

Затем снова анализируются ограничения (1), (2) и так как уточнены значения входящих в них переменных. Из условия и ограничения теперь следует, что и Из ограничения (1) ничего нового не получается, а из ограничения (2) следует так как и так как

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

Выбор

Перепишем систему ограничений:

Выводы. Кроме этого, граф «знает», что

Анализ новых ограничений сразу уточняет эти границы:

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

Из равенства следует, что так как значения 0, 2, 4, 8 запрещены. Таким образом, Но при этом все значения 0, 1, 2, 3, 4 и 5 уже использованы и ограничение не позволяет получить решения. Если то тогда так как значение 4 уже использовано. Отсюда следует, что и

И снова больше не остается свободных значений для в уравнении 4а:

Таким образом, последний выбор оказывается под угрозой. Остается только одна возможность:

Выбор В этом случае к ограничениям (4а) и добавляются

должно быть нечетным. Используя вновь результаты выбора 1, получим

Значение 5 уже закреплено за А, поэтому или 7. Но анализ уравнения дает из уравнения получаем, что

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

Выбор следовательно Сразу составим новые уравнения

Первым анализируется ограничение которое по условию четности дает отсюда следует

так как Е уже равно 9 и Отсюда получаем

При и анализ уравнения дает

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

Выбор Сначала анализируется ограничение

Но поэтому необходимо, чтобы и Подставляя эти данные в уравнения получаем . И далее . С другой стороны, ограничение

требует, чтобы что приводит к противоречию. Остается последний случай:

Выбор Имеем

Из ограничения следует, чтоодновременно должно выполняться или 7, а также откуда ALICE выводит и Решение уравнения путем перебора дает

1. Если то

следовательно, а также Затем

Решение задачи выглядит следующим Образом:

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

Таким образом, найденное решение является единственным, дерево поиска приведено на рис. 8.12. Дерево имеет шесть

Листьев, полное время его обработки составляет 9 с, что меньше времени, которое требуется программе, работающей по принципу перебора, типа приведенной в гл. 5 (1 мин и 10 с на ЭВМ IBM 4331).

Рис. 8.12. Дерево поиска системы ALICE для решения задачи Ветви, помеченные звездочкой, не приводят к решению.

8.8.2. Пример 2

Рассмотрим более сложную задачу — проблему перестановок, которая была предложена Марселем Шутценбергером.

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

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

Вектор опережения определяет: если то расположен слева от

если то расположен справа от кроме того, . В формальной записи

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

Рассмотрим простой числовой пример. Возьмем в качестве данных Тогда

Отсюда

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

Теперь из ограничения (а) получаем

и только элемент может быть равным единице

С другой стороны,

Из ограничений видно, что единственным возможным предшественником для 4 является

Из ограничения в свою очередь следует

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

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

В: Проверить частичное решение и продвинуться дальше в случае успеха.

С: В случае неудачи, но если надежда на получение решения еще не потеряна, вернуться назад.

Этап А соответствует нахождению следующего элемента. Для естественного порядка на интервале имеем

начиная с нулевых начальных значений.

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

удовлетворено ли ограничение на монотонность?

удовлетворено ли ограничение на опережение?

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

Тест наоборот, очень прост. В среднем он исключает большее число случаев, чем тест поэтому будем использовать его первым. Приведем теперь уточненную схему программы.

Процедура PERM: Определить все перестановки первых целых чисел с учетом данных булевых векторов .

(см. скан)

(см. скан)

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

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

8.8.3. Решение задачи системой ALICE

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

При ограничения, накладываемые вектором дают

или

Но должно удовлетворять биекции, поэтому

Отсюда следует

Дуги в графе отсутствуют для всех для которых выполняется условие Ограничения, накладываемые вектором а, приводят к 22 неравенствам:

Ограничения типа система предпочитает ограничениям типа Ф. Эти ограничения ALICE анализирует в порядке, который считает для себя удобным. Он задается вычислением функции Грунди (разд. 8.5.2) и поясняется на рис. 8.13.

Рис. 8.13. Граф ограничений по монотонности.

Первым проверяемым ограничением является из которого следует Тогда влечет за собой Кроме того,

Теперь некоторые проанализированные ограничения с неравенством исчезают, так как становятся тривиальными. Это относится, например, к или к поскольку

На этом этапе новая информация не может быть выведена, но является сюръекцией и точка 9 пространства изображений имеет в качестве предшественников только

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

Таким образом, только могут быть равными 8. Выбор приводит к

Точка 7 теперь имеет только двух предшественников. Допуская, что приходит к выводу, что или

Положив приходим к выводу, что , следовательно,

Приняв и учитывая единственное оставшееся ограничение , получаем для данного случая четыре решения

Для того чтобы найти 42 решения задач, надо вернуться только на шесть двоичных выборов, т. е. на 64 возможности вместо

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

Процедура PERM будет работать всегда одинаковым образом. Она последовательно находит векторы 1, 12, 123, 13, 132, 1324, 14, 142, 1423, 143, 1432, 14325 и т. д., хотя в действительности, как это сразу и определяет ALICE с помощью анализа ограничений, содержащих неравенства типа с необходимостью следует

Кроме того, при этом тривиально удовлетворяются все ограничения, связанные с вектором опережения, так как для выполняется соотношение Следовательно, единственная степень свободы связана со значением в множестве [1, 99]. Имеется только 99 перестановок, удовлетворяющих условию задач. Время, которое требуется ALICE для их нахождения, имеет полиномиальную зависимость от

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

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