8.3.2. Перебор вариантов

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

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

Различные типы и критерии выбора

Оригинальность системы ALICE заключается в постоянном самопрограммировании. Схема поиска решения не является

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

1) Какого типа выбор должен быть сделан?

2) Какие критерии можно использовать, осуществляя выбор?

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

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

Рис. 8.2. Результат выбора в пространстве поиска.

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

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

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

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

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

1. Число ограничений, в которых участвует одна и та же - переменная.

2. Сложность ограничений.

3. Число значений, еще возможных для переменной.

4. Число множеств, отображения. которых должны быть разъединены.

5. Значения коэффициентов.

6. Значения второго члена.

7. Границы изменения переменной.

8. Различие между локальными оптимальными затратами и вторичными затратами.

9. Число возможных предшественников.

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

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

Рис. 8.3. Общий план решения для системы ALICE.

Общий план решения (рис. 8.3)

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

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

1. Она нашла нижнюю границу стоимости и умеет находить решение, стоимость которого в точности равна этой границе (см. пример I).

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

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

Решение примеров

Напомним, что работа системы ALICE подробно описана в разд. 8.5.

Пример 1. План решения: 1) анализ трудности задачи;

2) поиск хорошего решения; 3) доказательство его оптимальности.

Критерии, подходящие для данного случая; длительность выполнения заданий; доступное место в процессоре; справедливое распределение заданий по процессорам.

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

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

общий лимит времени. С учетом длительностей выполнения заданий:

и с это дает

Таким образом, полная стоимость составляет 4 процессора. Этап 3. ALICE вычисляет нижнюю границу оптимального значения, суммируя ограничения на предельное время. Система знает, что оптимальная стоимость удовлетворяет условию

Отсюда следует, что

Решение задачи на этом закончено.

Рис. 8.4. Оптимизация числа процессоров.

Замечание. Для этого примера выбраны благоприятные данные. Однако если одно из значений длительности изменить с 6 до 7, то ход решения будет сильно отличаться от приведенного, как это видно из рис. 8.4, и ясно из структуры системы. Действительно, хотя ALICE и в этом случае находит то же оптимальное значение, равное 4, но она не сможет разместить второе задание длительностью 6 без привлечения пятого процессора на этапе 2. Но на этапе 3 устанавливается достаточность четырех процессоров. Система показывает, что это невозможно (третий случай доказательства оптимальности), осуществляя единственный значимый выбор — перемещая задание длительностью 8 с третьего процессора на четвертый. И снова задание длительностью 6 нигде не удается разместить. Отсюда следует, что на этот раз оптимальное значение получается равным 5.

Пример 2. Он был полностью решен в разд. 8.3.1. Наглядна польза рассмотрения различных наборов критериев: бессмысленно

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

Рис. 8.5. Локализация (внутреннее представление): район не может быть обслужен с помощью или

Пример 3. Его формулировка в действительности целиком взята из графического представления в системе ALICE, которое приведено на рис. 8.5.

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

Тогда полная стоимость

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

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

Кроме того, из этих минимальных стоимостей можно всякий раз вычитать начальную стоимость без изменения решения. Далее будем рассматривать работу ALICE с новыми уменьшенными стоимостями: (0, 0, 1, 0, 6, 0, 0, 3).

Этап 3. Остаточная стоимость размещения центра 5 недопустима из-за того, что она больше разности то же можно сказать о центре 8. Отметим, что даже в тех случаях, когда в оптимизации нет необходимости, ALICE дает относительное расстояние до оптимума.

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

В данном случае выбор является вынужденным. Если бы отличалось от 4, то полная стоимость с необходимостью увеличилась бы на 1. Если же то области 3 и 5 также охватываются обслуживанием. И наконец, с нулевой приведенной стоимостью, так что расположение мест 1, 4 и 7 является оптимальным со стоимостью 17.