ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 17.04.2019
Просмотров: 2343
Скачиваний: 1
56
6.5 Приклади NP – повних задач
6.5.1 Задача про виконуваність схеми
Розглянемо схему з функціональних елементів «і», «або», «ні» з n
бітовими входами і одним виходом, що складається не більше, ніж з O(n
k
)
елементів – рис 6.4.
Рис 6.4. Абстрактна функціональна схема
Будемо вважати під виконуючим набором значень з множини {0,1} на
вході схеми, такий набір входів – значення x1, ..., xn, при якому на виході
схеми буде значення «1».
Формулювання задачі – чи існує для даної схеми набір значень входу
x1, ..., xn.
Задача належить класу NP – перевірка знайденого набору x1, ..., xn не
складніше кількості функціональних елементів, і отже не більше ніж O(n
k
).
Це була одна з перших задач, для якої було доведено її NP повнота, тобто
будь-яка задача з класу NP поліноміально зводиться до задачі про
здійснимість схеми [5].
Вирішення цієї задачі може бути отримано перебором всіх 2n можливих
значень входу з подальшою перевіркою на відповідність умові ви-
виконуючого набору. У найгіршому випадку доведеться перевірити всі
можливі значення входу, що призводить до оцінки F
^
(n) = O(n
k
* 2
n
).
Для цієї, як і для всіх інших NP-повних задач, не відомий
поліноміальний алгоритм вирішення.
n
O(n
k
)
…
57
6.5.2
Задача про суму
Вже розглянута задача про суму також є NP-повною. Відмітимо, якщо
кількість доданків фіксована, то складність задачі є поліноміальної, так як:
•
для 2-х доданків ⇒ С
N
2
=(N*(N-1))/(1*2) = O(N
2
);
•
для 3-х доданків ⇒ C
N
3
=(N*(N-1)*(N-2))/(1*2*3) = O(N
3
).
В загальному випадку доведеться перебирати 2N різних варіантів,
оскільки за біноміальною теоремою
(a+b)
N
=
∑
c
N
k
* a
N-k
* b
k
,
а при a=b=1,
маємо:
(1+1)
N
=
∑
C
N
k
= 2
N
,
отже,
F
A
(N, V) = O(N * 2
N
).
6.5.3
Задача про клік
Нехай дано граф G = G (V, E), де V – безліч з n вершин, а E – безліч
ребер. Будемо розуміти під кліком максимальний за кількістю вершин повний
підграф на графі в G.
Задача полягає у визначенні кліку в заданому графі G.
Оскільки в повному графі на m вершинах мається m*(m-1)/2 ребер, то
перевірка, чи є даний граф повним, має складність O (m
2
).
Якщо ми розглядаємо підграф з m вершинами в графі G з вершинами (m
<n),
то всього існує Cnm різних підграфів. Якщо в задачі про клік кількість
вершин кліки фіксоване, то алгоритм розв’язку має поліноміальну складність:
F(m, n) = O(m
2
* C
n
m
) = O(m
2
* n
m
).
Однак у загальному випадку доведеться перевіряти всі підграфи з
кількістю вершин m = (2, n) на їх повноту і визначити максимальне значення
m
для якого в даному графі G існує повний підграф, що призводить до оцінки
в найгіршому випадку:
F
^
(n) =
∑
O( k
2
* C
n
k
)
⇒
O (n
2
* 2
n
)
k
58
6.6
Питання для самоконтролю
1)
Теоретична межа трудомісткості завдання.
2) Основні задачі теорії складності обчислень, поняття реально
вирішуваних завдань.
3)
Поняття с класів складності задач, клас Р.
4)
Клас складності NP, поняття сертифіката.
5)
Проблема P = NP, та її сучасний стан.
6)
Зводимість мов і визначення класу NPC.
7)
Приклади NP – повних задач.
8)
Задача про клік та її особливості.
59
7. ПРИКЛАД ПОВНОГО АНАЛІЗУ АЛГОРИТМУ
ВИРІШЕННЯ ЗАДАЧІ ПРО СУМУ
7.1
Формулювання задачі
і
асимптотична оцінка
Словесно задача про суму формулюється як задача знаходження таких
чисел з даної сукупності, які в сумі дають задане число. Класично завдання
формулюється в термінах цілих чисел [5].
У термінах структур даних мови високого рівня завдання формулюється,
як задача визначення таких елементів вихідного масиву S з N чисел, які в сумі
дають число V (відзначимо, що задача належить до класу NPC).
Детальне формулювання:
Задано:
Масив S[i], i={1, N} і число V.
Необхідно: Визначити такі S
j
, що
∑
S
j
= V
Тривіальне рішення визначається рівністю V=Sum, де Sum=∑ S
i
, умови
існування рішення мають вид:
Min {S[i], i=1,N}
≤ V ≤ Sum.
Отримаємо асимптотичну оцінку складності рішення даної задачі для
алгоритму, що використовує прямий перебір всіх можливих варіантів.
Оскільки вихідний масив містить N чисел, то перевірці на рівність V
підлягають такі варіанти рішень:
- V
містить 1 доданок ⇒ СN1 = N варіантів;
- V
містить 2 доданків ⇒ СN2 = (N * (N-1)) / (1 * 2) варіантів;
- V
містить 3 доданків ⇒ CN3 = (N * (N-1) * (N-2)) / (1 * 2 * 3) варіантів;
-
І т.д. до перевірки одного варіанту з N доданками.
Оскільки сума біноміальних коефіцієнтів для ступеня N дорівнює
(1+1)
N
=
∑ C
N
k
= 2
N
і для кожного варіанту необхідно виконати підсумовування (з оцінкою O(N))
для перевірки на V, то оцінка складності алгоритму в гіршому випадку має
вигляд:
F
^
A
(N, V) = O(N*2
N
)
(7.1)
60
7.2
Алгоритм
точного
рішення задачі
про суму
(метод
перебору
)
Визначимо допоміжний масив, що зберігає поточне поєднання вихідних
чисел в масиві S, що підлягають перевірці на V – масив Х[j], елемент масиву
дорівнює «0», якщо число S [j] не входить в V і дорівнює «1», якщо число S
[j]
входить до V.
Рішення отримано, якщо
V =
∑
S[j]*
Х[j].
Можуть бути запропоновані наступні дві реалізації механізму повного
перебору варіантів:
•
перебір за всілякими сполученням з k елементів по N. Тобто спочатку
алгоритм намагається представити V як один з елементів масиву S, потім
перебираються всі можливі пари, потім всі можливі трійки тощо;
•
перебір за допомогою бінарного лічильнику, реалізованому в масиві Х.
Друга ідея алгоритмічно більш проста і зводиться до вирішення задачі
про збільшення двійкового лічильника в масиві Х на «1»:
•
при 00 ... 0111 збільшення на «1» призводить до скиду всіх правих «1» і
установці в «1» наступного самого правого «0»;
•
при 00 ... 1000, коли останній елемент лічильника дорівнює «0»
збільшення на «1» призводить до переустановлення останнього елемента в
масиві Х з «0» в «1».
Розглядаючи масив Х як інформацію про елементи масиву S, що
підлягають підсумовуванню в даний момент, треба робити підсумовування і
перевірку на рівність V, до тих пір, поки рішення не буде знайдено або ж
безрезультатно будуть переглянуті всі можливі варіанти.
Таким чином, алгоритм точного рішення задачі про суму методом
прямого перебору має у формальній системі мови високого рівня наступний
вигляд:
TASKSUM(S,N,V;
Х,FL)
FL
←
false
i
←
1
repeat
Х[i]
←
0