Х. Пападимитриу, К. Стайглиц - Комбинаторная оптимизация (1125252), страница 97
Текст из файла (страница 97)
е. все точки многогранника лежат по одну сторону от этой гиперплоскости (см. й 2.3). Это означает, что существует такой вектор й, что йэх=З'д=й, н й'о~ й, для всехвершинобр„очах, д. Положим Я=-гп(п(й'о — Ые1, где минимум берется по всем вершинам оЕР„о Фх, у. Используя величину Я, повернем гиперплоскость так, чтобы точка х осталась на ней, а у стала еближайшейь вершиной.
Для этого выберем координату 1, для которой уу = ! и х, =- О. (Такая координата должна существовать, ибо, согласно определению (9.7, ни одно множество не содержится в другом.) Увеличим й на Я/2. Стоимость х остается д„, стоимость у, становится равной й,+ 9/2, а стоимость всех остальных вершин остается не меныяе чем й,+ (е Докажем теперь достаточность Согласно лемме (9.2, достаточно установить этот результат для образов вершин х и д в многограннике Рм соответствующем задаче ЛП„ которая представляет собой зада у линейного программирования в стандартной форме.
Выберем вектор стоимости й с описанным свойством и применим симплекс-алгоритм в вершине ру с вектором стоимости й= =(й!0). Вершина х=-рх будет единственной оптимальной вершиной в Р, и у будет второй по стоимости вершиной. Предположим, что х и у не смежны. Поскольку отношение смежности в многограннике порождает точную систему окрестностей для симплекс-ачгоритма (теорема 2.
(0) и так как в соответствующей окрестности вершины у в многограннике нет решения с лучшей стоимостью, мы делаем вывод, что д оптимально — противоречие. Д Теперь мы в состоянии показать, что система окрестностей, порожденная отношением смежности в СН(Р), является единственной минимальной точной системой окрестностей дчя локального поиска в исходной ДЛЗП. Другими словами, наименьшие окрестности локального поиска, гарантирующие оптимальность, — это в точности те, которые просматривались бы симплекс-алгоритмом в сн ®. Гл, 19.
Локальный поиск Теорема 19.3, Отношение смежности в многограннике СН(г) порождает единственную минимальную точную систему окрестностей для локального поиска по г. Доказательство. Используя снова г„из симплекс-алгоритма получаем, что система окрестностей, порожденная отношением смежности в многограннике, является точной. Остается показать, что каждая вершина, смежная с х в многограннике СН(г), должна содержаться в каждой точной окрестности вершины х.
Чтобы показать это, предположим, что 1 — вершина, смежная с х, но не лежащая в некоторой точной окрестности х. По теореме !9.2 существует такой вектор стоимости й, что относительно него 1 — единственная оптимальная вершина и х — вторая по стоимости вершина. Но алгоритм точного локального поиска при рассмотрении вершины х объявит ее оптимальной — противоречие. Д м.з Пример бопьших минимепьпых точных окрестностей (Р51) Разберем теперь детально пример ДЛЗП вЂ” а именно задачу о расписании для заданий с директивными сроками — в которой можно явно указать минимальную точную окрестность допустимого решения.
Этот пример не только еще раз проиллюстрирует идеи предыдущего пара~рафа, но и поставит вопрос о том, сколько времени требуется для поиска по точной окрестности. Определение 19.8. Пусть йг=-(1, 2,...,п ) — множество заданий с директивными сроками О и временем выполнения Те Подмножество заданий ~:-У допустимо, если все задания из М вЂ” (Ц можно выполнить на одном процессоре без превьппения директивных сроков и множество У вЂ ()) максимально по включению, т.
е. М вЂ” Я не является собственным подмножеством никакого другого подмножества из У с тем же свойством. Индивидуальная задача о расписании для заданий с директивными сроками (РЗДС) — это ДЛЗП с указанным допустимым множеством г и некоторыми стоимостями й, для (бдг. С) Заметим, что мы определили допустимое множество как множество заданий, не вошедших в расписание, с тем, чтобы представить эту задачу как задачу минимизации. Таким образом, мы хотим найти такое ) б г, минимизирующее стоимость что с( можно рассматривать как штраф, накладываемый в том случае, если задание 1 не выполнено к директивному сроку. Заме.
тим также, что 0~ и Т~ считаются фиксированными:, они не по- !9.В. //ример больших минимальных окрестностей 491 л — 3 — при /=1, 2 0 при /Ф! и /бз, 1 в противном случае. д/ (з) =. Стоимость точки з относительно этого вектора с( равна (и — 3)/2, стоимость точки / равна (л — 1)/2, а стоимость любой другой допустимой точки не меньше, чем (и — 1)/2, Таким образом, любая точка з содержится в минимальной точной окрестности точки /, которая на самом деле в точности совпадает с Р'.
Эта окрестность Р' содержит (~"„~~ !/е) точек. Используя формулу Стирлинга, можно показать, что 2лл )/ 2лл (19. 16; В результате мы получили, что наименьшая точная окрестность точки / содержит огромное число точек. Этот факт является следствием нашего выбора 0~ и Т/, но это геометрический факт, незавнсимый от вектора стоимости д, который мы рассматриваем как входную информацию. ступают в качестве входных данных задачи, а только определяют допустимое и ожество Р.
Рассмотрим еперь задачу РЗДС, в которой допустимое мно- жество определя~тся следующими фиксированными значениями О/ и Р/ при условии, что п нечетно: л — 1 2 для всех 1Е й/, / л — 1 т/= 2 — при /=1, 1 при /> 1. Если мы включаем в расписание задание 1, то не остается времени для выполнения никакого другого задания, поэтому одной допусти- мой точкой будет /=й/ — (! ). Если мы не включаем в расписание задание 1, то остается место ровно для (и — 1)/2 заданий с единич- ным временем выполнения, что приводит к следующему множеству допустимых точек: Р'=4зыУ: 1Е л+! ! Этим исчерпываются все возможные допустимые точки, поэтому Р=(/) (! Р'. Выберем теперь произвольную точку ВЕ Р' и укажем вектор стоимости п(з), относительно которогоз — единственная оптималь- ная точка и / — вторая по стоимости точка. По теореме 19.2 отсюда будет следовать, что / и з смежны.
В качестве искомого вектора можно взять вектор с координагами 492 Гм 19. Локальный поиск Если иметь в виду перечисление всех точек из Р', то должно казаться, что точный локальный поиск из точки 1 потребует очень много времени. Следующий результат может показаться удивительным. Теорема 19.4. Для любой индивидуальной задачи РЗДС с определенными еьиие Ту, 0 и произвольным вектором стоимости й поиск по минимальйой точной окрестности Р' точки 1' можно произвести за время 0(п).
Доказательство, Так как Р=Я() Р', то поиск по Р' сводится к нахождению оптимального решения. Это можно осуществить, находя (и — 1)/2 заданий из множества М вЂ” (1), суммарная стоимость которых максимальна, и сравнивая эту стоимость с с(ы Алгоритм нахождения медианы, упомянутый в задаче 2 из гл.
12, позволяет сделать это за время 0(п). ь1 Здесь мы имеем пример, когда поиск по окрестности очень сильно ориентирован на данные в направлении, подсказанном поиском переменной глубины из 9 19.5. В работах [Ба!, За2, Зьч'В, ЯаЪ'К) показано, что минимальная точная окрестность для ЗК имеет экспоненциальную мощность (см. задачу 15), однако предыдущий пример позволяет надеяться, что для ЗК существует алгоритм точного локального поиска с окрестностями, которые можно просматривать быстро, скажем за полиномиальное время. Это не будет гарантировать существования полииомиального алгоритма для ЗК, так как останется не ясным, сколько улучшений требуется для достижения оптимальности.
Но это по крайней мере давало бы точный алгоритм, полезный для задач малого размера, совершенно аналогично симплекс-алгоритму для задачи ЛП, который также производит поиск по точной окрестности за полиномиальное время. Результаты следующего параграфа разрушают даже эту надежду, 1 9.т Сложность точного локального поиска для ЗК 1Р541 Цель этого параграфа — показать, что поиск поточной окрестности для задачи коммивояжера можно производить за полиномиальное время только в том случае, если Р- ИР, что очень маловероятно. Нам потребуется следующая задача.
ОГРАНИЧЕННЫЙ ГАА(ИЛЬТОНОВ ЦИКЛ (ОГЦ) Даны граф 0=-(У, Е) и гамильтонов путь Р в О. Спрашивается, существует ли гамильтонов цикл с в графе О? Таким образом, мы указываем гамильтонов путь (т. е. гамильтонов цикл без одного ребра) и интересуемся, существует ли гамиль- 19:У. Сложность точного локального поисхо длл ЗК 493 тонов цикл. Окарывается, что этот гамильтонов путь не помогает нам при решений данного вопроса. Теорема 19.5. Задача ОГЦ НР-полна. Доказапгельство. Задача ОГЦ, очевидно, принадлежит ИР. Мы полииомиальпо преобразуем обычную задачу о гамильтоновом цикле (ГЩ в задачу ОГЦ с помощью специального подграфа, изображенного на рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
