|
||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[281] (т.е. его размер ограничен полиномом от размера формулы р>), и что построение графа G по формуле р> проводится за полиномиальное время. Таким образом, задача 3-CNF-SAT сводится за полиномиальное время к задаче HAM-CYCLE, что и требовалось доказать. 36.4.4. Задача коммивояжёра С задачей о гамильтоновом цикле тесно связана задача коммивояжёра (traveling salesman problem, TSP). В этой задаче требуется найти оптимальный маршрут посещения га городов. Коммивояжёр хочет объехать все города, побывав в каждом ровно по одному разу и вернуться в город, из которого начато путешествие. Известно, что перелёт из города г в город j стоит c(i,j) рублей (считаем цены целыми числами). В терминах теории графов задачу можно сформулировать так: требуется найти в данном графе гамильтонов цикл с наименьшей стоимостью (стоимость цикла есть сумма стоимостей всех его рёбер). Соответствующий язык формально определяется так: TSP = {(G, с,k) : G = (V, Е) - полный граф,с : V X V -> Z - функция стоимости, к G Z и в G есть гамильтонов цикл стоимости не более к}. Теорема 36.15 Задача коммивояжера является NP-полной. Доказательство Очевидно, задача TSP принадлежит классу NP (в качестве сертификата можно взять гамильтонов цикл стоимости не выше к). Чтобы убедиться, что задача коммивояжёра является NP-трудной, сведём к ней задачу HAM-CYCLE. Чтобы узнать, есть ли в графе G гамильтонов цикл, построим полный граф G с теми же вершинами; рёбра из G будут иметь цену 0, а все остальные рёбра - цену 1. Очевидно, что в графе G существует путь коммивояжёра стоимости 0 в том и только в том случае, когда граф G имел гамильтонов цикл. Упражнения 36.5-1 Задача изоморфизма с подграфом subgraph-isomorphism problem требует выяснить для пары графов G\ и G2, изоморфен ли граф G\ некоторому подграфу графа G2. Докажите, что эта задача NP-полна. 36.5-2 Дана целочисленная матрица А размера т X п и то-мерный вектор Ь. Задача 0-1 целочисленного линейного программирования (01 integer-progeamming problem) требует выяснить, существует ли такой га-мерный вектор х с элементами из множества {0,1}, что Ах Ь. Докажите, что данная задача NP-полна. (Указание: сведи- те к ней задачу 3-CNF-SAT.) 36.5-3 Докажите, что задача о сумме подмножества становится полиномиальной, если величину требуемой суммы (t) записывать в унарной системе счисления (как последовательность из t единиц). 36.5-4 Задача о разбиении на равные части (set-partition problem) состоит в следующем: дано множество целых чисел S; выяснить, можно ли разбить его на две части с равными суммами, то есть найти множество ACS, для которого YlxeA х = 2xes\Ax- Покажите, что эта задача является NP-полной. 36.5-5 Докажите NP-полноту задачи о гамильтоновом пути (упр. 36.26). 36.5-6 Задача о самом длинном простом цикле состоит в отыскании в данном графе простого (без повторяющихся вершин) цикла наибольшей длины. Сформулируйте соответствующую задачу разрешения и докажите её NP-полноту. 36.5-7 Профессор утверждает, что конструкцию А-блока в доказательстве теоремы 36.14 можно упростить, исключив вершины z3 и z4, а также вершины под над ними. Прав ли он - или такое упрощение создаст не предвиденные им проблемы? Задачи 36-1 Независимое множество Множество вершин V С V графа G = (V, Е) называется независимым (independent), если никакие две его вершины не соединены ребром. Задача о независимом множестве (independent-set problem) состоит в отыскании в данном графе независимого множества максимального размера. a.Сформулируйте соответствующую задачу разрешения и докажите ее NP-полноту. b.Предположим, мы имеем «чёрный ящик», с помощью которого можем решать задачу из пункта (а) за единичное время. Как с его помощью находить независимое множество максимального размера (а не только этот размер) за полиномиальное (от \V\ и \Е\) время? Хотя задача о независимом множестве в общей постановке NP-полна, некоторые её частные случаи могут быть решены за полиномиальное время. c.Постройте полиномиальный алгоритм, решающий задачу о независимом множестве для графов степени 2. Докажите правильность вашего алгоритма и оцените время его работы. d.Постройте полиномиальный алгоритм, решающий задачу о независимом множестве для двудольных графов. Докажите правиль- ность вашего алгоритма и оцените время его работы. (Указание: используйте результаты раздела 27.3.) 36-2 Раскраска графа Назовём к-раскраской (/г-coloring) неориентированного графа G = (V, Е) функцию с : V -> {1, 2,... , к}, для которой с(и) ф с[у) для всех рёбер (и, v) £ Е. Если считать, что числа 1,2,... , к обозначают к различных цветов, a c(v) есть цвет вершины v, то условие на раскраску состоит в том, что концы любого ребра имеют разные цвета. Задача о раскраске графа (graph-coloring problem) состоит в нахождении минимального количества цветов, необходимого для раскраски данного графа G с соблюдением этого условия. a.Постройте эффективный алгоритм, находящий 2-раскраску данного графа (если таковая существует). b.Сформулируйте задачу разрешения, соответствующую задаче о раскраске графа. Докажите, что сформулированная вами задача разрешима за полиномиальное время в том и только том случае, если задача о раскраске графа разрешима за полиномиальное время. c.Рассмотрим язык 3-COLOR, состоящий из графов, для которых существует 3-раскраска. Покажите, что если язык 3-COLOR является NP-полным, то и задача пункта (Ь) является NP-полной. Чтобы установить NP-полноту языка 3-COLOR, сведём к нему язык 3-CNF-SAT. Пусть имеется формула р> из класса 3-CNF, состоящая из т дизъюнкций и содержащая переменные х\, х2, • • • , хп. Построим по ней граф G = (V,E), который можно раскрасить в три цвета в том и только том случае, когда формула р> выполнима. Для каждой переменной жг- формулы р> мы добавим в граф две вершины (одна будет обозначаться жг-, другая - -*Xi). Кроме того, для каждой дизъюнкции мы добавим по 5 вершин. Наконец, нам понадобятся три специальные вершины, которые мы будем условно называть true, false и red. Теперь опишем рёбра графа G. Они делятся на два типа, которые мы условно назовём «литеральные» и «дизъюнктивные». Три литеральных ребра соединяют между собой вершины true, false и red (тем самым гарантируя, что каждая из трёх вершин будет окрашена в свой цвет). Кроме того, для каждой переменной жг- имеется треугольник из литеральных рёбер, включающий в себя вершины жг-, -1Жг- и red. (К дизъюнктивным рёбрам мы ещё вернёмся.) d.Рассмотрим произвольную 3-раскраску графа G с описанными литеральными ребрами. Докажите, что из каждой пары вершин жг-, -1Жг- одна покрашена в цвет c(true), то есть в тот же цвет, что вершина true, а другая - в цвет c(false). Покажите, что есть естественное соответствие между 3-раскрасками такого графа и наборами значений переменных. Остается описать дизъюнктивные рёбра; они нужны, чтобы наложить на 3-раскраску условия, соответствующие истинности |
Среды: 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 | ||