NP-складність і NP-повнота. Приклади наближених алгоритмів для NP-повних задач. Лекція 4

Сентябрь 15, 2022

Главная
Алгебра
NP-складність і NP-повнота. Приклади наближених алгоритмів для NP-повних задач. Лекція 4

Содержание

2. Питання NP-складність задач. NP-повнота задач. Приклади наближених алгоритмів для NP-повних задач.
3. Задача пошуку (search problem) Задача пошуку (search problem) задається алгоритмом С, який отримує на вході умову
4. Теза Черча - Тьюринга Будь-яка обчислювана функція обчислюється машиною Тьюринга. Поліноміальні алгоритми існують для багатьох задач.
5. Задача «від прогулянок по Кенігсбергу до реконструкції геному». Перша половина XVIII століття. Великий математик Леонард Ейлер
6. Твердження: P⊆PC. Доказ: оскільки детерміновані машини Тьюринга є частковим випадком не детермінованих. Отже, до детермінованих класів
7. Існують більш високі класи. Крім класу P вивчають інші класи, які визначаються порядком зростання часу роботи
8. До класу NP відносяться недетерміновані машини Тьюрінга. Формально недетерміновані обчислення проводяться на недетермінованій машині Тьюринга. Клас
9. NP-повнота Якщо Р не збігається з NP, то відмінність між Р і NP\P дуже істотна. Всі
10. Поняття поліноміальної зведеності Основна ідея умовного підходу заснована на понятті поліноміальної зведеності. Будемо говорити, що має
11. Лемма 1. Якщо L1∞L2, то з L2∈Р слідує, що L1∈Р. (Еквівалентне твердження: з L1 Р слід,
12. Лемма 2. Якщо L1∞L2 та L2∞L3 , L1∞L3. Лемма 2 стверджує, що це відношення є відношенням
13. Мова L називається NP-повною, якщо L∈NP і будь-яка інша мова L'∈NP зводиться до мови L. Pадача
14. Будь-яка NP-повна задача П має властивість: якщо P≠NP, то П∈NP\P. Точніше, П∈Р тоді і тільки тоді,
15. Приклади наближених алгоритмів для NP-повних задач Алгоритм, який повертає рішення, близькі до оптимальних, називається наближеним алгоритмом.
16. Методи розв’язання NP-повних задач Наближені та евристичні методи – застосування евристик для вибору елементів рішення. Псевдополіноміальні
17. Метод локальних покращень Розпочати з довільного рішення. Для покращення поточного рішення застосувати до нього будь-яке перетворення
18. Метод гілок та меж Вирішуючи дискретну екстремальну задачу, розіб'ємо множину всіх можливих варіантів на класи і
19. Дискретна екстремальна (на мінімум) задача в загальному вигляді: Нехай задано дискретну множину А і визначено на
20. Алгоритм методу: Розіб'ємо множину А на підмножини Аі і на кожному з них знайдемо нижню оцінку
22. Скачать презентацию

Слайд 2

Питання
NP-складність задач.
NP-повнота задач.
Приклади наближених алгоритмів для NP-повних задач.

Слайд 3

Задача пошуку (search problem)
Задача пошуку (search problem) задається алгоритмом С,

який отримує на вході умову І та кандидата на розв’язок S і має час роботи, обмежений поліномом від |I|.
S називається рішенням (solution), якщо С(S,I)=true.
Стосовно класів задач P, NP:
NP – клас всіх задач пошуку.
P – клас задач пошуку, рішення для яких може бути швидко знайдено (за поліноміальний час).

Слайд 4

Теза Черча - Тьюринга
Будь-яка обчислювана функція обчислюється машиною Тьюринга.
Поліноміальні алгоритми існують

для багатьох задач.
Багато важливих задач для транспортних потоків («Математика транспортних потоків») допускають поліноміальні алгоритми.
Алгоритми, пов'язані з Інтернетом («Математика інтернету») є алгоритмами лише в широкому сенсі, так як самі задачі за своєю суттю динамічні і розподілені.
Всі алгоритми, що використовуються в криптографії – поліноміальні.
Алгоритми, що використовуються для стиснення даних, також є поліноміальними. Боротьба йде за поліпшення швидкості кодування і декодування всередині класу P - як і у випадку «великих даних», різниця між лінійними і, скажімо, квадратичними алгоритмами виявляється досить відчутною.

Слайд 5

Задача «від прогулянок по Кенігсбергу до реконструкції геному».
Перша половина XVIII

століття. Великий математик Леонард Ейлер розв’язує «задачу про Кенігсбергські мости» - доводить, що в Кенігсберзі, розташованому на берегах річки і двох її островах, не можна було пройти по кожному з семи мостів, що існували в той час, рівно один раз і повернутися після цього у вихідну точку. Подібний шлях на відповідному графі називається ейлеровим циклом. У задачі про існування ейлерова циклу критерій можливості розв'язання дуже простий - з кожної вершини графа має виходити парне число ребер. Та й задача знаходження ейлерова циклу (ЗЕЦ) вирішується відносно швидко навіть для дуже великого графа.
Друга половина XIX століття. Математик Вільям Гамільтон розглядає зовні схожу на ЗЕЦ задачу: знайти на графі замкнутий шлях (гамільтонів цикл), що проходить через кожну вершину по одному разу (ЗГЦ).
Друга половина XX століття. Було встановлено, що ЗГЦ (на відміну від ЗЕЦ) є представником класу задач, для яких ефективні алгоритми рішення невідомі.
Кінець XX століття - XXI століття. В середині 1990-х років був секвенірован геном бактерії, в 2001 році - людини. Робота була тривалою і дорогою, оскільки алгоритми суперкомп'ютерів грунтувалися на ЗГЦ. В останнє десятиліття математиками були розроблені швидкодіючі методи збирання, пов'язані з ЗЕЦ, і тепер біологи готуються до вирішення фундаментальної задачі: для кожного виду ссавців провести збірку генома.

Слайд 6

Твердження: P⊆PC. Доказ: оскільки детерміновані машини Тьюринга є частковим випадком не

детермінованих.
Отже, до детермінованих класів складності відноситься клас Р – це множина мов, що розпізнаються за поліноміальний час. Формально він визначається так:

Слайд 7

Існують більш високі класи. Крім класу P вивчають інші класи, які

визначаються порядком зростання часу роботи на машині Тьюринга:

Слайд 8

До класу NP відносяться недетерміновані машини Тьюрінга. Формально недетерміновані обчислення проводяться

на недетермінованій машині Тьюринга.
Клас NP є класом всіх задач розпізнавання, які можуть бути вирішені недетермінованими алгоритмами за поліноміальний час.

Слайд 9

NP-повнота
Якщо Р не збігається з NP, то відмінність між Р

і NP\P дуже істотна. Всі задачі з Р можуть бути вирішені поліноміальними алгоритмами, а всі задачі з NP\P складнорозв’язувані. Тому, якщо P≠NP, то для кожної конкретної задачі П∈NP важливо знати, яка з двох можливостей реалізується.

Слайд 10

Поняття поліноміальної зведеності
Основна ідея умовного підходу заснована на понятті поліноміальної зведеності.

Будемо говорити, що має місце поліноміальна зведеність мови L1⊆∑*1 до мови L2⊆∑*2, якщо існує функція f: → , що задовольняє, двом умовам:
1. Існує ДМТ-програма, що обчислює f p тимчасової складністю, обмеженою поліномом.
2. Для будь-якого х∈∑*1, х∈L1 в тому і тільки в тому випадку, якщо f(x)∈L2.
Якщо L1 поліноміально зводиться до L2, то будемо писати L1∞L2

Слайд 11

Лемма 1. Якщо L1∞L2, то з L2∈Р слідує, що L1∈Р. (Еквівалентне

твердження: з L1 Р слід, що L2 Р).
Якщо П1 і П2 - задачі розпізнавання, a e1 і е2 - їх схеми кодування, то будемо писати П1∞П2 (щодо заданих схем кодування), якщо існує поліноміальна зведеність мови L[П1, e1] к L[П2, e2] .
Таким чином, на рівні задач поліноміальної зведеності задачі розпізнавання П1 до задачі розпізнавання П2 означає наявність функції f:Dn1→Dn2, що задовольняє двом умовам:
(1) f обчислюється поліноміальним алгоритмом;
(2) для всіх І∈Dn, І∈Yn1, тоді і тільки тоді, коли f(I)∈Yn2

Слайд 12

Лемма 2. Якщо L1∞L2 та L2∞L3 , L1∞L3.
Лемма 2 стверджує, що

це відношення є відношенням еквівалентності, а також, що відношення ∞ визначає часткове впорядкування класів еквівалентності мов, що виникають (задач розпізнавання).

Слайд 13

Мова L називається NP-повною, якщо L∈NP і будь-яка інша мова L'∈NP

зводиться до мови L.
Pадача розпізнавання П називається NP-повної, якщо П∈NP і будь-яка інша задача розпізнавання П∈NP зводиться до П.
Якщо хоча б одна NP-повна задача може бути вирішена за поліноміальний час, то і всі задачі з NP також можуть бути вирішені за поліноміальний час.
Якщо хоча б одна задача з NP складнорозв’язувана, то і все NP-повні задачі складнорозв’язувані.

Слайд 14

$Будь-яка NP-повна задача П має властивість: якщо P≠NP, то П∈NP\P. Точніше,$

Будь-яка NP-повна задача П має властивість: якщо P≠NP, то П∈NP\P. Точніше,

П∈Р тоді і тільки тоді, коли Р=NP.
Зауважимо, що NP не просто поділяється на дві області: клас Р і клас NP-повних задач. Якщо Р відрізняється від NP, то повинні існувати задачі з NP, нерозв'язні за поліноміальний час і не є NP-повними.

Слайд 15

Приклади наближених алгоритмів для NP-повних задач
Алгоритм, який повертає рішення, близькі до

оптимальних, називається наближеним алгоритмом.

Слайд 16

Методи розв’язання NP-повних задач
Наближені та евристичні методи – застосування евристик для

вибору елементів рішення.
Псевдополіноміальні алгоритми – підклас динамічного програмування.
Метод локальних покращень – пошук більш оптимального рішення в околиці деякого поточного рішення.
Метод гілок і меж – відкидання свідомо неоптимальних рішень цілими класами відповідно до деякої оцінки.
Метод випадкового пошуку – представлення вибору послідовністю випадкових виборів.

Слайд 17

Метод локальних покращень
Розпочати з довільного рішення.
Для покращення поточного рішення застосувати до

нього будь-яке перетворення із заданої сукупності перетворень. Це покращене рішення стає поточним рішенням.
Повторити зазначену процедуру до тих пір, поки жодне з перетворень із заданої сукупності не дозволить поліпшити поточне рішення.
Якщо задана сукупність перетворень включає всі перетворення, то ми отримаємо точне (глобально-оптимальне) рішення.
На практиці сукупність перетворень обмежують. За допомогою них з ряду довільних рішень отримують локально-оптимальні рішення і вибирають з них краще.

Слайд 18

Метод гілок та меж
Вирішуючи дискретну екстремальну задачу, розіб'ємо множину всіх можливих

варіантів на класи і побудуємо оцінки для них.
В результаті стає можливим відкидати рішення цілими класами, якщо їх оцінка гірше деякого рекордного значення.

Слайд 19

Дискретна екстремальна (на мінімум) задача в загальному вигляді:
Нехай задано дискретну множину

А і визначено на ньому певна функція f. Позначимо мінімум функції f на Х як F(X).
Потрібно знайти x0∈A: f(x0)=F(A).

Слайд 20

Алгоритм методу:
Розіб'ємо множину А на підмножини Аі і на кожному з

них знайдемо нижню оцінку Φ.
Для елементів множини А будемо обчислювати значення функції f і запам'ятовувати найменше в якості рекордного значення f *.
Все підмножини, у яких оцінка вище f *, об'єднаємо в підмножину A0, щоб в подальшому не розглядати.
Оберемо будь-яке з множин Ai, i> 0. Розіб'ємо цю множину на більш дрібні підмножини. При цьому ми будемо продовжувати покращувати рекордне значення f *.
Цей процес триває до тих пір, поки не будуть переглянуті всі множини Ai, i> 0.

NP-складність і NP-повнота. Приклади наближених алгоритмів для NP-повних задач. Лекція 4

Содержание

ПитанняNP-складність задач.NP-повнота задач.Приклади наближених алгоритмів для NP-повних задач.

Задача пошуку (search problem) Задача пошуку (search problem) задається алгоритмом С,

Теза Черча - ТьюрингаБудь-яка обчислювана функція обчислюється машиною Тьюринга.Поліноміальні алгоритми існують

Задача «від прогулянок по Кенігсбергу до реконструкції геному». Перша половина XVIII

Твердження: P⊆PC. Доказ: оскільки детерміновані машини Тьюринга є частковим випадком не

Існують більш високі класи. Крім класу P вивчають інші класи, які

До класу NP відносяться недетерміновані машини Тьюрінга. Формально недетерміновані обчислення проводяться

NP-повнота Якщо Р не збігається з NP, то відмінність між Р

Поняття поліноміальної зведеностіОсновна ідея умовного підходу заснована на понятті поліноміальної зведеності.

Лемма 1. Якщо L1∞L2, то з L2∈Р слідує, що L1∈Р. (Еквівалентне

Лемма 2. Якщо L1∞L2 та L2∞L3 , L1∞L3.Лемма 2 стверджує, що

Мова L називається NP-повною, якщо L∈NP і будь-яка інша мова L'∈NP

Будь-яка NP-повна задача П має властивість: якщо P≠NP, то П∈NP\P. Точніше,

Приклади наближених алгоритмів для NP-повних задачАлгоритм, який повертає рішення, близькі до

Методи розв’язання NP-повних задачНаближені та евристичні методи – застосування евристик для

Метод локальних покращеньРозпочати з довільного рішення.Для покращення поточного рішення застосувати до

Метод гілок та межВирішуючи дискретну екстремальну задачу, розіб'ємо множину всіх можливих

Дискретна екстремальна (на мінімум) задача в загальному вигляді:Нехай задано дискретну множину

Алгоритм методу:Розіб'ємо множину А на підмножини Аі і на кожному з

Похожие презентации