МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНО-ОПТИМИЗАЦИОННЫХ ЗАДАЧ

Широкий круг методов поиска решения комбинаторно-оптимизационных задач основан на двух

идеях: декомпозиция пространства решений и выбор перспективного подмножества вариантов на основе некоторой оценки.
Рассмотрим процесс декомпозиции. Множество возможных вариантов решения М разбивается в соответствии с каким-то принципом, как правило, на непересекающиеся подмножества М такие, что ∪ Мi = М, Далее, используя тот же принцип, полученные подмножества вновь разбиваются на подмножества, включающие меньшее количество вариантов. После некоторого шага разбиения каждое множество содержит по одному варианту решения. Сопоставим каждому подмножеству вершину графа. Соединив ребром вершины, соответствующие подмножествам Мi и Мj (если подмножество Μj получено непосредственным разбиением подмножества Мi), придем к так называемому дереву решений.
Принцип разбиения пространства решений связан с видом преобразований, которые необходимо выполнить над графом для получения графа результата.
Проиллюстрируем сказанное примером поиска простых цепей (маршрутов) из вершины х1 в вершину х4 в графе G(X, U), показанном на рис. 3.1, а. Начиная с вершины х1 будем включать в маршруты ребра в порядке возрастания их номеров. Вершина 0 дерева решений (рис. 3.1, б) соответствует множеству всех возможных вариантов маршрутов из x1 в х4. Принцип разбиения этого множества в данном случае естественно вытекает из процедуры последовательно-параллельного прослеживания вариантов маршрутов по ребрам графа G, т.е. последовательного включения ребер в возможные маршруты.

простых цепей по методу в ширину (б) и в глубину

с возвращением (в)

включению в маршрут ребра u1 вершины с номерами 2 и

3 - ребер и3 и и6. Таким образом, на первом шаге (на 2-м уровне дерева решений) множество М разбивается на три непересекающихся подмножества вариантов, одно из которых М1, соответствующее вершине 1 дерева решений, порождает следующие три варианта простых цепей графа G: {u1, u2, u5}, {u1, u4, u7} и {u1, u8, и9}. Далее процесс очевиден. Обратим внимание на то, что в данном случае на следующий уровень дерева решений переходим только после того, как были получены все подмножества текущего уровня.
Описанный процесс реализует получение всех вариантов решения по методу поиска в ширину с последовательным формированием состава вариантов и соответствует полному перебору. Очевидно, что в рассмотренном виде этот метод можно использовать, если необходимо найти все варианты решения.
Другая стратегия разбиения множества всех возможных вариантов на подмножества приводит к иному методу, который назовем поиск в глубину с возвращением. Рассмотрим его на том же примере. Принцип разбиения пространства решений - тот же, что и выше. Выделим на 1-м шаге из множества Μ подмножество М1 включив в маршрут ребро и1 из возможных {и1, и3, и6} в соответствии с минимальным индексом.
Таким образом, разобьем множество Μ на подмножества М1 и M \ M1. Тогда на 2-м уровне дерева решений получим вершину 1 (см. рис. 3.1, в). Множество M1 разобьем на подмножества М2 и М1 \ М2, добавив в маршрут ребро и2. На третьем уровне дерева решений получим вершину 2. Продвигаясь по этой ветви в глубь дерева решений получим один из возможных вариантов маршрута, соединяющего вершины x1, и х4 – x1, х2, х3, х4 или в виде последовательности ребер – u1, и2, u5, что соответствует вершине 3 дерева решений (сравните номер такой же вершины на рис. 3.1,б). Теперь возвращаемся по ветви вверх, пока не придем в вершину, такую, что из множества вариантов, ей сопоставленных, можно выделить некоторое подмножество в соответствии с принятым принципом. В нашем примере такой вершиной будет вершина с номером 1.

включению в маршрут ребра u1 вершины с номерами 2 и

3 - ребер и3 и и6. Таким образом, на первом шаге (на 2-м уровне дерева решений) множество М разбивается на три непересекающихся подмножества вариантов, одно из которых М1, соответствующее вершине 1 дерева решений, порождает следующие три варианта простых цепей графа G: {u1, u2, u5}, {u1, u4, u7} и {u1, u8, и9}. Далее процесс очевиден. Обратим внимание на то, что в данном случае на следующий уровень дерева решений переходим только после того, как были получены все подмножества текущего уровня.
Описанный процесс реализует получение всех вариантов решения по методу поиска в ширину с последовательным формированием состава вариантов и соответствует полному перебору. Очевидно, что в рассмотренном виде этот метод можно использовать, если необходимо найти все варианты решения.
Другая стратегия разбиения множества всех возможных вариантов на подмножества приводит к иному методу, который назовем поиск в глубину с возвращением. Рассмотрим его на том же примере. Принцип разбиения пространства решений - тот же, что и выше. Выделим на 1-м шаге из множества Μ подмножество М1 включив в маршрут ребро и1 из возможных {и1, и3, и6} в соответствии с минимальным индексом.
Таким образом, разобьем множество Μ на подмножества М1 и M \ M1. Тогда на 2-м уровне дерева решений получим вершину 1 (см. рис. 3.1, в). Множество M1 разобьем на подмножества М2 и М1 \ М2, добавив в маршрут ребро и2. На третьем уровне дерева решений получим вершину 2. Продвигаясь по этой ветви в глубь дерева решений получим один из возможных вариантов маршрута, соединяющего вершины x1, и х4 – x1, х2, х3, х4 или в виде последовательности ребер – u1, и2, u5, что соответствует вершине 3 дерева решений (сравните номер такой же вершины на рис. 3.1,б). Теперь возвращаемся по ветви вверх, пока не придем в вершину, такую, что из множества вариантов, ей сопоставленных, можно выделить некоторое подмножество в соответствии с принятым принципом. В нашем примере такой вершиной будет вершина с номером 1.

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

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

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

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

подмножествах вариантов либо лишь на некоторых. В первом случае выбор

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

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

на каждом уровне дерева решений в соответствии с некоторой оценкой, определяемой спецификой задачи, выбирают одно подмножество, не формируя (отсекая) остальные, до тех пор, пока не получим решение. Таким образом, здесь формируется только одна ветвь дерева решений. Очевидно, что алгоритмы, основанные на этом методе, должны быть весьма эффективными в смысле затрат времени и памяти ЭВМ. Если оценка выбора является отсекающей, т.е. с вероятностью, равной единице, позволяет судить о том, что оптимальный вариант находится в данном подмножестве, получаем точное решение. В противном случае гарантируется лишь приближенное. Это положение имеет очень большое значение, так как в большинстве источников утверждается, что последовательные алгоритмы, реализующие метод поиска в глубину, гарантируют лишь приближенное решение.
Проиллюстрируем сказанное примером идеи алгоритма Прима, предназначенного для построения остовного дерева минимального веса графа G. В § 4.1 в ходе доказательства правильности этого алгоритма будет показано, что выбор на каждом шаге ребра минимальной длины (не образующего цикл) обеспечивает получение точного решения. Таким образом, минимальная длина очередного ребра является достоверной оценкой, а включение в строящееся дерево такого ребра отсекает все вершины дерева решений, которые соответствуют вариантам остовного дерева графа G, не содержащим этого ребра. На рис. 3.2 показаны полный четырех вершинный граф G, дерево решений и полученное остовное дерево минимальной длины; здесь Μ1 и — все варианты деревьев графа G(X, U), содержащих и не содержащих ребро и1; М2 ⊂ М1 - все варианты деревьев, включающих ребра и1 и u5; и ⊂ М1 - все варианты деревьев, содержащих ребро u1 и не содержащих ребро и5; М3 - остовное дерево минимальной длины графа G: {u1, u5, u6}, вес которого равен 12.

и остовное дерево минимальной длины (в)

поиска относится к классу эвристических и представляет упрощенный вариант метода

поиска в ширину. Он заключается в следующем: множество решений разбивается на подмножества 1-го уровня, каждая вершина которого становится началом ветви, формируемой по методу поиска в глубину. Переход к формированию подмножеств следующего уровня дерева решений выполняется после получения подмножеств всех ветвей текущего уровня. Дерево решений, иллюстрирующее идею метода, показано на рис. 3.3; здесь n - количество искомых решений, следовательно, на j-м уровне дерева n подмножеств Мi j, i = - множество индексов этих подмножеств (верхний индекс соответствует номеру уровня дерева решений).







Рис. 3.3. Дерево решений по методу параллельного поиска
В зависимости от специфики задачи подмножества разных ветвей могут быть как пересекающимися, так и непересекающимися. Рассмотрим задачу компоновки схемы в n конструктивных модулей. Множество элементов схемы Э поставлено во взаимно-однозначное соответствие множеству вершин X гиперграфа Э ↔ X. Указанная задача может быть решена алгоритмом, реализующим метод параллельного поиска (алгоритм параллельного разрезания гиперграфа см. § 5.3). Результатом его работы будет разбиение множества вершин гиперграфа на n подмножеств X, i = . Так как один и тот же элемент схемы не может входить в разные конструктивные модули и состав Xi определяется по методу поиска в глубину последовательным включением вершин x ∈ Х в X1i (X1i соответствует Mji), то Хji ∩ Xjp = ∅ для всех i, p ∈ I = . Таким образом, в данной задаче подмножества, принадлежащие разным ветвям дерева решений, должны быть непересекающимися.

варианты решения, т.е. удовлетворяют условию ∪М1i = М и оценка

выбора подмножества в каждой ветви является отсекающей, то метод обеспечивает точное решение.
Вырожденным случаем оценочной функции является невычисляемая отсекающая оценка, например, некоторое заранее сформулированное условие. Примером может служить задача о кодовом замке. Пусть кодовый замок имеет четыре разряда, и каждый разряд может принимать значения «0» и «1». Мы забыли код, но помним, что в нем не может быть подряд трех нулей или единиц -условие отсечения. Мы готовы перепробовать все коды, но хотели бы избежать этого. Нам нужен алгоритм для систематического генерирования четырехразрядных комбинаций из «0» и «1». Учитывая вероятность того, что мы откроем замок раньше, чем будут испытаны все комбинации, целесообразно использовать метод поиска в глубину с возвращением. Примем направление обхода дерева решений слева направо. Принцип разбиения множества решений - присваивание соответствующему разряду значения «0» или «1» (количество сгенерированных разрядов равно номеру уровня дерева решений). Очевидно, что дерево будет бинарным. Тогда алгоритм можно сформулировать так: движемся вниз по дереву, придерживаясь левой ветви, пока не получим полной комбинации либо не выясним нецелесообразность этого (рис. 3.4 - отсечение левой ветви после вершины с кодом 11). Если комбинация не подходит, либо ее или некоторое множество комбинаций нет смысла набирать (отсечение по условию), то возвращаемся в ближайшую вершину и пробуем спускаться по другой ветви (левая ветвь - разряд ставим в положение «1», правая - в «0»). В некоторых источниках [4] этот метод называют «программирование с отходом назад».

поиска кода по методу в глубину с возвращением

Рассмотрим пример использования текущего значения целевой функции в качестве оценки перспективности во всех вершинах дерева решений и этой же величины в качестве отсекающей - в «особых» вершинах дерева решений. В §3.1 коротко рассмотрена задача нахождения всех простых цепей из исходной вершины графа в некоторую конечную. Модифицируем ее: необходимо найти простую цепь (маршрут) из некоторой вершины хi в вершину xj графа G(X, U), такой, чтобы суммарная длина ребер, его составляющих, была минимальна.
Примем стратегию формирования дерева решения по методу поиска в ширину, Принцип разбиения множества на подмножества тот же, что и выше, т.е. включение в фрагмент маршрута некоторого ребра. В качестве оценочной функции примем суммарную длину ребер, составляющих фрагмент маршрута. Нетрудно убедиться, что эта величина является нижней границей длины маршрута. Действительно - это функция, определенная на вершинах дерева решений, в каждой конечной вершине она принимает значение целевой функции для соответствующего варианта маршрута и, наконец, функция возрастающая, так как длины ребер - величины положительные. Так как доказательства того, что эта оценка является отсекающей, нет, будем использовать ее в качестве оценки перспективности ветви.

с вершиной xj могут проходить через одну и ту же

вершину xk. Это свойство позволяет в особых точках дерева решений использовать суммарную длину ребер как отсекающую оценку. Отсюда, если суммарная длина ребер от вершины хi до вершины xk фрагмента маршрута Мr больше, чем фрагмента маршрута Mt то все варианты маршрутов, порождаемые фрагментом Mr следует отбросить.
На рис. 3.5, а показан граф G(X, U). Пусть исходной является вершина x1, a конечной – x8. На 1 - м уровне дерева решений (см. рис. 3.5, б) множество возможных вариантов маршрута из вершины х1 разбивается на два подмножества: маршруты из х1 через вершину х2 (вершина дерева решений 1) и через вершину х5 (вершина дерева решений 2)-длины фрагментов F1 = 10 и F2 = 8 соответственно. На основании оценки перспективности выбираем вторую вершину дерева решений и выполняем ветвление в ней. Из вершины x5 графа G можно продолжать маршруты в вершины х4 и х7. Получаем вершины дерева решений 3 и 4 (фрагмент М3 = {х1 х5, х4} с F3 = 17 и фрагмент Μ4 = {x1, x5, х7} с F4 = 29). Выбирая минимальную оценку F1 = 10 (из F1 = 10, F3 = 17 и F4 = 29), выполняем ветвление в вершине 1 дерева решений. Из вершины х2 графа G можно продолжить маршруты в вершины х3 и x4. Соответствующие вершины 5 и 6 дерева решений имеют оценку F5 = 41 и F6 = 16. Вершины 3 и 6 дерева решений имеют оценки F3 = 17 и F6 = 16 и оба фрагмента {х1, х5, x4} и {x1, х2, х4} порождают все маршруты от вершины x1 графа G до вершины x8 через вершину х4.
На основании рассмотренного выше свойства простых цепей отсекаем ребра и вершины дерева решений, следующие за вершиной 3. Этот прием используется в алгоритме Дейкстры [4].

цепи минимальной длины (б)
Изложенный в данном разделе

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

границ - универсальный, хотя и достаточно сложный метод точного решения

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

1. Сравнение оценки (нижней – FН(Мi) или верхней

– FВ(Мi) границы) со значением целевой функции для уже найденного (опорного) решения FОП. Действительно, если при решении задачи на минимум целевой функции FН(Мi) > FОП, то подмножество Мi не содержит оптимального варианта, и соответствующая вершина дерева решений отсекается. Опорное решение можно получить приближенным алгоритмом заранее либо в ходе решения задачи методом ветвей и границ. При разбиении пространства решений по методу в глубину с возвращением опорное решение получается на более ранних этапах построения дерева решений, чем при методе в ширину.
2. Сравнение двух оценок. Такое отсечение выполняется, если, например в задаче на минимум целевой функции, для подмножества вариантов соответствующей вершины можно найти оценку снизу FН(Мi) и сверху FВ(Мi). Тогда, если для некоторого подмножества Мi окажется, что FН(Мi) > FВ(Мi), то ветвление в вершине, соответствующей Μi прекращается.
3. Прекращение ветвления, если соответствующее подмножество не содержит оптимального решения, можно установить, во-первых, в «особых точках» по значениям оценочной функции, например нижней границы (см. § 3.2), и, во-вторых, если известен оптимальный среди вариантов этого подмножества. Чем точнее будет получена оценка, т.е. чем ближе она будет к значению целевой функции для оптимального варианта подмножества, тем меньшее количество вершин дерева решений будет построено и исследовано.
Точность оценки зависит от принципа разбиения множества вариантов на подмножества и вида оценочной функции или способа ее вычисления. Следовательно, если возможно использование нескольких принципов разбиения, необходимо выбирать тот, при котором оценки более точны. Как правило, число отсечений тем больше, чем сильнее отличаются оценки подмножеств.
Таким образом, лучшими являются тот принцип разбиения и такая оценочная функция, при которых разность между оценками подмножеств наибольшая, а сами оценки вычисляются с наибольшей точностью в смысле их близости к значению целевой функции для оптимального варианта подмножества. Число отсечений зависит и от способа ветвления, хотя никаких точных оценок и рекомендаций указать нельзя.