|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[283] При этом степень и коэффиценты полинома, ограничивающего время работы, могут сколь угодно быстро расти с уменьшением е. Более сильное ограничение таково: схема приближения называется полностью полиномиальной (fully polynomial-time approximation scheme), если время работы обраничено некоторым полиномом от га и от 1/е, где га - размер входа, ае - оценка относительной ошибки. Например, время работы может быть ограничено величиной (1/е)2га3. В этом случае уменьшение е, скажем, в 3 раза приводит к увеличению времени работы в 9 раз. План главы В первых трёх разделах рассматриваются полиномиальные приближённые алгоритмы для трёх NP-полных задач. Последний раздел содержит пример полностью полиномиальной схемы приближения. В разделе 37.1 приводится полиномиальный приближенный алгоритм, решающий задачу о минимальном вершинном покрытии с ошибкой не более чем в 2 раза. В разделе 37.2 рассматривается задача о коммивояжёре. Если расстояния удовлетворяют неравенству треугольника, то имеется приближённый алгоритм, решающий эту задачу с ошибкой не более чем в 2 раза. В общем случае (когда неравенство треугольника не обязательно) такого алгоритма не существует ни для какой фиксированной оценки ошибки (если только Р не равно NP). В разделе 37.3 строится жадный приближённый алгоритм для задачи о покрытии множествами. Даваемое им решение отличается от оптимального не более чем логарифмическим (от числа элементов) множителем. Наконец, в разделе 37.4 мы приводим полностью полиномиальную схему приближения для задачи о сумме подмножества. 37.1. Задача о вершинном покрытии Эта задача описана в разделе 36.5.2. Там же доказана её NP-полнота. Напомним, что вершинным покрытием (vertex cover) неориентированного грана G = (V, Е) мы называем некоторое семейство его вершин V С V с таким свойством: для всякого ребра (и, v) графа G хотя бы один из концов и, v этого ребра содержится в V. Размером вершинного покрытия считаем количество входящих в него вершин. Задача о вершинном покрытии (vertex-cover problem) состоит в нахождении оптимального вершинного покрытия (optimal vertex cover), то есть вершинного покрытия минимального размера. Эта проблема является NP-трудной, поскольку соответствующая проблема разрешения является NP-полной (по теореме 36.12). Несмотря на это несложно найти вершинное покрытие, которое Рис. 37.1 37.1 Работа алгоритма APPROX-VERTEX-COVER (а) Исходный граф G с 7 вершинами и 8 рёбрами. (Ь) На первом шаге выбрано ребро (Ь, с) (жирное). Его концы Ъ и с (серые) включаются в вершинное покрытие С. Пунктирные рёбра (а, Ь), (с, е) и (с, d) покрыты и удаляются, (с) Ребро (е, /) добавляется к С. (d) Ребро (d, g) добавляется к С. (е) Результат работы алгоритма, множество С, содержит 6 вершин Ь, с, d, е, /, g. (f) Оптимальное вершинное покрытие этого графа содержит только три вершины (b,d,e). хуже оптимального не более чем в 2 раза. Это делает алгоритм Approx-Vertex-Cover: 4 возьмём произвольное ребро (и, v) из Е 6 удалим из Е все рёбра, инцидентные и или v На рисунке 37.1 приведюн пример работы алгоритма Approx-Vertex-Cover. Алгоритм строит вершинное покрытие С постепенно. Вначале С пустое (строка 1), а множество Е содержит все рёбра графа (строка 2). Затем в цикле (строки 3-6) мы берём ребро из Е, добавляем его концы и и v в С, а из Е изымаем все рёбра, имеющие своим концом и или v. Время работы этого алгоритма есть О(Е) (при соответствующем представлении множества Е). Теорема 37.1. Алгоритм Approx-Vertex-Cover работает с ошибкой не более чем в 2 раза. Доказательство. Прежде всего заметим, что даваемое им мно-ежство С является вершинным покрытием. В самом деле, цикл в строках 3-6 продолжается до тех пор, пока множество непокрытых рёбер Е не станет пустым. Чтобы убедиться, что число вершин в С не более чем вдвое хуже оптимально, посмотрим на множество А рёбер, выбираемых в ходе работы алгоритма. Никакие два из них не имеют общей вершины (после того, как ребро выбрано в строке 4, все имеющие с ним общую вершину удаляются в строке 6). Поэтому общее число вершин в С вдвое больше числа рёбер в А. Заметим теперь, что любое вершинное покрытие (в частности, оптимальное покрытие С*) содержит хотя бы одну вершину каждого выбранного ребра, и для разных рёбер эти вершины разные. Таким образом, А С*, и, следовательно, \С\ = 2\А\ 2С*. Что и требовалось доказать. Упражнения. 37.1-1. Приведите пример графа, для которого этот алгоритм всегда даёт неоптимальное решение. 37.1-2. Профессор Шипилов предлагает такой алгоритм решения задачи о вершинном покрытии: взять вершину наибольшей степени, включить её в покрытие, удалить все смежные рёбра, повторить это ещё раз и так далее. Приведите пример графа, для которого этот способ даёт решение, отличающееся от оптимального более чем в 2 раза. 37.1-3. Постройте жадный алгоритм, который находит оптимальное вершинное покрытие для графа, являющегося деревом, за линейное время. 37.1-4. Как мы видели в доказательстве теоремы 6.12, задача о вершинном покрытии и задача о клике взаимно дополнительны: минимальное вершинное покрытие является дополнением к максимальной клике в дополнительном графе. Можно ли отсюда заключить, что и для задачи о клике имеется приближённый алгоритм с ошибкой не более чем в константу раз? Почему? 37.2. Задача коммивояжёра Эта задача описана в разделе 36.5.5 и состоит в следующем. Для каждого ребра (и, v) полного неориентированного графа G = (V, Е) известна его стоимость c(u,v). Необходимо найти гамильтонов цикл минимальной стоимости. Стоимостью цикла (и вообще любого множества рёбер АСЕ) мы считаем сумму стоимостей его рёбер: (u,v)EA На практике функция стоимости рёбер обычно удовлетворяет неравенству треугольника, которое говорит, что промежуточная остановка w на пути из и в v увеличивает его стоимость: с(и, w) с(и, v) + c(v, w) для любых трёх вершин и, v, w. Например, это неравенство выполнено, если вершинами графа являются точки плоскости и стоимостью ребра считается его длина (расстояние между его концами). Как показывает упражнение 37.2-1, даже в предположении неравенства треугольника задача коммивояжёра остаётся NP-полной. Тем самым мало шансов найти полиномиальный алгоритм, дающий оптимальный путь, и имеет смысл искать приближённые алгоритмы. В разделе 37.2.1 мы рассмотрим приближённый алгоритм, решающий эту задачу (в предположении неравенства треугольника) с ошибкой не более чем в 2 раза. Неравенство треугольника существенно: в общем случае алгоритма, решающего её с ошибкой не более чем в С раз, не существует ни для какого фиксированного С (если только Р не равно NP). 37.2.1. Задача коммивояжёра (с неравенством треугольника) Мы можем воспользоваться алгоритмом MST-Prim отыскания минимального покрывающего дерева из раздела 24.2, переделав его в цикл. Если выполнено неравенство треугольника, то этот цикл не более чем вдвое длиннее оптимального. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | ||