Лабораторная работа 25. Np полные задачи

Лабораторная работа 25. NP – полные задачи
Цель работы: овладеть навыками составления алгоритма NP – полных задач и их анализ на эффективность.

Теоретическая часть
Считается, что алгоритм – полиномиальный или имеет полиномиальную временную сложность, если существует полином p(x) такой, что на любом входном слове длины n алгоритм завершает вычисления после выполнения не более чем p(n) операций.
Говорят, что задача разрешима за полиномиальное время или полиномиально разрешима, если для неё существует полиномиальный алгоритм. При этом считается, что задача является «хорошей».
Множество всех задач, для каждой из которых существует полиномиальный алгоритм, называется классом Р.
Абстрактной моделью полиномиального алгоритма является так называемая детерминированная машина Тьюринга. Эта машина в каждый данный момент времени находится в строго определённом состоянии, за один шаг она совершает одно из некоторого конечного множества действий. Затем она переходит в следующее состояние и всё начинается вновь, пока не придёт к ситуации останова.
Наиболее простыми считаются полиномиальные задачи, т.е. задачи класса Р.
Другим, возможно более широким, «сложностным классом» является класс NP. Эта аббревиатура обозначает выражение «разрешимых на Недетерминированной машине Тьюринга за Полиномиальное время». Класс NP стали впервые изучать Эдмонде, Кук и Кири. Оказалось, что многие известные задачи принадлежат к NP классу.
Вобычных машинах Тьюринга (их называют детерминированными, чтобы отличать от недетерминированных) новое состояние, в которое машина переходит на очередном шаге, полностью определяется текущим состоянием и тем символом, который обозревает головка на ленте.
Внедетерминированных машинах Тьюринга для каждого состояния может быть несколько следующих состояний, в соответствии с функцией перехода. И в каждом следующем состоянии запускается новая копия данной машины Тьюринга.
Недетерминированность лучше всего понять, рассматривая алгоритм, который производит вычисления до тех пор, пока не доходит до места, в котором должен быть сделан выбор из нескольких альтернатив. Детерминированный алгоритм исследовал бы сначала одну альтернативу, а потом вернулся для рассмотрения следующей альтернативы. Недетерминированный алгоритм может исследовать все альтернативы одновременно, «копируя», в сущности, самого себя для каждой альтернативы. Все копии работают независимо. Если копия обнаруживает, что данный путь безрезультатный, то она прекращает выполняться. Если копия находит требуемое решение, она объявляет об этом, и все копии прекращают работать. Определим NP класс как класс задач, которые можно решить недетерминированными алгоритмами, работающими в течение полиномиального времени. Чтобы доказать, что некоторая задача принадлежит классу NP, достаточно построить недетерминированный алгоритм (алгоритм недетерминированной машины Тьюринга), который решает эту задачу за полиномиальное время.
Детерминированная машина Тьюринга является частным случаем недетерминированной машины Тьюринга (которая не имеет копий).
Примеры задач из класса NP:
1)выяснение выполнимости формулы логики высказываний, записанной в к.н.ф.;
2)нахождение целочисленных решений системы линейных
уравнений;
3)задача распознавания простого числа;
4)выяснение гамильтоновости графа;
5)задача коммивояжёра;
6)размещение обслуживающих центров (телефон, телевидение, срочные службы) для максимального числа клиентов при минимальном числе центров;
7)оптимальный раскрой (бумага, стальной прокат, отливка), оптимизация маршрутов в воздушном пространстве, инвестиций, станочного парка;
8)составление расписаний, учитывающих определённые условия;
9)оптимальная загрузка ёмкости (рюкзак, поезд, корабль, самолёт) при некоторых условиях;
10)динамическое распределение памяти.
Рассмотрим сводимость задач. Хотя сведение одних задач к другим является традиционной математической деятельностью, оно до работ С. Кука не было подвержено самостоятельному исследованию. Именно С. Куку принадлежит честь выделения этого понятия как центрального в теории полиномиальной сводимости.
Говорят, что задача Z1 сводится к задаче Z2 если метод решения задачи Z2 можно преобразовать в метод решения задачи Z1. Сводимость называется полиномиальной если указанное преобразование можно осуществить за полиномиальное время.
Если одновременно задача Z1 полиномиально сводится к задаче Z2 и Z2 полиномиально сводится к задаче Z1, то задачи Z1 и Z2 полиномиально эквивалентны.
Задача называется NP-трудной если каждая задача из NP полиномиально сводится к ней.
NP-трудная задача имеет тот смысл, что эта задача не проще, чем «самая трудная в NP».
В классе NP выделяются NP-полные задачи. Задача называется NP- полной, если она входит в NP и каждая задача из NP полиномиально сводится к ней (т.е. является NP-трудной). NP-полные задачи понимаются как самые трудные задачи из класса NP.
Класс NP- полных задач обладает следующими свойствами.
1.Никакую NP-полную задачу нельзя решить никаким известным полиномиальным алгоритмом, несмотря на настойчивые усилия многих блестящих исследователей.
2.Если бы удалось построить полиномиальный алгоритм для какой-нибудь NP-полной задачи, то это бы означало полиномиальную разрешимость каждой NP-полной задачи. Основываясь на этих двух свойствах, многие высказывают гипотезу, что P ≠ NP. Практическое значение понятия NP-полной задачи лежит именно в широко распространенном мнении, что такие задачи по существу труднорешаемы. Следовательно, при их решении в худшем случае потребуется экспоненциальное количество времени и не будет возможности решить на практике такие задачи, за исключением очень малого числа индивидуальных задач.