8.3. Модуль решения задачи

Ниже этот модуль описан в общих чертах. Более подробное описание приведено в разд. 8.5.

Система ALICE имитирует поведение человека, приступающего к решению задачи:

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

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

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

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

В процессе решения системой предпринимаются три основных действия.

• Перенос ограничений

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

• Построение гипотез

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

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

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

8.3.1. Перенос ограничений

Эта фаза основана на алгоритме унификации (гл. 3), который позволяет выполнять операции с выражениями так же, как

мы это делаем вручную. Он позволяет также упрощать выражения типа

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

где — целые, то она выводит из них новую информацию или

Возвращаясь к первому примеру (разд. 8.2), из алгебраического ограничения на величину вектора длительностей

выполняя суммирование по выводит

где является оптимальной величиной числа процессоров. При получаем Для лучшего понимания этой фазы приведем полное решение примера 2 с булевыми переменными, которое осуществляется с помощью переноса. Напомним условие: найти решение системы уравнений, в которой переменные принимают значения 0 или 1. Итак,

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

которое приводится к виду

Затем анализируется ограничение (3), которое дает

С учетом ограничения находим

Получается система уравнений, эквивалентная исходной:

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

или, упрощая выражение (), получаем

Из ограничения следует и приходим к окончательному результату

С уже имеющимися результатами это дает единственное решение: