 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Сложность задач
Сложность задачи и полиномиальная сводимость
Сложности задачи характеризуют сложностью наилучшего алгоритма, решающего задачу с самым трудным значением входа.
Сводимость задач
Пусть имеем задачи Z1 и Z2 . Пусть имеем также алгоритм S, позволяющий получить решение задачи Z1 из решения задачи Z2. Таким образом, получить решение задачи Z1 мы можем, решив задачу Z2 (с соответствующими входными данными) и преобразовав это решение в искомое решение задачи Z1 с помощью алгоритма S.
Говорят, что задача Z1 полиномиально сводится к задаче Z2, если существует алгоритм S полиномиальной сложности, позволяющий получить решение задачи Z1 из решения соответствующей задачи Z2.
Теорема
Если задача Z1 полиномиально сводится к задаче Z2, тогда если задача Z2 имеет полиномиальную сложность, то и задача Z1 также имеет полиномиальную сложность.
Различают 3 основных класса сложности задач:
1) задачи, для которых известны алгоритмы полиномиальной сложности;
2) задачи, для которых не известны алгоритмы полиномиальной сложности, но для которых и не доказано несуществование таких алгоритмов;
3) задачи, для которых установлено, что они не могут быть решены алгоритмом полиномиальной сложности.
Задачи, которые не принадлежат первому классу, называют труднорешаемыми.
Второй класс задач является самым загадочным. Для большинства задач этого класса справедливо следующее: существование полиномиального алгоритма для одной из них означает существование полиномиального алгоритма для всех остальных.
Большим разнообразием в отношении сложности отличаются задачи дискретной математики. Алгоритмы решения многих из них имеют переборный характер, что часто приводит к труднорешаемости задачи. Нередки случаи, когда такая задача может быть решена только путем применения алгоритма полного перебора. В таком случае сложность задачи определяется тем, насколько быстро растет множество вариантов с увеличением размера входных данных.
Классы сложности задач
Далее под задачей будем понимать задачу, для которой мы имеем строгую формулировку, которая является правильной в некоторой системе понятий. Формулировка задачи считается правильной, если имеется критерий правильности ее решения.
Все возможные задачи делятся на два класса:
AR - алгоритмически разрешимые задачи,
NAR - алгоритмически не разрешимые задачи.
Примерами задач класса NAR являются:
- проблема разрешимости для логики предикатов;
- проблема тождества слов в полугруппах.
К классу задач AR относятся все задачи вычислительной математики. Задачи этого класса делятся на два подкласса:
NP - задачи, которые могут быть решены недетерминированным алгоритмом полиномиальной сложности;
AR-NP - алгоритмические разрешимые задачи, которые не могут быть решены недетерминированным алгоритмом полиномиальной сложности.
Задачи класса NP в свою очередь делятся на два подкласса:
P - множество задач, которые решаются детерминированным алгоритмом полиномиальной сложности;
NP-P - задачи класса NP, для которых не существует детерминированный алгоритм полиномиальной сложности.
Класс P представляет собой множество задач, для каждой из которых существует детерминированный алгоритм с полиномиальной функцией сложности.
Класс NP определяется как множество задач, которые могут быть решены недетерминированным алгоритмом с полиномиальной функцией сложности.
Очевидно, что P Í NP.
NP-трудные и NP-полные задачи
Задача называется NP-трудной, если любая задача из NP полиномиально сводится к ней.
Задача называется NP-полной, если она является NP-трудной и в то же время принадлежит к классу NP.
Таким образом, имеют место следующие соотношения:
{NP-полные} Í {NP-трудные}
сложность(NP-полная) £ сложность(NP-трудная).
Примеры задач разной сложности
Полиномиальная сложность:
- задачи о кратчайших путях и маршрутах на графах;
- задача о максимальном потоке транспортной сети;
- задачи о паросочетаниях, о назначениях (двудольные графы).
Экспоненциальная сложность:
- задача установления изоморфности графов.
NP-трудные задачи:
- поиск максимальной клики и определение плотности графа;
- определить, является ли заданный граф гамильтоновым;
- задача коммивояжера;
- задача о наибольшем общем подграфе;
- задача о взломе шифра.
Задача определения изоморфности графов
О задаче определения изоморфности двух графов известно, что она принадлежит NP, но не известно, принадлежит ли она классу P и является ли она NP-полной. В то же время более сложная задача: определить, изоморфен ли граф G1 какому либо подграфу графа G2, является NP-полной. Задача о выделении максимального множества независимых вершин является NP-полной даже для класса планарных графов.
Поиск по сайту: