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

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

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

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

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

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

Приведем еще один пример, когда задача синтеза допустимого решения по вычислительной сложности оказывается соизмеримой с задачей построения оптимального решения. Допустим, мы имеем алгоритм А _Ц синтеза допустимого решения для задачи целочисленного линейного программирования (ЦЛП); в случае отсутствия в рассматриваемой задаче ЦЛП допустимых решений, алгоритм дает ответ «Æ». Пусть ZC – произвольная индивидуальная задача ЦЛП, оптимальное значение критерия которой принадлежит отрезку [ А, В ], числа А и В – целые; для определенности считаем, что ZC – задача максимизации, ее критерий обозначаем L(Х). Далее через ZC [ P, Q ] будем обозначать задачу, получаемую из исходной задачи добавлением линейных ограничений P ≤ L (Х) ≤ Q. Пусть С ⁰ – ближайшая к середине отрезка [А, В] его целочисленная точка. Применением алгоритма А_ц строим допустимое решение задачи ZC[С⁰, В]. Если такого решения не существует, то оптимальное значение критерия за-дачи ZC лежит на отрезке [ А, С⁰ – 1]; если решение имеется, обозначим его Х⁰, то оптимальное значение критерия задачи ZC лежит на отрезке [ L (Х⁰), В ]. И в том, и в другом случае нам удается уменьшить длину отрезка, в котором локализовано искомое оптимальное значение критерия, не менее, чем в два раза. Далее находим целочисленную точку С ¹, ближайшую к середине полученного отрезка локализации, и применением алгоритма А _Ц будем строить допустимое решение полученной задачи ZC [ С ¹, С ⁰ – 1] или ZC [ С ¹, В ]. Так определяется итерационный процесс, на каждом шаге которого длина отрезка, содержащего искомое оптимальное значение критерия, уменьшается не менее чем в два раза. Выполнив не более log₂(В – А) итераций, мы определим, что искомое значение критерия принадлежит некоторому отрезку единичной длины [ h, h + 1]. Далее, применяя алгоритм А _Ц к задачам ZC [ h +1, h +1] и ZC [ h, h ], а, возможно, только к первой из них, мы найдем оптимальное решение исходной за-дачи ZC. Задача ЦЛП относится к числу NP- трудных, ибо таковым является ее частный случай – классическая задача о ранце. Из гипотезы Р ≠ NP в предположении, что для любой задачи ЦЛП достаточно просто найти отрезок локализации оптимального значения критерия длины не более чем экспоненциально зависящей от размера входной информации, вытекает, что алгоритм синтеза допустимого решения задачи ЦЛП не может иметь полиномиальной верхней оценки числа выполняемых элементарных операций.

Изложенное показывает целесообразность разделения задач дискретной оптимизации на два класса: К ₁ – задачи, для которых допустимые решения строить относительно легко (есть полиномиальные алгоритмы синтеза); К ₂ – задачи, для которых допустимые решения строить трудно (нет полиномиальных алгоритмов синтеза). Этот простой вывод для практики оказывается важным. Перспективным следует считать создание допустимых и эвристических алгоритмов для задач класса К ₁. Задачи класса К ₂ значительно сложнее, в них поиск приближенных решений по трудности сравним с поиском оптимальных планов.

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

Применяя к определяемой (n × n)-матрицей A = { a_ij } классической задаче о назначениях (КЗН)

жадный алгоритм, мы на первом шаге находим в матрице А наибольший элемент a_ij и реализуем закрепление исполнителя i за работой R_j; далее в матрице А', получаемой из А вычеркиванием элементов i -ой строки и j -го столбца вновь находим максимальный элемент и реализуем закрепление определяемого этим элементом исполнителя за соответствующей работой, и т.д. Решая жадным алгоритмом задачу коммивояжера, мы на каждом шаге осуществляем переход в ближайший из возможных городов. При синтезе жадным алгоритмом решения классической задачи о ранце упорядочиваем предметы по убыванию их стоимостей (при одинаковой стоимости – по возрастанию весов) и в полученном порядке помещаем, если это позволяет сделать весовое ограничение, в ранец.

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

Рассмотрим класс К* дискретных оптимизационных задач, определяемых следующим образом. Задано конечное множество М, некоторое семейство его подмножеств I и принимающая только неотрицательные значения функция f (x), которая каждому элементу х из М ставит в соответствие его «вес» f (x). Функцию f (x) именуем весовой функцией. Весом произвольного подмножества Х множества М называем сумму весов входящих в Х элементов. В семействе I требуется найти подмножество наибольшего веса.

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

Жадный алгоритм для описанной общей модели определяем следующим образом:

1. Полагаем, что W – пустое множество. Элементы множества М упорядочиваем (нумеруем) по убыванию их весов, (m_i – i -й по полученному порядку элемент множества М, i = 1,..., n).

2. Полагаем i = 1.

3. Определяем, является ли W ∪ { m_i } подмножеством некоторого множества Q из I; в случае положительного ответа переходим к п. 4, в случае отрицательного – к п. 5.

4. Включаем элемент m_i в множество W.

5. Увеличиваем значение i на единицу.

6. Если i ≠ n + 1, переходим к п. 3, в противном случае к п. 7.

7. Построенное множество W считаем решением задачи.

Изложенный алгоритм назовем G -алгоритмом (от английского greedy – жадный).

Относительно общего класса задач К* поставим вопрос: при каких налагаемых на семейство I условиях G -алгоритм строит оптимальное решение сформулированной экстремальной задачи?

Введем следующее определение.

Матроид – это пара < М, I >, где М – произвольное конечное множество, а I – семейство его подмножеств, удовлетворяющее аксиомам:

А1). Æ Î I и если А Î I и В Í А, то В Î I;

А2) Для произвольных P Î I, Q Î I, таких что | Q | = | P | + 1, существует элемент е Î Q \ P такой, что P È е Î I.

Отметим, что условие Æ Î I исключает вырожденный случай I = Æ. Множества семейства I далее будем называть независимыми, остальные подмножества совокупности М – зависимы-ми множествами матроида < М, I >.

Имеется определенная связь концепции матроида с теорией линейной зависимости. Аксиомы матроида отражают наиболее характерные свойства независимых подмножеств, содержащихся в конечном множестве элементов линейного пространства. Очевидно, что произвольное подмножество элементов из независимого множества линейного пространства независимо (совокупность элементов е ₁, е ₂, …, е_n линейно независима, если не существует набора скаляров λ ₁, λ ₂, …, λ _n не все из которых равны нулю такого, что λ ₁ е ₁+ λ ₂ е ₂ + … + λ _nе_n = 0). Если для линейно независимых подмножеств P, Q линейного пространства имеет место | Q | = | P | + 1, то P порождает подпространство размерности | P |, которое может содержать не более чем | P | элементов множества Q. Следовательно, существует элемент е Î Q \ P, не принадлежащий указанному подпространству. Таким образом, множество P È { е } линейно независимо.

Для произвольного подмножества С из М введем понятие его максимального независимого подмножества. Независимое подмножество А, А Í С именуем максимальным в С, если в С не существует независимого подмножества В такого, что А Ì В.

Приведем без доказательства следующий результат.

Теорема 3.2. Пусть М – конечное множество, а I – семейство его подмножеств, удовлетворяющее аксиоме А1. В этой ситуации пара < М, I > является матроидом тогда и только тогда, когда удовлетворяется условие:

А3) Для произвольного подмножества С из М два любых его максимальных подмножества содержат равное число элементов.

Из данной теоремы вытекает, что пара аксиом А1 и А3 образует эквивалентную паре А1 и А2 систему аксиом для матроидов.

Рангом произвольного подмножества С из М называем число элементов в максимальном независимом подмножестве множества С. Для ранга произвольного подмножества С из М принимаем обозначение r (С). Очевидно, что подмножество С из М независимо тогда и только тогда, когда r (С)= | С |. Каждое мак-симальное независимое подмножество множества М именуется базой матроида. Число r (М) – ранг матроида.

Очевидно, что две любые базы матроида < М, I > имеют одинаковое число элементов. Каждое независимое множество С из М можно расширить до базы путем поочередного добавления к нему новых элементов, присоединение которых не нарушает независимости, вплоть до момента, когда ни одного нового эле-мента добавит невозможно.

Приведем еще один, эквивалентный предыдущим, способ задания матроида. Матроид – это пара < М, В >, где где М – произвольное конечное множество, а В – семейство его подмножеств, удовлетворяющее аксиомам:

В1) Никакое множество из семейства В не содержится в другом множестве этого семейства.

В2) Если В ₁ и В ₂ входят в семейство В, то для любого эле-мента х из В ₁ существует элемент у из В ₂ такой, что совокупность (В ₁ \ x) È у тоже входит в семейство В.

Элементы семейства В – базы матроида.

Рассмотрим несколько примеров матроидов.

1. Пара < M, { M }>, где M – произвольное конечное непустое множество, является матроидом, единственной базой которого служит само множество M.

2. Пусть L – линейное пространство, M Í L – произвольное конечное непустое подмножество из L, I – множество, элементами которого служат все линейно независимые системы векторов из M и пустое множество. Тогда пара < М, I > является матроидом с набором независимых множеств I. Такой матроид именуется векторным матроидом, порожденным множеством векторов M. Базами этого матроида являются все базы множества M. В частности, взяв в качестве M множество векторов, являющихся столбцами (строками) некоторой матрицы В, получаем матричный матроид. Ранг матроида равен рангу матрицы В.

3. Пусть G – произвольный конечный неориентированный граф, M – множество всех его ребер. Подмножество ребер Х, Х Í M, является базой (элементом совокупности В), если это под-множество образует некоторый остов данного графа. Для пары < М, В > аксиомы В1 и В2 выполняются, данная пара образует матроид.

Теорема 3.3. (Теорема Радо–Эдмондса). Если пара < М, I > – матроид, то для любой весовой функции применением к данной паре G -алгоритма конструируется множество Х, являющееся независимым множеством с наибольшим весом. Если же пара < М, I > не является матроидом, то существует такая весовая функция f (x), что конструируемое применением G -алгоритма множество Х не является независимым множеством с наибольшим весом.

Теорема Радо–Эдмондса дает ответ на поставленный для за-дач класса К* вопрос об условиях, при которых G -алгоритм строит решения, являющиеся оптимальными.

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

В случае, если массовая задача Z – это задача коммивояжера, сформулированный вопрос об оптимальности построенного жадным алгоритмом решения произвольной индивидуальной задачи Z ₁ не имеет способа получения ответа с полиномиальной верхней оценкой числа выполняемых элементарных операций (считается, что Р ≠ NP). Данный факт прямо следует из доказательств теорем 19.5 и 19.6 монографии [17]. Идентичное имеет место и для задачи о ранце.

Введем понятие ε -оптимального решения, рассмотрим вопросы синтеза таких решений.

Для произвольной задачи

(12)

с обозначаемым через К* ненулевым оптимальным значением критерия решение Х назовем ε - оптимальным, если

{| К* – К (Х) | / К*} ≤ ε. (13)

Дробь{|К* – К (Х) | / К*} называем относительным отклонением критерия К (Х) при решении Х от своего оптимального значения.

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

Рассмотрим формулируемую следующим образом задачу об упаковке в контейнеры. Задано конечное множество предметов А = { a ₁, a ₂, …, a_n }; каждый предмет a_i имеет «размер» v (a_i), где v (a_i) – рациональное число, принадлежащее отрезку [0, 1]; требуется найти разбиение множества А на попарно непересекающиеся подмножества А ₁, А ₂, …, А_g такое, чтобы сумма «размеров» элементов каждого подмножества не превосходила 1 и чтобы значение g (число подмножеств в разбиении) было минимально возможным. Здесь мы считаем, что предметы одного подмножества должны упаковываться в один контейнер «размера» 1 и наша цель – использовать как можно меньшее число контейнеров.

Введенная задача NP - трудна в сильном смысле, ибо в частном случае она дает задачу «3-разбиение». С учетом гипотезы Р ≠ NP, можно утверждать отсутствие для задачи об упаковке в контейнеры даже псевдополиномиального алгоритма синтеза оптимального решения. Однако имеются несколько весьма простых алгоритмов синтеза для этой задачи ε -оптимальных решений.

Один из таких алгоритмов известен под названием «Первый подходящий» (ПП). Предположим, что имеется бесконечная последовательность контейнеров размера 1, каждый из них в начальный момент пуст. Предметы множества А распределяем по контейнерам согласно следующему простейшему правилу: очередной (по возрастанию индекса) предмет a_i помещается в контейнер с наименьшим номером, у которого сумма размеров уже помещенных в него предметов не превосходит 1 – v (a_i). Иными словами, предмет a_i помещается в первый контейнер, куда его поместить можно. Отметим, что алгоритм ПП не начинает заполнять новый контейнер до тех пор, пока можно использовать контейнеры, уже начатые заполнением.

Обозначим через Х _ПП решение задачи об упаковке в контейнеры, конструируемое изложенным алгоритмом. Число нужных при этом решении контейнеров К (Х _ПП) удовлетворяет неравенству

(14)

Действительно, в противном случае в построенном решении обязательно найдутся два непустых, но загруженных менее чем на половину контейнера, что невозможно. То, что указанная граница – наилучшая из возможных, следует из рассмотрения задачи с множеством предметов А = { a ₁, a ₂, …, a_n }, где v (a_i) = = (1/2) + ε,. i = 1,..., n. Так как никакие два предмета не могут быть помещены в один контейнер, общее число нужных контейнеров равно n. В то же время суммарный размер предметов равен (n /2) + n ε; если выбрать ε достаточно малым, суммарный размер окажется сколь угодно близким к n /2.

Оценим, как К (Х _ПП) может отличаться от минимально необходимого числа контейнеров К*. Очевидно неравенство

(15)

Из соотношений (14)–(15) получаем, что К (Х _ПП) ≤ 2 К*. Таким образом, алгоритм ПП для решения задачи упаковки в контейнеры является ε -оптимальным при ε = 1. Более тонкие рассуждения дают возможность установить ε -оптимальность алгоритма ПП для ε = 7/10.

Очевидно, что алгоритм ПП можно модифицировать, введя, например, такое правило размещения: каждый следующий предмет a_i помещается в тот контейнер, содержимое которого ближе всего к 1 – v (a_i), но не превосходит эту величину; если имеется несколько таких контейнеров, то из них выбирается имеющий минимальный номер. Такой алгоритм можно назвать «Наилучший из подходящих» (НП). К сожалению, оказывается, что алгоритм НП не является существенно лучшим, чем алгоритм ПП; характеристики этих алгоритмов практически совпадают.

Сейчас предположим, что предметы совокупности А упорядочены не произвольно (как это считалось ранее), а по уменьшению размеров. Процедура применения алгоритма ПП к упорядоченному таким образом списку предметов называется «Первый подходящий в порядке убывания» (ПППУ). Решение, получаемое этой процедурой, обозначим Х _ПППУ. Тогда К (Х _ПППУ) – число нужных при этом решении контейнеров. Минимально необходимое число контейнеров в рассматриваемой задаче по-прежнему обозначаем К*. Имеет место следующий результат.

Теорема 3.4. (Теорема Джонсона). Для любой задачи об упаковке в контейнеры выполняется неравенство

К (Х _ПППУ) ≤ (11/9) К* + 4.

Более того, существуют задачи об упаковке в контейнеры, для которых

К (Х _ПППУ) ≥ (11/9) К*.

Сейчас рассмотрим классическую задачу о ранце

(16)

при условиях

(17)

х_i Î {0, 1} (18)

и задачу о ранце с дробимыми предметами, отличающуюся от КЗР заменой условия (18) на

х_i Î [0, 1] (18')

В задаче с ограничением (18 ') считается, что предметы в ранец можно помещать не только целиком, но и частями. Для этой задачи известен очень простой способ синтеза оптимального решения – алгоритм Данцига. Этот алгоритм заключается в следующем. Для каждого i -го предмета вычисляется показатель γ _i = с_i / v_i; далее предметы помещаются в ранец последовательно, в порядке убывания показателя γ _i, до тех пор, пока остается выполненным ограничение (17); первый предмет, который нельзя поместить в ранец целиком, делится на две части так, что первая (помещаемая в ранец) часть имеет вес, обеспечивающий выполнение условия (17) как точного равенства. Вторая часть разделенного на части предмета в ранец не помещается, так же как и все следующие далее предметы.

Для задачи (16)–(18) алгоритм Данцига может трактоваться как следующая эвристическая процедура: для каждого i- го предмета вычисляем показатель γ _i = с_i / v_i; помещаем в ранец предмет с наибольшим значением этого показателя (если таких предметов несколько – первый из них по номеру), каждый следующий (по убыванию показателя γ _i) предмет помещается в ранец, если это позволяет сделать ограничение (17). Изложенную процедуру именуем эвристическим алгоритмом Данцига (ЭАД).

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

2 х ₁ + Мх ₂ → max;

х ₁ + М х ₂ ≤ М;

х_i Î {0, 1}, i = 1, 2;

здесь М – натуральная константа, удовлетворяющая ограничению М ≥ 3.

Для приведенной задачи ЭАД строит решение Х = (1, 0); обеспечиваемое этим решением значение критерия равно 2. В то же время оптимальным является решение Х* = (0, 1), обеспечивающее значение критерия М. Так как константа М может быть сколь угодно большой, ЭАД не является ε -оптимальным ни при каком значении ε.

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

299 х ₁ + 73 х ₂ + 159 х ₃ + 221 х ₄ + 137 х ₅ + 89 х ₆ + 157 х ₇ → max

при ограничениях

4 х ₁ + х ₂ + 2 х ₃ + 3 х ₄ + 2 х ₅ + х ₆ + 2 х₇ ≤ 10;

х_i Î {0, 1}, i = 1, 2, …, 7.

Если к данной задаче применить алгоритм B _кзр, то получим, что оптимальным решением является совокупность предметов с множеством номеров М ^(!) = {1, 2, 3, 6, 7}, а оптимальное значение критерия С ^(!) равно 777. В процессе реализации алгоритма приходится построить списки, суммарное число записей в которых оказывается равным 91. Естественная идея упрощения заключается в замене нулем младшего разряда в каждом из параметров с_i. В рассматриваемой задаче получаем следующий критерий:

290 х ₁ + 70 х ₂ + 150 х ₃ + 220 х ₄ + 130 х ₅ + 80 х ₆ + 150 х ₇ → max.

При новой критериальной функции получаем М ^(!) = {1, 3, 4, 6}, а оптимальное значение критерия С ^(!) равно 740. Здесь при реализации алгоритма B _кзр приходится построить списки, суммарное число записей в которых оказывается равным 36, т.е. практически втрое меньше, чем раньше. В то же время отличие в значении критерия около 5%; если для полученного множества {1, 3, 4, 6} вычислить значение первоначальной критериальной функции, то получим 768 (отличие от оптимума порядка 1%).

В общем случае, если при округлении отбросить в числах с_i последние t разрядов, то отклонение от оптимального значения критерия не будет превышать 10 ^tn. Время, необходимое для ра-боты алгоритма при решении исходной задачи не превосходит kс*n ³. После отбрасывания t разрядов оценка временных затрат принимает вид kс*n ³10 ^–t.

Если решение Х задачи о ранце с n предметами построено алгоритмом B _кзр после того, как в числах с_i отброшены последние t разрядов, разность К* – К (Х) не превышает 10 ^tn. При этом К * не меньше, чем с*. Получаем, что найденное решение Х является ε -оптимальным при некотором ε ≤ (10 ^tn) /с*. Отсюда

с* ≤ (10 ^tn)/ ε.

С учетом последнего неравенства, верхняя оценка числа выполняемых алгоритмом B _кзр элементарных операций kс*n ³10 ^–t путем замены параметра с* преобразуется к виду kn⁴/ ε.

Будем говорить, что алгоритм является полиномиальной приближенной схемой (ППС) для массовой задачи оптимизации Z, если по начальным данным индивидуальной задачи Z ₀ и ε > 0 он выдает ε -оптимальное решение этой задачи за время, ограниченное полиномом (зависящим от ε) от одной переменной – объема входной информации по решаемой задаче.

Таким образом, нами определена ППС для решения классической задачи о ранце; полином, зависящий от ε, имеет здесь вид (kn ⁴)/ε. Полученная оценка полиномиальна относительно n и 1/ε. Это достаточно удачная ситуация, ибо сделанное определение ППС допускает полином, в котором наибольшей степенью переменной n является, например, 1/ε.

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

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

Теорема 3.5. В предположении Р ≠ NP при любом ε > 0 для задачи коммивояжера нет решающей ППС.

Положим противное; допустим, что при некотором ε ₀ > 0 имеется ППС, решающая задачу коммивояжера. Покажем, что в таком случае существует способ решения задачи «Гамильтонов цикл» за полиномиальное время.

По произвольному конечному ориентированному графу G с множеством вершин {1, 2, …, n } строим (n × n)-матрицу S = { s_ij }, определяющую задачу коммивояжера. Полагаем, что все эле-менты главной диагонали матрицы S нулевые; в случае i ≠ j элемент s_ij этой матрицы равен 1 тогда и только тогда, когда в графе G имеется дуга (i, j); если i ≠ j и дуги (i, j) в графе нет, эле-мент s_ij полагаем равным 2 + n ε ₀.

Применим к построенной задаче коммивояжера ППС, конструирующую ε ₀-оптимальное решение. Утверждаем, что данной схемой в построенной задаче коммивояжера будет найдено решение с суммарной длиной обхода n тогда и только тогда, когда в исходном графе G гамильтонов цикл имеется.

Если применением ППС в задаче коммивояжера найдено решение с суммарной длиной обхода n (обходов меньшей длины в построенной задаче существовать не может), то граф G, оче-видно, гамильтонов. Докажем справедливость обратного утверждения. Предположим противное, т.е. что граф G гамильтонов, а применением ППС строится решение задачи коммивояжера с суммарной длиной обхода большей, чем n. В таком случае суммарная длина обхода не меньше n + 1 + n ε ₀, ибо реализуется по меньшей мере один элементарный переход длины 2 + n ε ₀. Вместе с тем, так как граф G гамильтонов, оптимальное значение критерия в построенной задаче коммивояжера равно n. Разность между значением критерия для решения, построенного применением ППС, и оптимальным его значением оказывается не меньше n ε ₀ + 1, а относительное отклонение критерия задачи при найденном ППС решении от оптимального его значения оказывается не меньшим ε ₀ + 1/ n. Но это противоречит утверждению о том, что применяемая ППС строит ε ₀-оптимальное решение. Получаем, что применением ППС в построенной зада-че коммивояжера решение с суммарной длиной обхода n строится тогда и только тогда, когда в исходном графе G гамильтонов цикл имеется. Таким образом, рассматриваемая ППС в полиномиальном времени решает проблему определения по произвольному графу, является ли он гамильтоновым. В предположении Р ≠ NP это невозможно. Методом от противного теорема доказана.

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

Пусть

– произвольная задача дискретной оптимизации. Предполагаем, что для каждого X из D определена окрестность G (Х), при этом X Î G (Х). Решения, принадлежащие окрестности G(Х), это в том либо ином смысле близкие X решения. Алгоритмы локальной оптимизации имеют следующую общую структуру:

1. Находим исходное допустимое решение Х ₀, Х ₀ Î D; пола-гаем k = 0;

2. По имеющемуся допустимому решению Х_k определяем окрестность этого решения G (Х_k); перебором принадлежащих окрестности решений находим решение Х*, оптимизирующее значение критерия при условии, что X Î G (Х_k). Если К (Х_k) = К (Х*), то Х_k – локальный оптимум. В противном случае переходим к п. 3.

2. Полагаем k = k +1;

3. Полагаем Х_k = Х* и переходим к п. 2.

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

Отметим, что симплекс-метод решения задач линейного программирования может трактоваться как локальный поиск; совокупность D – вершины многогранника ограничений, окрестность каждой точки Х из D включает вершины, смежные с вершиной Х.

В задаче коммивояжера понятие k -окрестности (k – натуральное число, фиксирующее размер окрестности, k ≥ 2) определим следующим образом: гамильтонов цикл С* принадлежит k -окрестности гамильтонова цикла С, если С* можно получить из С путем замены не более чем k дуг. Выполненные эксперименты показывают, что использование систем окрестностей при k = 2 малоэффективно, при k = 3 получаются достаточно хорошие (в среднем) результаты; переход к значению k = 4 существенно увеличивает время вычислений и мало улучшает качество получаемых результатов.