ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2008, том 48, < 1, с. 159-175
УДК 519.658
ЛОКАЛЬНЫЕ ЭЛИМИНАЦИОННЫЕ АЛГОРИТМЫ РЕШЕНИЯ РАЗРЕЖЕННЫХ ДИСКРЕТНЫХ ЗАДАЧ
© 2008 г. О. А. Щербина
(Institut für Mathematik, University of Vienna, Vienna, Austria) e-mail: oleg.shcherbina@univie.ac.at
Поступила в редакцию 18.04.2007 г. Переработанный вариант 01.11.2007 г.
Рассмотрен класс локальных алгоритмов элиминации, позволяющих на основе вычисления локальной информации получать глобальную информацию о решении всей задачи. Описана общая структура локальных алгоритмов элиминации, использующих окрестности элементов, структурный граф, описывающий структуру задачи, а также алгоритм элиминации. Представителями этого класса алгоритмов являются локальные алгоритмы декомпозиции задач дискретной оптимизации, алгоритмы несериального динамического программирования (НСДП), алгоритмы сегментной элиминации, методы древовидной декомпозиции. Показана возможность реализации локальных алгоритмов элиминации для решения оптимизационных задач. Библ. 34. Фиг. 5. Табл. 9.
Ключевые слова: разреженные дискретные задачи, локальные элиминационные алгоритмы, теория графов, динамическое программирование.
1. ВВЕДЕНИЕ
Использование локальной информации (см. [1], [2]) при изучении сложных дискретных систем и при разработке методов декомпозиции для решения больших разреженных дискретных задач является весьма актуальной, причем упомянутые задачи принадлежат как области дискретной оптимизации (ДО) (см. [3]), так и области искусственного интеллекта (см. [4], [5], [6]), баз данных (см. [7]). В линейной алгебре разработаны мультифронтальные методы решения разреженных систем линейных уравнений (см. [8]), имеющие декомпозиционный характер.
Использование моделей и алгоритмов ДО позволяет решать многие практические задачи, такие как задачи теории расписаний, оптимизации на сетях, маршрутизации трафика в коммуникационных сетях, задачи размещения экономических объектов, задачи оптимизации автоматизированных систем планирования ресурсов (ERP), задачи логистики, в частности оптимизацию цепочек предложения (Supply Chain Management, см. [9]). К задачам искусственного интеллекта относятся доказательство теорем, задачи SAT (см. [10]), задачи робототехники, расчета байесовских апостериорных вероятностей при проектировании экспертных систем (см. [11]), задачи теории расписаний (см. [12]) и т.п.
В последнее время возрос интерес к графовым декомпозиционным подходам, в том числе к методам древовидной декомпозиции (ДД - tree décomposition). Важность и актуальность указанных подходов обусловлены результатами из [13] и [14], в которых доказано, что ряд NP-трудных задач, поставленных в монадической логике второго порядка, может быть решен за полиномиальное время с помощью методов динамического программирования на графах, описывающих структуру задачи ДО, с ограниченной древовидной шириной.
При изучении сложных объектов не всегда возможно получить (или вычислить) полную информацию об объекте в целом, поэтому представляет интерес получить информацию об объекте, рассматривая его по частям, т.е. локально.
В [1] описываются локальные алгоритмы (ЛА) вычисления информации. Локальный алгоритм A изучает элементы в порядке, задаваемом алгоритмом упорядочения Ап, производит вычисление функции ф, значение которой на каждом шаге алгоритма определяет вид информационной отметки, и расставляет пометки, используя при этом локальную информацию об элементах из окрестности данного элемента. Функция ф, порождающая алгоритм, - это функция от двух аргументов, первый из которых пробегает множество элементов, а второй - множество окрестностей.
ЛА декомпозиции (см. [15]—[19]) задач ДО имеют свою специфику, состоящую в том, что они не вычисляют предикаты, а, используя принцип оптимальности Беллмана, вычисляют оптимальные решения подзадач, соответствующих блокам задачи ДО. Шаг ЛА % заключается в смене окрестностей и замене индекса p на p + 1 (хотя вовсе не обязательно переходить к окрестности с индексом на единицу больше, можно переходить и от Sp к Sp + S), на каждом шаге алгоритма для каждого фиксированного набора переменных граничного кольца запоминаются значения переменных соответствующей окрестности, в этом состоит одно из важных отличий ЛА % от ЛА A: запоминается информация не о предикатах, а о значениях переменных в решениях подзадач; такую информацию Ю.И. Журавлёв предложил называть индикаторной информацией.
Успехи графовых декомпозиционных схем, позволяющих справиться с решением NP-труд-ных задач с помощью алгоритмов динамического программирования (см. [20]), вызвали интерес к применению этих методов и в областях, отличных от оптимизации.
Для решения ряда разреженных задач, возникающих в самых разных областях, были предложены обобщения принципа динамического программирования, такие как обобщение из [4] (сегментная элиминация) и др. Интересно заметить, что все структуры, для которых были предложены отмеченные обобщения, характеризовались возможностью находить на базе локальных решений решения всей задачи путем анализа окрестностей элементов задачи. В [11] даже употребляются термины локальные вычисления, вычисление глобальной информации по локальной.
Автор считает важным подчеркнуть возможность использования именно локальной информации (т.е. информации об элементах окрестности элемента) при решении этих задач и предложить класс локальных алгоритмов элиминации (ЛАЭ) для их решения, позволяющих осуществить вычисление глобальной информации о решении всей задачи с помощью локальных вычислений (обычно решений подзадач). Отметим, что главным фактором в рассматриваемых ниже задачах является локальность информации, введение и изучение окрестностей (см. [2]) элементов. Кроме того, локальные алгоритмы вычисления информации были предложены в [1] не только для решения оптимизационных задач, но и как алгоритмы более широкого плана.
2. СТРУКТУРА ДИСКРЕТНОЙ ЗАДАЧИ
Структура дискретной задачи задается зависимостями, сформулированными в рамках рассматриваемой парадигмы моделирования, и может быть задана как исходными элементами (переменными) с заданием системы окрестностей (см. [2]) этих переменных и порядка просмотра этих переменных с помощью ЛАЭ, так и различными производными структурами - блочными, блочно-древовидными, задаваемыми так называемым структурным графом.
ЛАЭ элиминирует локальные элементы структуры задачи, задаваемой структурным графом, вычисляя и записывая локальную информацию об этих элементах в виде новых зависимостей, добавляемых к задаче.
Процедура ЛАЭ, таким образом, разбивается на две части: прямая часть - элиминация элементов, вычисление и запоминание локальных решений и получение в конце значения критерия, обратная часть - нахождение глобального решения всей задачи по имеющимся таблицам с локальными решениями, обеспечивающего достижение критерия в прямой части.
Алгоритмическая схема ЛАЭ представляет собой бесконтурный орграф (directed acyclic graph, DAG), вершины которого соответствуют локальным подзадачам, а ребра выражают информационную зависимость подзадач друг от друга. Так, если подзадача B требует для своего решения информацию о решении подзадачи А, это может быть графически изображено, как на фиг. 1. Оператор ЛАЭ показан на фиг. 2.
Структурный граф может быть как графом взаимосвязей исходных элементов (например, переменных или ограничений) задачи, так и конденсированным графом (см. [25]). Конденсированный граф может быть получен с помощью конденсирования (или сгущения) подмножества элементов (например, подграфа) графа в один элемент, называемый конденсированным элементом. Исходное подмножество (подграф), образовавшее конденсированный элемент, называется детализированным графом конденсированного элемента. Конденсированный элемент может быть вершиной (вершинная конденсация) или ребром (реберная конденсация).
ЛАЭ анализирует окрестность Nb(x) текущего элемента x в структурном графе задачи, применяет оператор элиминации, зависящий от конкретной задачи, к этому элементу, вычисляя функцию Ä(Nb(x)), содержащую локальную информацию об элементе x, а также локальное решение x*(Nb(x)). Далее элемент x элиминируется, а из элементов окрестности Nb(x) создается
О
Фиг. 1.
3
Подзадачи
Фиг. 2.
клика. Элиминация элементов и создание клик изменяет структурный граф и окрестности элементов. Обратная часть ЛАЭ восстанавливает решение всей задачи на основе сохраненных локальных решений х*(ЫЪ(х)).
при ограничениях
(X)Я 0, ' е М = {1, 2,..., т},
X] е О}, ] е N = {1, 2, ..., п},
где Ук с {х1; ..., хп}, X' с {х1; ..., хп}; Я' е {<, >, =}, ' е М = {1, 2, ..., т}; О] - конечное множество возможных значений переменной X] е О],] е N = {1, 2, ..., п}.
Функции/к (к е К) называются компонентами целевой функции.
В зависимости от вида структурного графа элементом х может быть либо отдельная переменная (если структурный граф - граф взаимосвязей переменных, см. [17], [18], [20]), либо подмножество переменных (структурный граф - граф взаимосвязей блоков) при блочной элиминации переменных (см. [18], [20]) или древовидной декомпозиции (см. [16], [19]).
Описание структуры задачи ДО может осуществляться с различной степенью детализации. Рассмотрим вначале представление структуры с помощью графа взаимосвязей переменных О = (V, Е). Вершина графа взаимосвязей ] е V соответствует переменной X] задачи оптимизации; вершины графа 1 и 2 смежные (обозначается 1 ~ 2) только тогда, когда соответствующие этим вершинам переменные х1 и х2 появляются вместе в одной компоненте /к целевой функции или в одном и том же ограничении ' (другими словами, если переменные х1 и х2 входят одновременно во множество Ук или во множество X'). Далее множество вершин графа будем отождествлять с множеством переменных. Пусть и 5 - множества вершин графа, а ] - его вершина.
4. ЛАЭ В ЗАДАЧАХ ОПТИМИЗАЦИИ
Рассмотрим задачу ДО следующего вида:
(Р)
Введем необходимые обозначения.
1. Смежность множеств 5 ~ 52 (читается: "5 смежно 52"), если существует вершина]1 в 5 и вершина ]2 в 52 такие, что ]1 ~]2; ] ~ 5 означает {/
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.