8.2. Язык системы ALICE

Название системы ALICE происходит от первых букв ее названия (A Language for Intelligent Combinatorial Exploration).

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

Таким образом, класс задач, решаемых системой ALICE, может быть выражен в общем виде:

Найти величину где X — конечное данное, которое удовлетворяет совокупности ограничений

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

Формулировки на языке ALICE

Формулировка задачи состоит из четырех частей:

1) определение, задаваемое ключевым словом “пусть”, описывает объекты, участвующие в решении задачи, и задает их типы;

2) с помощью ключевого слова «найти» задаются цель, которую необходимо достигнуть, и неизвестные величины, значения которых необходимо определить;

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

4) наконец, задаются числовые или формальные данные в соответствии с описаниями, приведенными в первой части, на чем полностью завершается формулировка решаемой задачи.

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

Этот обычный текст преобразуется в ALICE в следующий:

Определим множество Т заданий, которые перенумеруем от

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

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

(см. скан)

(см. скан)

Это — строгая формулировка проблемы. Мы видели, что ALICE работает с числовыми данными, которые вводятся в четвертой части в том порядке, в котором они были указаны в тексте: сначала и затем вектор длительностей. Система использовалась для обработки ситуаций, в которых число заданий доходило до нескольких сотен (см. разд. 8.7); здесь приводится пример, содержащий только девять заданий, длительности которых составляют соответственно 6, 2, 8, 3, 6, 15, 6, 9 и 13, а значение что даст нам возможность в разд. 8.3 проследить за полным решением задачи системой. Тогда три последние строки формулировки будут такими:

Отметим, что для различных значений длительностей решения существенно различаются, в частности, если длительность задания 1 изменится с 6 до 7. Мы увидим, что система адаптируется к входным данным, но не опирается на использование какого-то определенного метода для формального решения этой задачи (разд. 8.3).

Пример 2. Существуют программы типа “Численный анализ” для решения линейных или нелинейных задач в области

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

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

(см. скан)

Числовых данных здесь нет.

Пример 3. В городе необходимо наилучшим образом расположить центры аварийных служб (медицинской помощи, пожарной команды и т. д.). Для каждого возможного размещения центра в прилегающем районе определяется задержка, как показано на рис. 8.1. Этими службами должны быть обеспечены все районы. Кроме того, необходимо обеспечить минимальную общую стоимость организации всех центров при известной стоимости каждого из них. (Встречаются также аналогичные задачи без оптимизации.) Через обозначены возможные места расположения центров, окружности показывают границы обслуживаемых районов, — сами районы. Введем также обозначения Стоимости организации центров на указанных местах обозначим с помощью вектора (3, 7, 5, 8, 10, 4, 6, 9).

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

Рис. 8.1. Размещение центров аварийных служб.

Теперь сформулируем задачу, используя указанные обозначения:

(см. скан)

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

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

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

Эти задачи решаются достаточно быстро. Их решение системой ALICE описано в разд. 8.3.2.

В языке системы ALICE имеются и другие ключевые слова, которые облегчают запись классических ограничений. Система “знает” понятия сюръекции, инъекции и биекции. Она “понимает” все обычные логические обозначения, знает, что такое дерево, путь, схема. Целью разработки системы являлось сохранение доступных, максимально понятных формулировок задач, близких к обычному разговорному языку. В табл. 8.1 приведен полный список известных ALICE слов и их значения (ранг слова представляет собой число членов, которыми оно управляет).

Каждое слово, не входящее в этот список, рассматривается как новый объект, описание которого должно содержаться в части определений после слова ПУСТЬ.

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