Введение

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

Если не оговорено дополнительно, то далее будут использоваться следующие обозначения:

– множество целых неотрицательных чисел;

– множество n-мерных неотрицательных целочисленных векторов;

– множество вещественных чисел;

– множество n-мерных вещественных векторов

– множество n-мерных булевых векторов

– мощность множества ;

– целая часть числа ;

– минимальное целое число, которое не меньше ;

– оптимальное решение;

∎ – конец доказательства.

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

Определение 1. Графом называется пара множеств и , где – множество вершин, а – множество ребер графа. Для изображения вершины, как правило, используется точка, а для изображения ребра – отрезок линии между двумя точками. Упорядоченная пара вершин определяет дугу и изображается стрелкой, которая заканчивается в конечной вершине дуги.

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

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

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

Определение 5. Граф, каждому ребру которого приписано число – «вес», называется взвешенным. Сумма весов ребер, входящих в подграф, называется весом подграфа.

Определение 6. Количество символов в стандартном (двоичном) представлении данных индивидуальной задачи назовем длиной входа и обозначим

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

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

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

В теории вычислительной сложности принято рассматривать задачи распознавания (свойств), то есть задачи, в которых возможным ответом является«Да» или «Нет». Например, правда ли, что заданный граф является деревом? Среди задач распознавания принято выделять классы P и NP. Напомним, что класс P состоит из задач распознавания, разрешимых за полиномиальное время. Класс NP является более широким. Он включает в себя все задачи распознавания, в которых ответ «Да» может быть проверен за полиномиальное время. Задача принадлежит этому классу, если, даже не умея ее решать, можно «легко» проверить ответ, подглядев его или найдя в Интернете. При этом достаточно уметь проверять только ответ «Да». Иногда проверка ответа «Да» может быть легче или сложнее проверки ответа «Нет». Рассмотрим задачу о гамильтоновости графа: задан простой неориентированный граф, требуется узнать, содержит ли он гамильтонов цикл? Покажем, что эта задача принадлежит классу NP. Предположим, что граф действительно гамильтонов, и кто-то подсказал нам ответ, указав один из таких циклов. Можно ли проверить эту подсказку за полиномиальное время? Для этого нужно проверить, что указанный набор ребер образует простой цикл, и он покрывает все вершины. Очевидно, что это «легко» сделать и, следовательно, задача принадлежит классу NP. Заметим, что ответ «Нет» проверить здесь куда труднее. Говорят, что задача распознавания принадлежит классу co-NP, если ответ «Нет» можно проверить за полиномиальное время. Легко показать, что следующая задача принадлежит классу co-NP. Задан простой неориентированный граф, правда ли, что он не является гамильтоновым? Ответ «Нет» означает гамильтоновость графа, а это можно легко проверить.

В классе P можно проверить с полиномиальной трудоемкостью любой ответ, и, значит, P  NP. Доказать или опровергнуть обратное включение пока никому не удается. На сегодняшний день это одна из центральных проблем математики – «задача тысячелетия» (http://www.claymath.org/millennium/). За ее решение Американское математическое общество обещает приз – миллион долларов.

Многолетние интенсивные исследования подсказывают, что P ≠ NP. Косвенным доказательством этой гипотезы служит тот факт, что в классе NP обнаружены так называемые NP-полные задачи.

Определение 8. Задачу из класса NP называют NP-полной, если существование полиномиального алгоритма для ее решения влечет существование полиномиальных алгоритмов для всех задач из класса NP.

К настоящему времени известно огромное количество NP-полных задач [7, 17]. Однако ни для одной из них не удалось разработать точный полиномиальный алгоритм.

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

Задача из класса NP может быть решена экспоненциальным алгоритмом, который просто перебирает всех потенциальных кандидатов. Мы предполагаем, что их размер ограничен полиномом от размера входа. Оказывается, что бывают задачи, которые не решаются вообще никаким алгоритмом (ни полиномиальным, ни экспоненциальным, ни ещё более долго работающим); их называют неразрешимыми (unsolvable) [38].