Что это такое?

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

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

Методы решения труднорешаемых задач

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

Оценки качества приближенных алгоритмов

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

Мы будем говорить, что алгоритм решает задачу с ошибкой не более чем в ρ (n) раз, если

Max(C ⁄ C *, C * ⁄ C) ≤ ρ (n)

Заметим, что поскольку максимум из двух взаимно обратных величин не меньше 1, то

Иногда удобнее использовать относительную ошибку, которая определяется как | C − C *| ⁄ C *

Мы будем говорить, что алгоритм имеет ошибку не более ε (n), если

| C − C *| ⁄ C * ≤ ε (n)

Легко проверить, что ε (n) может быть ограничена сверху через функцию ρ (n), а именно ε (n) ≤ ρ (n) − 1. В самом деле для задач на минимум это неравенство превращается в равенство. Для задач на максимум ε (n) = (ρ (n) − 1) ⁄ ρ (n) (далее нужно вспомнить, что ρ (n) ≥ 1.

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

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

Схема приближения называется полиномиальной, если для любого фиксированного ε > 0 время её работы не превосходит некоторого полинома от n . Схема приближения называется полностью полиномиальной, если время её работы ограничено некоторым полиномом от n и от 1 ⁄ ε .

Задача коммивояжера — полигон для испытания оптимизационных методов

Формулировка задачи коммивояжера (1934 г.):

Коммивояжер должен выйти из первого города, посетить по разу в неизвестном порядке города 2, 3, …, n и вернуться в первый город. Расстояния между городами известны. В каком порядке следует обходить города, чтобы замкнутый путь (тур) коммивояжера был кратчайшим?

В терминах теории графов задачу можно сформулировать так: имеется полный ориентированный граф G = (V , E), каждой дуге (u , v) которого сопоставлен вес c (u , v). Требуется найти в этом графе гамильтонов контур наименьшей стоимости.

Обратим внимание на детали, которые будут очень существенными для алгоритмов решения задачи:

1. В обеих формулировках предполагается c (u , v) ≥ 0; c (u , u) = ∞ для всех u , v ∈ V .
2. В наивной формулировке предполагается c (u , v) = c (v , u) для всех u , v ∈ V , т. е. граф можно считать неориентированным. Такая задача называется симметричной задачей коммивояжера. Однако, в общем случае, это необязательно.
3. В наивной формулировке предполагаем, что для всех u , v , w ∈ V с (u , v) ≤ c (u , w) + c (w , v) (неравенство треугольника), что нередко выполняется в практических задачах. Однако вообще говоря, это неверно.

Теорема

Пусть P ≠ NP , ρ ≥ 1. Тогда не существует полиномиального приближенного алгоритма, решающего общую (более того, симметричную) задачу коммивояжера с ошибкой не более чем в ρ раз.

Доказательство. Для доказательства заметим, что взяв произвольный граф G = (V , E) и сопоставив ему полный граф G ′ с функцией стоимости c (u , v) = 1, если (u , v) ∈ E и ρ | V | + 1 иначе. Убедимся, что наш полиномиальный алгоритм будет определять, есть ли в графе G гамильтонов цикл, что невозможно.

Метод ветвей и границ ("поиск с возвратом", "backtracking")

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

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

Рассмотрим дискретную экстремальную (для определенности — на минимум) задачу в общем виде:

Пусть задано дискретное множество A и определенная на нем функция f . Обозначим минимум функции f на X как F (X).

Требуется найти x 0 ∈ A: f (x 0) = F (A)

Замечание 1

Пусть A = A 0 ∪ A 1 ∪ … ∪ A k , A i ∩ A j = Ø, i ≠ j . Причем F (A) < F (A 0), т. е. на A 0 минимум не достигается.

Тогда справедливо следующее: F (A) = min { F (A i) | i ∈ 1: k }

Замечание 2

Пусть Φ — функция, заданная на совокупности подмножеств множества A так, что Φ (X) ≤ F (X) ∀ X ⊂ A

Пусть x * — произвольный элемент A и пусть f * = f (x *).

Тогда справедливо следующее: F (A) = min { f *, min { F (A i) | i ∈ 1: k , Φ (A i) ≤ f *} }

Эти два соображения позволяют предложить следующую технологию поиска минимума. Разобьем множество A на какие-либо подмножества A i и на каждом из них найдем нижнюю оценку Φ . Для элементов множества A будем вычислять значения функции f и запоминать наименьшее в качестве рекордного значения. Все подмножества, у которых оценка выше рекордного значения функции (f *), объединим в подмножество A 0 , чтобы в дальнейшем не рассматривать.

Теперь выберем какое-либо из множеств A i , i > 0. Разобьем это множество на несколько более мелких подмножеств. При этом мы будем продолжать улучшать рекордное значение f *. Этот процесс продолжается до тех пор, пока не будут просмотрены все множества A i , i > 0.

Более наглядно метод ветвей и границ (поиск с возвратом) можно объяснить с помощью дерева возможностей. Узлы такого дерева можно рассматривать как совокупности конфигураций (подмножества A i множества A), а каждый потомок некоторого узла представляет подмножество этой совокупности. Наконец, каждый лист представляет собой отдельную конфигурацию.

Пример 1. Задача коммивояжера (алгоритм Литтла)

Рассмотрим работу этого алгоритма на конкретном примере.

Пусть имеется граф, заданный матрицей смежности:

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

Приведем исходную матрицу по строкам

Исходная

Приведенная по строкам

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

(Отметим, что сумма констант приведения есть 4 + 6 + 3 + 4 + 3 + 7 = 27)

А затем по столбцам:

(Отметим, что сумма констант приведения здесь есть 0 + 2 + 0 + 1 + 0 + 4 = 7, а всех констант: 27 + 7 = 34)

Теперь, тур, проходящий только через ребра нулевой стоимости, будет, очевидно, минимальным. Для того, чтобы определить его стоимость, прибавим к нулю только что вычисленную константу 34:

Таким образом, мы получили нижнюю оценку стоимости класса всех возможных туров. Т. е. минимальный тур в данной задаче не может стоить меньше, чем 34.

Назовем оценкой нуля в позиции (i , j) в матрице сумму минимальных элементов в i -й строке и j -м столбце (не считая сам этот ноль). Оценим теперь каждый ноль в приведенной матрице:

Оценки, равные нулю, не указаны. Оценка k нуля, в позиции (i , j) означает буквально следующее: если в тур не будет включен путь из i в j (стоимостью 0), то придется доплатить как минимум k. Поэтому, можно разделить класс всех возможных туров на два: туры, содержащие ребро (i , j) и туры, не содержащие его. Для последних минимальная оценка увеличится на k .

Рассмотрим ребро, соответствующее нулю с максимальной оценкой. В данном случае это ребро (1, 2). Таким образом, как только что было замечено, класс всех туров разбивается на два: содержащих ребро (1, 2) и не содержащих его. Нижняя оценка стоимости второго класса туров увеличивается до 35. Чтобы определить оценку для первого класса туров удалим из матрицы строку 1 и столбец 2 (Обозначим ее как C [(1,2)]):

Т. к. матрицу удалось привести на 1 (по 1-му столбцу), то оценка класса туров с ребром (1, 2) увеличивается на 1 и становится равной 35.

Разбиение на классы и сами оценки можно представить в виде дерева:

Таким образом, класс (ВСЕ) был разбит на два и были вычислены соответствующие оценки.

Выберем теперь класс с наименьшей оценкой и повторим этот процесс для него. Затем из двух полученных классов выберем тот, у которого оценка минимальна и разобьем его. Так будем повторять до тех пор, пока не достигнем листа дерева. Т. е. пока не получим матрицу 0×0:

C [(1, 2); [−](a 1 , b 1); [−](a 2 , b 2); … [−](a k , b k)]

Где (каждое) −(x , y) означает, что матрица соответствует классу, не содержащему ребро (x , y) Удалив из обозначения матрицы элементы вида −(x , y), получим следующее:

(c 0 , d 0); (c 1 , d 1); … (c n , d n)

Вершина (5, 4) дерева будет соответствовать классу, содержащему ребра: (1, 2); (3, 1); (6, 5); (2, 6); (4, 3); (5, 4). Этот класс, очевидно, состоит из одного полного тура (1, 2, 6, 5, 4, 3, 1) со стоимостью = 36 (для полного тура его минимальная оценка равна точной стоимости)

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

Матрица, соответствующая классу туров, не содержащих ребро (1, 2), приведенная по второму столбцу, будет выглядеть так:

Она была получена из матрицы, соответствующей классу всех туров путем установки прочерка (обозначающего бесконечную стоимость перелета) вместо элемента (1, 2). Т.е. с 1,2 = ∞. Обозначим ее как C [−(1,2)]

Т. к. максимальная оценка нуля 3 (элемент 1,3) получаем, что оценка для ветви −(1,3) равна 38.

Вычеркивая первую строку и первый столбец, получим матрицу, приводимую на 1 по четвертой строке. То есть оценка ветви −(1,2)(1,3) становится равной 36. Дальнейшее ветвление будем продолжать уже с учетом найденного рекордного значения (36):

Таким образом, вершин не осталось, перебор завершен. А найденное в ходе него рекордное значение и соответствующий ему тур — решение задачи.

Удовлетворительных теоретических оценок алгоритма Литтла и ему подобных нет, но практика показывает, что на современных машинах они позволяют решать задачу коммивояжера с количеством вершин ≈ 100. Кроме того, алгоритмы типа ветвей и границ являются эффективными эвристическими процедурами. Если нет возможности доводить их до конца.

Пример 2. Задача о размыкании контуров

Тот же подход можно применить к задаче о размыкании контуров. Постановка задачи:

Пусть задан граф G = (V , E), каждой дуге (u , v) которого сопоставлено положительное число c (u , v) — вес этой дуги.

Требуется найти E 0 ⊂ E так, чтобы граф (V , E 0) не имел контуров и сумма весов дуг (из E 0) была максимальной.

Рассмотрим вспомогательную задачу (обозначим ее (E , E *)) аналогичную только что сформулированной, но с дополнительным параметром — множеством E * ⊂ E из которого дуги удалять нельзя (при этом будем требовать, чтобы в графе (V , E *) не было контуров).

Если имеется задача (E , E *) то возможно все множество ее решений разбить на два класса следующим образом.

Рассмотрим дугу (u , v) ∈ E \ E * такую, что в графе (V , E * ∪ (u , v)) нет контуров.

Тогда множество решений задачи можно разбить на два:

1. множество решений задачи (E \ (u , v), E *)
2. множество решений задачи (E , E* ∪ (u , v))

Исходная задача о размыкании контуров, очевидно, является задачей (E , Ø).

Введем теперь функцию est(E , E 0) следующим образом:

1. если граф (V , E) не содержит циклов, то est(E , E 0) = 0
2. иначе, пусть E cyc — цикл, тогда: est(E , E 0) = est(E \ E cyc , E 0) + c cyc , где c cyc = min{ c (u , v) | (u , v) ∈ E cyc \ E 0 } (т. е. мин. вес, которым можно разомкнуть этот цикл)

Несложно показать, что

V (E , E 0) ≥ est(E , E 0),

где v (E , E 0) — минимум суммы весов дуг, удаление которых из E \ E 0 размыкает все контуры графа.

Метод локальных улучшений ("локальный поиск")

Идея этого метода заключается в том, что для каждого решения экстремальной задачи x ∈ X определяется окрестность близких решений A (x) и на каждой итерации вычислительного процесса при заданном текущем решении x делается попытка найти в его окрестности решение, которое имело бы лучшее значение целевой функции. Если такое решение удается найти, оно само становится текущим решением, если нет — поиск заканчивается.

Более конкретно стратегия локального поиска такова:

• Начните с произвольного решения
• Для улучшения текущего решения примените к нему какое-либо преобразование из заданной совокупности преобразований. Это улучшенное решение становится текущим решением
• Повторяйте указанную процедуру до тех пор, пока ни одно из преобразований в заданной совокупности не позволит улучшить текущее решение

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

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

Рассмотрим точный алгоритм нахождения минимального остовного дерева в графе с помощью метода локального поиска. Локальные преобразования будут таковы: мы берем то или иное ребро, не относящееся к текущему остовному дереву и добавляем его к дереву (получая цикл), а затем убираем из этого цикла одно ребро (с наивысшей стоимостью). Это продолжается, пока все ребра вне дерева не будут иметь наивысшую стоимость среди всех ребер в цикле, который образуется при добавлении его к дереву (одна эта проверка требует времени O (| V || E |)). Этот алгоритм работает медленнее, чем алгоритмы Прима и Крускала, и служит примером нерационального использования локального поиска для не NP-полных задач.

Пример 2. Задача коммивояжера ("двойной выбор")

Простейшее преобразование, которым можно воспользоваться в симметричной задаче коммивояжера, является так называемый "двойной выбор" . Он заключается в том, что мы выбираем любые два ребра (например (a , b) и (c , d)), удаляем их и "перекоммутируем" соединявшиеся ими точки так, чтобы образовался новый маршрут. Если сумма стоимостей двух новых ребер оказалась меньше, чем двух старых, то мы нашли улучшенный маршрут.

Рассмотрим тот же граф, для которого мы строили остовное дерево. Выберем в качестве начального маршрута (a , b , c , d , e) и применим к нему "двойной выбор". Легко убедиться, что на рисунке "в" нельзя удалить ни одну пару ребер, выгодно заменив её другой.

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

Легко убедиться в том, что количество различных преобразований, которые нужно рассмотреть при k -выборе равно O (| V | k). Однако время, требуемое для получения какого-либо оптимального маршрута, может оказаться значительно больше.

На практике очень эффективным является "выбор с переменной глубиной". Он с большой вероятностью обеспечивает получение оптимального маршрута для | V | = 40 − 100.

Пример 3. Задача размещения блоков

Формулировка задачи одномерного размещения блоков: требуется упорядочить вершины неориентированного графа G = (V , E) с весами на ребрах c (u , v), пронумеровав их числами 1 … n так, чтобы минимизировать ∑ i , j = 1… n | i − j | c (v i , v j); n = | V |.

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

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

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

1. Произвести взаимную перестановку смежных блоков v i и v i +1 , если результирующий порядок имеет меньшую стоимость. Пусть

   L (j) = ∑ k =1… j −1 c (v k , v j);
   R (j) = ∑ k = j +1… n c (v k , v j).

   Улучшение можно выполнить, если

   L (i) − R (i) + R (i +1) − L (i +1) + 2 c (v i , v i +1) < 0

2. Взять блок v i и вставить его между некоторыми блоками v i и v i +1 при некоторых значениях i и j .
3. Выполнить взаимную перестановку двух блоков v i и v j .

Как и в задаче коммивояжера мы не в состоянии точно оценить время, необходимое для нахождения локального оптимума. Можно показать, что, если ограничиться преобразованием (1 ), времени O (| V |) будет достаточно, чтобы проверить, является ли выполняемое преобразование улучшающим, и вычислять L (i) и R (i). Для преобразований (2 ) и (3 ) это время увеличивается до O (| V | 2). Но это не есть оценка времени нахождения локального оптимума, так как каждое улучшение может создавать возможности для новых улучшений.

Приближенные и эвристические методы

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

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

Пример 1. Задача коммивояжера (деревянный алгоритм)

Рассмотрим три эвристических алгоритма, решающих симметричную задачу коммивояжера с неравенством треугольника с ошибкой не более чем в два раза (ρ = 2).

Первый из них, так называемый деревянный алгоритм, состоит в следующем: построим для нашего графа минимальное покрывающее дерево с помощью алгоритма Прима, а затем совершим обход дерева в порядке root-left-right , удаляя повторяющиеся вершины.

Время работы этого алгоритма равно Θ(E) = Θ(V 2).

Пример 1. Задача коммивояжера (жадный алгоритм и алгоритм Карга-Томпсона)

Самый очевидный алгоритм решения задачи коммивояжера — жадный: из текущего города иди в ближайший из тех, куда ещё не ходил. Если выполняется неравенство треугольника, нетрудно доказать, что этот алгоритм ошибается не более, чем в два раза. Трудоемкость этого алгоритма O (V 2).

Алгоритм Карга-Томпсона (эвристика ближайшей точки) чуть менее очевиден: сначала возьмем две ближайшие вершины (вырожденный тур), затем в цикле по всем ребрам уже построенного тура для каждого ребра (u , v) выберем из свободных вершин такую w , чтобы c (u , w) + c (w , v) − c (u , v) было минимальным и включим w в тур между u и v . Для этого способа также ρ = 2, однако его трудоемкость составляет уже O (V 3).

Пример 2. Задача о вершинном покрытии

Напомним, что вершинным покрытием неориентированного графа G =(V , E) мы называем некоторое семейство его вершин V ′ с таким свойством: для всякого ребра (u , v) графа G хотя бы один из его концов u или v содержится в V ′. Размером вершинного покрытия считаем количество входящих в него вершин.

Задача о вершинном покрытии состоит в нахождении вершинного покрытия минимального размера. Эта задача NP-трудна, однако приведенный ниже простой алгоритм решает её с ошибкой не более, чем в два раза.

Пусть С — это уже построенная часть вершинного покрытия, а E ′ содержит непокрытые ребра графа. На каждом шаге мы берем ребро из E ′ и добавляем его концы u и v в C , а из E ′ изымаем все ребра имеющие своим концом u или v . И так пока множество E ′ не станет пустым. Время работы этого алгоритма есть O (E).

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

Дано конечно множество X и семейство его подмножеств F . При этом:

X =∪ S ∈ F S

Мы ищем минимальное число подмножеств из F , которые вместе покрывают множество X , т. е. семейство С наименьшей мощности, для которого:

X =∪ S ∈ C S

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

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

Так происходит, пока U не пусто. Трудоемкость алгоритма составляет O (| X |·| F |·min(| X |,| F |)).

Размер покрытия, даваемого этим алгоритмом, превосходит минимально возможный не более чем в H (max{| S |: S ∈ F }) раз (где H (d) — сумма первых d членов гармонического ряда) или, что тоже самое, в (ln| X | + 1) раз.

Псевдополиномиальные алгоритмы

Такие алгоритмы часто получаются при применении динамического программирования к NP-полным задачам. У таких алгоритмов экспоненциальная зависимость времени работы (и памяти компьютера) от длины входа, однако существует полиномиальная зависимость от некоторого числа (чисел) на входе задачи. Такие алгоритмы очень полезны, т. к. позволяют точно решать задачи с маленькими числами и приближенно — для больших чисел, каким-либо образом преобразованных в маленькие.

Пример 1. Задача о суммах подмножеств ("табличный" алгоритм)

Пусть задана пара (S , t), где S = { x 1 , x 2 , …, x n } представляет собой множество положительных целых чисел, а t — положительное целое число. Требуется отыскать среди подмножеств множества S , сумма которых не превосходит t , такое, у которого сумма ближе всего к t .

Пусть | S | = n . Обозначим (k , w) — задачу, в которой имеется k первых чисел из S и нужно набрать сумму w . Таким образом исходная задача — это задача (n , t).

Для решения задачи построим таблицу T [ n , t + 1], в клетку T [ i , j ] которой будем записывать оптимальное решение задачи (i , j).

Первый столбец заполним нулями. Первую строку заполним сначала нулями, а начиная с клетки (1, x 1) — числами x 1 . Клетку T [ i , j ] (i , j > 1) будем заполнять по правилу:

1. Если j − x i > 0, то y:= T [ i − 1, j − x i ], иначе y:= 0;
2. T [ i , j ] := max(T [ i − 1, j ], y + x i)

S = {3, 5, 7, 9, 11} t = 13;

Таблица примет такой вид. Ответ: нет подмножества весом 13, ближе всего снизу 12.

Условие (2) говорит о том, что оптимальная сумма может достигаться либо без использования x i (T [ i − 1, j ]), либо если x i входит в сумму (y + x i). В этом случае его надо прибавить к решению задачи (i − 1, j − x i), что и сохраняется в переменной y в условии (1). Из получившейся таблицы можно узнать и состав оптимальной суммы.

Трудоемкость этого алгоритма составляет O (n t) операций. Таким образом, если t будет велико, можно будет все числа поделить, к примеру, на 10, округлить и получить приближенный алгоритм.

Пример 2. Задача о суммах подмножеств ("списковый" алгоритм)

Пусть L — набор чисел, а x — некоторое число, тогда через L + x обозначим набор чисел, который получится, если ко всем элементам L прибавить x . В этом алгоритме также используется тот факт, что x i может как входить в сумму, так и не входить, то есть:

L i = L i −1 ∪ (L i −1 + x i)

Выкидывая из списка элементы, большие t получим L n — упорядоченный список всех возможных удовлетворяющих нас сумм подмножеств S . Остается взять максимальный (последний) элемент, чтобы получить решение задачи. Список L n может содержать до 2 n элементов (т. е. алгоритм экспоненциален), однако, т.к. все элементы различны, их не может быть более t . Налицо псевдополиномиальность.

Схемы приближения

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

Мы рассмотрим две схемы приближения для задачи о сумме подмножеств. Одна из них получается из "спискового" алгоритма, а другая называется алгоритмом Джонсона.

Пример 1. Задача о суммах подмножеств (полностью полиномиальная схема приближения)

Такая схема получается из "спискового" алгоритма, если хранить список L в сокращенной форме. Список L ′ называется δ -сокращением списка L , если L ′ является частью L и

∀ y ∈ L ∃ z ∈ L ′: z ≤ y , (y − z) ⁄ y ≤ δ

Например для δ = 0,1 и L = <10, 11, 12, 15, 20, 21, 22, 23, 24, 29> список L ′ = <10, 12, 15, 20, 23, 29> является δ -сокращением. Сокращение упорядоченного списка из m элементов требует Θ (m) операций. Таким образом, можно доказать, что "списковый" алгоритм, хранящий вместо полного списка сокращенный является полностью полиномиальной схемой приближения.

Пример 2. Задача о суммах подмножеств (алгоритм Джонсона)

Алгоритм, кроме множества S и числа t принимает на вход целочисленный параметр m > 2. Назовем i -е число большим, если x i > t ⁄(m +1). Описание алгоритма:

1. Перебрать все подмножества из больших чисел и найти множество больших чисел с суммой t ′: t ′ < t , Δ = t − t ′ min
2. Если Δ = 0, алгоритм закончен.
3. Перебрать все малые числа в порядке убывания. Если очередное x i ≤ Δ , то t ′:= t ′ + x i , Δ := Δ − x i ;
4. Когда перебор по малым числам закончен, выдать t ′ в качестве ответа.

Пусть k — количество больших чисел. Тогда можно доказать, что количество подходящих нам подмножеств из больших чисел составляет O (k m) ≤ O (n m). Таким образом, перебор имеет полиномиальную, возрастающую с m сложность. Корме того, можно показать, что:

T ′⁄ t ≥ 1 − 1 ⁄ (m + 1) 1 − 1 ⁄ (m + 1) ≤ t ′⁄ t* ≤ 1

то есть относительная погрешность ε = 1⁄ (m +1). Таким образом, эта схема приближения является полиномиальной, но не является полностью полиномиальной.

Метод случайного поиска

Обычно выбор решения можно представить последовательностью выборов. Если делать эти выборы с помощью какого-либо случайного механизма, то решение находится очень быстро, так что можно находить решение многократно и запоминать "рекорд", т. е. наилучшее из встретившихся решений. Этот наивный подход существенно улучшается, когда удается учесть в случайном механизме перспективность тех или иных выборов, т. е. комбинировать случайный поиск с эвристическим методом и методом локального поиска. Такие методы применяются, например, при составлении расписаний для Аэрофлота.

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

Пожалуйста. На запрос "метод случайного поиска" поисковик Google анонсирует более 300000 ссылок. Этой информации должно хватить..........

Благодарю за статью, разобрался с алгоритмом Литтла. Хотел запомнить сайт и был удивлен, увидев домен родного университета:)

Про запрет переходов выше замечено верно - хотелось бы видеть здесь пояснения.

Спасибо за понятное разъяснение алгоритма Литтла. Но не учтена важная деталь: при выборе следующего ребра нужно учитывать, чтобы путь из набора ребер последовательно охватывал все точки. Так как ребра добавляем в случайном порядке, то приходится отслеживать наличие микроциклов (например выбрали ребро 1,0 - значит 0, 1 уже нельзя выбирать, или выбрали 0,1 и 1,2 - тогда нельзя выбирать 2,0 и 2,1 и т.д.), что отследить не так уж и просто. Я реализовал алгоритм на C#, циклы отслеживал с помощью специального класса, который содержал набор микроциклов и вычеркивал запрещенные ребра при добавлении в него новых и ребер и восстанавливал ребра при удалении ребер.

Реализация алгоритма оказалась очень сложна на практике, а его отладка просто ад. Код занял 512 строк. 20 точек обрабатывает за 0.1 - 10 секунд - длительность сильно зависит от входного набора. Большее количество уже за адекватное время не решает. Простейший переборщик у меня находит решение для 13 вершин за 1 секунду.

Если нужна реализация алгоритма на C# - пишите на почту [email protected].

Решение задачи коммивояжера методом ветвей и границ (алгоритм Литтла)

http://igorvn.ucoz.ru/load/kursovye/kommivojazher/2-1-0-15

Метод Литла работает только на небольшом количестве точек поэтому во всех примерах их не более 10 Начиная 15 точек он дает приближенный результат 1-2 % больше минимального и это заложено в порядке определения каждого хода (редукции) непонятно на каком основании это делается.Ведь формально мы получаем другую матрицу.

Высылаю вам "Русский метод" для подтверждения моего комментария.

Благодарим. Не сомневаемся в Вашей добросовестности и компетентности. Но файлы *.doc мы не размещаем. Если выложите его содержимое в общедоступное место со статусом постоянного хранения и включите ссылку в текст своего нового комментария, опубликуем для всеобщего обозрения.

Всем, кто хочет узнать про все теоретические ошибки метода Литтла, прошу сначала объяснить себе, что такое редукция и на каком это математическом основании оно проводится. Кроме того, Русский метод, разработанный мной, могу выслать совершенно бесплатно. Мой email: [email protected]

Метод ветвей и границ -- один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.

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

Алгоритм решения:

Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных. Пусть им является план X 0 . Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи и

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

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

Найдем решение задач линейного программирования (I) и (II). Очевидно, здесь возможен один из следующих четырех случаев:

• 1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.
• 2. Одна из задач неразрешима, а другая имеет оптимальный план, среди компонент которого есть дробные числа. Тогда рассматриваем вторую задачу и в ее оптимальном плане выбираем одну из компонент, значение которой равно дробному числу, и строим две задачи, аналогичные задачам (I) и (II).
• 3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции на этих планах и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и он вместе со значением целевой функции на нем дает искомое решение.

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

4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда вычисляем значение целевой функции на данных оптимальных планах и рассматриваем ту из задач, для которой значение целевой функции является наибольшим. В оптимальном плане этой задачи выбираем одну из компонент, значение которой является дробным числом, и строим две задачи, аналогичные (I) и (II).

Таким образом, описанный выше итерационный процесс может быть представлен в виде некоторого дерева, на котором исходная вершина отвечает оптимальному плану Х 0 задачи (1)-(3), а каждая соединенная с ней ветвью вершина отвечает оптимальным планам задач (I) и (II). Каждая из этих вершин имеет свои ветвления. При этом на каждом шаге выбирается та вершина, для которой значение функции является наибольшим. Если на некотором шаге будет получен план, имеющий целочисленные компоненты, и значение функции на нем окажется больше или равно, чем значение функции в других возможных для ветвления вершинах, то данный план является оптимальным планом исходной задачи целочисленного программирования и значение целевой функции на нем является максимальным.

Итак, процесс нахождения решения задачи целочисленного программирования (1)-(4) методом ветвей и границ включает следующие основные этапы:

• 1. Находят решение задачи линейного программирования (1)-(3).
• 2. Составляют дополнительные ограничения для одной из переменных, значение которой в оптимальном плане задачи (1)-(3) является дробным числом.
• 3. Находят решение задач (I) и (II), которые получаются из задачи (1)-(3) в результате присоединения дополнительных ограничений.
• 4. В случае необходимости составляют дополнительные ограничения для переменной, значение которой является дробным, формулируют задачи, аналогичные задачам (I) и (II), и находят их решение. Итерационный процесс продолжают до тех пор, пока не будет найдена вершина, соответствующая целочисленному плану задачи (1)-(3) и такая, что значение функции в этой вершине больше или равно значению функции в других возможных для ветвления вершинах.

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

целочисленный программирование задача коммивояжер ранец

Метод ветвей и границ − один из комбинаторных методов. В отличие от метода Гомори применим как к полностью, так и частично целочисленнным задачам.

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

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

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

или
, или

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

Очевидно, что возможен один из следующих четырех случаев.

Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции на нем и дают решение исходной задачи.

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

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

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

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

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

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

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

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

Пример . Найти методом ветвей и границ решение задачи целочисленного программирования

Решение . Находим оптимальный план сформулированной задачи симплексным методом без учета целочисленности переменных, а именно решаем задачу 1.

Оптимальный план задачи 1 линейного программирования

при
.

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

Для поиска целочисленного оптимального решения разделим интервал изменения переменной x 1 на две области, а именно x 1  и x 1 = 10 , и разобьем заданную задачу на две новые задачи.

Нижняя граница линейной функции не изменилась: Z 0 = 0. Решаем одну из задач, например задачу 3, симплексным методом. Получаем, что условия задачи противоречивы.

Решаем задачу 2 симплексным методом. Получаем оптимальный целочисленный план поставленной задачи 2, который является также оптимальным планом задачи 1:

при
.

Таким образом, в результате одного ветвления задачи было найдено ее оптимальное решение.

Введение

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

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

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

1. Историческая справка

Впервые метод ветвей и границ был предложен Лендом и Дойгом в 1960 для решения общей задачи целочисленного линейного программирования. Интерес к этому методу и фактически его «второе рождение» связано с работой Литтла, Мурти, Суини и Кэрела, посвященной задаче коммивояжера. Начиная с этого момента, появилось большое число работ, посвященных методу ветвей и границ и различным его модификациям. Столь большой успех объясняется тем, что авторы первыми обратили внимание на широту возможностей метода, отметили важность использования специфики задачи и сами воспользовались спецификой задачи коммивояжера.

Этот метод является наиболее общим среди всех методов дискретного программирования и не имеет принципиальных ограничений по применению. Алгоритм метода ветвей и границ представляет собой эффективную процедуру перебора всех целочисленных допустимых решений.

Метод ветвей и границ - один из комбинаторных методов. Его суть заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.

2. Описание метода

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

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

При применении метода ветвей и границ к каждой конкретной задаче в первую очередь должны быть определены две важнейшие его процедуры: 1) ветвления множества возможных решений; 2) вычисления нижних и верхних оценок целевой функции.

2.1 Правила ветвления

В зависимости от особенностей задачи для организации ветвления обычно используется один из двух способов:

1. ветвление множества допустимых решений исходной задачи D;

2. ветвление множества D" получаемого из D путем снятия условия целочисленности на переменные.

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

Второй способ ветвления - более универсальный, чем первый. Для осуществления ветвления некоторой области D i " этим способом на D i " решается оптимизационная задача с целевой функцией исходной задачи и действительными переменными.

Ветвление осуществляется, если в оптимальном решении значение хотя бы одной целочисленной по исходной постановке задача переменной не является целочисленным. Среди этих переменных выбирается одна, например j - я. Обозначим ее значение в найденном оптимальном решении x 0 [j]. Говорят, что ветвление осуществляется по переменной x[j]. Область D i " разделяется на две подобласти D i1 " и D i2 " следующим образом:

где ] - целая часть значения x 0 [j]

На рис. 2 условно дана геометрическая интерпретация такого ветвления.

Рис. 2. Геометрическая интерпретация ветвления

Видно, что при этом из области D i " удаляется часть между плоскостями вновь введенных ограничений. Так как переменная x[j] по условиям области допустимых решений исходной задачи - целочисленная, то из подобласти допустимых решений исходной задачи. D i (D i D i ") при таком изъятии не исключается ни одного решения.

2.2 Формирование нижних и верхних оценок целевой функции

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

где х - вектор оптимизационных переменных, среди которых часть действительных, а часть целочисленных; f(x) - в общем случае нелинейная целевая функция; D - область допустимых решений задачи дискретного программирования общего вида.

Нижние оценки целевой дикции в зависимости от выбранного способа ветвления могут определяться либо для подобластей D i D либо для подобластей D i " D" (D i " и D" получены из соответствующих множеств D i и D путем снятия условий целочисленности на дискретные переменные).
Нижней оценкой целевой функции f(x) на множестве D i (или D i ") будем называть величину:

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

На рис. 3 показан такой идеальный случай, когда нижние оценки (соединены ломаной штрихпунктирной линией) правильно отражают соотношения между действительными минимальными значениями f(x) (соединены штриховой линией) для четырех подмножеств допустимых решений D 1 , D 2 , D 3 , D 4 .

Один из универсальных способов вычисления нижних оценок заключается в решении следующей задачи:

Определенная таким образом о i является нижней оценкой f(x) на D i (или D i "), так как D i D i ".

Если при решении задачи (4) установлено, что, то для общности будем полагать, что.

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

Совместно с нижней оценкой в методе ветвей и границ используются верхние оценки f(x). Как правило, вычисляют лишь одно значение верхней оценки, которую определяют как значение целевой функции для лучшего найденного допустимого решения исходной задачи. Такую верхнюю оценку иногда называют рекордом. Если же можно для решаемой задачи достаточно просто и точно получить верхние оценки f(x) для отдельных множеств, образующихся при ветвлении, то их необходимо использовать в методе для уменьшения вычислительной сложности процесса решения. При использовании единой верхней оценки ее первоначальное значение обычно полагают равным бесконечности (), если, конечно, из априорных соображений не известно ни одного допустимого решения исходной задачи. При нахождении первого допустимого решения:

Затем при определении более лучшего допустимого решения верхнюю оценку корректируют:

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

2.3 Алгоритм метода ветвей и границ

Основные правила алгоритма могут быть сформулированы следующим образом:

1. Ветвлению в первую очередь подвергается подмножество с номером, которому соответствует наименьшее значение нижней оценки целевой функции (I - это множество номеров всех подмножеств, (или), находящихся на концах ветвей и ветвление которых еще не прекращено). Если реализуется изложенный выше способ ветвления множеств, то может возникнуть неоднозначность относительно выбора компоненты, по которой необходимо осуществлять очередной шаг ветвления. К сожалению, вопрос о «наилучшем» способе такого выбора с общих позиций пока не решен, и поэтому в конкретных задачах используются некоторые эвристические правила.

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

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

4. Если, где, то выполняются условия оптимальности для найденного к этому моменту лучшего допустимого решения. Обоснование такое же, как и пункта 2 настоящих правил.

5. После нахождения хотя бы одного допустимого решения исходной задачи может быть рассмотрена возможность остановки работы алгоритма с оценкой близости лучшего из полученных допустимых решений к оптимальному (по значению целевой функции):

2.4 Решение задачи методом ветвей и границ

Целые .

Первоначально находим симплексным методом или методом искусственного базиса оптимальный план задачи без учета целочисленности переменных.

Если среди компонент этого плана нет дробных чисел, то тем самым найдено искомое решение данной задачи.

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

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

Пусть переменная в плане - дробное число. Тогда в оптимальном плане ее значение будет по крайней мере либо меньше или равно ближайшему меньшему целому числу, либо больше или равно ближайшему большему целому числу.

Определяя эти числа, находим симплексным методом решение двух задач линейного программирования

- целые .

Целые .

Возможны четыре случая при решении этой пары задач:

1. Одна из задач неразрешима, а другая имеет целочисленный оптимальный план. Тогда этот план и значение целевой функции дают решение исходной задачи.

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

3. Обе задачи разрешимы. Одна из задач имеет оптимальный целочисленный план, а в оптимальном плане другой задачи есть дробные числа. Тогда вычисляем значения целевой функции от планов и сравниваем их между собой. Если на целочисленном оптимальном плане значение целевой функции больше или равно ее значению на плане, среди компонент которого есть дробные числа, то данный целочисленный план является оптимальным для исходной задачи и дает искомое решение.

4. Обе задачи разрешимы, и среди оптимальных планов обеих задач есть дробные числа. Тогда рассматриваем ту из задач, для которой значение целевой функции является наибольшим. И строим две задачи.

Таким образом, при решении задачи получаем схему:

1. Находим решение задачи линейного программирования без учета целочисленности.

2. Составляет дополнительные ограничения на дробную компоненту плана.

3. Находим решение двух задач с ограничениями на компоненту.

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

Пример

Найдем решение задачи

Целые .

Решение. Находим решение без учет целочисленности задачи симплексным методом.

Рассмотрим следующую пару задач:

Задача №1

изадача №2

Первая задача имеет оптимальный план

вторая - неразрешима.

Проверяем на целочисленность план первой задачи. Это условие не выполняется, поэтому строим следующие задачи:

Задача №1.1

и задача №1.2

Задача №1.2 неразрешима, а задача №1.1 имеет оптимальный план, на котором значение целевой функции.

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

3. Решение задачи коммивояжера методом ветвей и границ

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

3.1 Постановка задачи

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

Очевидно, в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес Ґ, считая, что Ґ - это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом Ґ можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе.

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

пусть - полный ориентированный граф и - весовая функция; найти простой остовный ориентированный цикл («цикл коммивояжера») минимального веса.

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

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

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

Слова привести матрицу по строкам означают, что все строки матрицы приводятся. Аналогичный смысл имеют слова привести матрицу по столбцам.

Наконец, слова привести матрицу означают, что матрица сначала приводится по строкам, а потом приводится по столбцам.

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

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

Первый шаг . Фиксируем множество всех обходов коммивояжера (т.е. всех простых ориентированных остовных циклов). Поскольку граф - полный, это множество заведомо не пусто. Сопоставим ему число, которое будет играть роль значения на этом множестве оценочной функции: это число равно сумме констант приведения данной матрицы весов ребер графа. Если множество всех обходов коммивояжера обозначить через G, то сумму констант приведения матрицы весов обозначим через j(G). Приведенную матрицу весов данного графа следует запомнить; обозначим ее через M 1 ; таким образом, итог первого шага:

множеству G всех обходов коммивояжера сопоставлено чис-ло j(G) и матрица M 1 .

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

Сопоставим множеству следующую матрицу M 1,1: в матрице M 1 заменим на Ґ число в клетке. Затем в полученной матрице вычеркнем строку номер i и столбец номер j, причем у оставшихся строк и столбцов сохраним их исходные номера. Наконец, приведем эту последнюю матрицу и запомним сумму констант приведения. Полученная приведенная матрица и будет матрицей M 1,1 ; только что запомненную сумму констант приведения прибавим к j(G) и результат, обозначаемый в дальнейшем через j(), сопоставим множеству.

Теперь множеству тоже сопоставим некую матрицу M 1,2 . Для этого в матрице M 1 заменим на Ґ число в клетке и полученную в результате матрицу приведем. Сумму констант приведения запомним, а полученную матрицу обозначим через M 1,2 . Прибавим запомненную сумму констант приведения к числу j(G) и полученное число, обозначаемое в дальнейшем через j(), сопоставим множеству.

Теперь выберем между множествами и то, на котором минимальна функция j (т.е. то из множеств, которому соответствует меньшее из чисел j() и j()).

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

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

К выбранному множеству с сопоставленными ему матрицей и числом j повторим все то же самое и так далее, пока это возможно.

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

После этого осуществляется улучшение рекорда вплоть до получения окончательного ответа.

3.2 Условие задачи

Студенту Иванову поручили разнести некоторые важные документы из 12-ого корпуса. Но, как назло, у него на это очень мало времени, да и еще надо вернуться обратно. Нужно найти кротчайший путь. Расстояния между объектами даны в таблице

3.3 Математическая модель задачи

Для решения задачи присвоим каждому пункту маршрута определенный номер: 12-ый корпус - 1, Белый дом - 2, КРК «Премьер» - 3, Администрация - 4 и 5-ый корпус - 5. Соответственно общее количество пунктов. Далее введем альтернативных переменных, принимающих значение 0, если переход из i-того пункта в j-тый не входит в маршрут и 1 в противном случае. Условия прибытия в каждый пункт и выхода из каждого пункта только по одному разу выражаются равенствами (8) и (9).

Для обеспечения непрерывности маршрута вводятся дополнительно n переменных и дополнительных ограничений (10).

Суммарная протяженность маршрута F , которую необходимо минимизировать, запишется в следующем виде:

В нашем случае эти условия запишутся в следующем виде:

3.4 Решение задачи методом ветвей и границ

задача коммивояжер ветвь граница

1) Анализ множества D.

Найдем оценку снизу Н . Для этого определяем матрицу минимальных расстояний по строкам (1 где расстояние минимально в строке).

Аналогично определяем матрицу минимальных расстояний по столбцам.

Выберем начальный план: . Тогда верхняя оценка:

Очевидно, что, где означает переход из первого пункта в j-тый. Рассмотрим эти подмножества по порядку.

2) Анализ подмножества D 12 .

3) Анализ подмножества D 13 .

4) Анализ подмножества D 14 .

5) Анализ подмножества D 15 .

6) Отсев неперспективных подмножеств.

Подмножества D 13 и D 15 неперспективные. Т.к. , но, то далее будем рассматривать подмножество D 14 .

7) Анализ подмножества D 142 .

8) Анализ подмножества D 143 .

9) Анализ подмножества D 145 .

10) Отсев неперспективных подмножеств

Подмножество D 143 неперспективное. Т.к. , но, то далее будем рассматривать подмножество D 145 .

11) Анализ подмножества D 1452 .

12) Анализ подмножества D 1453 .

Оптимальное решение: .

Таким образом, маршрут студента: 12-ый корпус - Администрация - 5-ый корпус - Белый дом - КРК Премьер - 12-ый корпус.

Список литературы

1. Абрамов Л.А., Капустин В.Ф. Математическое программирование. - Л.: Изд-во ЛГУ, 1981. -328 с.

2. Алексеев О.Г. Комплексное применение методов дискретной оптимизации. - М.: Наука, 1987. -294 с.

3. Корбут А.А., Финкелгейн Ю.Ю. Дискретное программирование. М.: Наука. 1969. -240 с

4. Кузнецов Ю.Н. и др. Математическое программирование: Учебное пособие. - 2-е изд., перераб и доп. - М.: Высшая школа, 1980. -300 с.

5. Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985. -213 с.

Подобные документы

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

задача , добавлен 24.07.2009


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

контрольная работа , добавлен 07.06.2011


Методы решения задачи коммивояжера. Математическая модель задачи коммивояжера. Алгоритм Литтла для нахождения минимального гамильтонова контура для графа с n вершинами. Решение задачи коммивояжера с помощью алгоритма Крускала и "деревянного" алгоритма.

курсовая работа , добавлен 30.04.2011


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

курсовая работа , добавлен 18.06.2011


Математическая модель задачи. Решение транспортной задачи методом потенциалов. Значение целевой функции. Система, состоящая из 7 уравнений с 8-ю неизвестными. Решение задач графическим методом. Выделение полуплоскости, соответствующей неравенству.

контрольная работа , добавлен 12.06.2011


Теория динамического программирования. Понятие об оптимальной подструктуре. Независимое и полностью зависимое множество вершин. Задача о поиске максимального независимого множества в дереве. Алгоритм Брона-Кербоша как метод ветвей, границ для поиска клик.

реферат , добавлен 09.10.2012


Решение двойственной задачи с помощью первой основной теоремы теории двойственности, графическим и симплексным методом. Математическая модель транспортной задачи, расчет опорного плана перевозок методами северо-западного угла и минимального элемента.

контрольная работа , добавлен 27.11.2011


Постановка задачи коммивояжера и основные алгоритмы решения. Маршруты и пути. Понятия транспортной сети. Понятие увеличивающая дуга, цепь, разрез. Алгоритм Флойда-Уоршелл. Решение задачи аналитическим методом. Создание приложения для решения задачи.

курсовая работа , добавлен 08.10.2015


Решение первой задачи, уравнения Пуассона, функция Грина. Краевые задачи для уравнения Лапласа. Постановка краевых задач. Функции Грина для задачи Дирихле: трехмерный и двумерный случай. Решение задачи Неймана с помощью функции Грина, реализация на ЭВМ.

курсовая работа , добавлен 25.11.2011


Последовательность решения линейной краевой задачи. Особенности метода прогонки. Алгоритм метода конечных разностей: построение сетки в заданной области, замена дифференциального оператора. Решение СЛАУ методом Гаусса, конечно-разностные уравнения.

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

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

Для каждой конкретной задачи целочисленного программирования (другими словами, дискретной оптимизации) метод ветвей и границ реализуется по-своему. Есть много модификаций этого метода.

Рассмотрим реализацию метода ветвей и границ для задачи коммивояжёра и задачи о рюкзаке.

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

Пример.

Пусть в задаче коммивояжера задана следующая матрица стоимостей переездов

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

.

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

,

каждая строка и столбец, которой содержит хотя бы один нуль. Такая матрица называется приведенной по строкам и столбцам.

Суммируя элементы и , получим константу приведения:

.

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

.

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

Разбиваем множество всех допустимых маршрутов на два подмножества:

– подмножество, содержащее дугу ;

– подмножество, не содержащее дугу

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