Приклад.

Розглянемо задачу про виконуваність булевого виразу, яка формулюється так: для будь-якого булевого виразу від n змінних знайти хоча б один набір значень змінних x₁… x_n, при якому цей вираз приймає значення 1.

Типова схема розв'язку цієї задачі може мати такий вигляд: спочатку надаємо одне з двох можливих значень (0 або 1) першій змінній x₁, потім другій і т.д. Коли будуть розставлені значення всіх змінних, ми можемо визначити значення булевого виразу. Якщо він дорівнює 1, задача вирішена. Якщо ні - потрібно повернутися назад і змінити значення деяких змінних.

Можна інтерпретувати цю задачу як задачу пошуку на певному дереві перебору. Кожна вершина цього дерева відповідає певному набору встановлених значень x₁ …, x_k . Ми можемо встановити змінну x _k+1 в 0 або 1, тобто маємо вибір з двох дій. Тоді кожній з цих дій відповідає одна з двох дуг, які йдуть від цієї вершини. Вершина x₁ …, x_k має двох синів x₁ …, x_k 0 і x₁ …, x _{k 1}.

При n=3 дерево можливостей матиме вигляд, показаний на мал. (вершини помічені наборами значень змінних, а дуги - рішеннями, які приймаються на черговому кроці). Вершини, що відповідають рішенням задачі для виразу (x1 x2) є x3, зафарбовані.

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

Зі зростанням розмірності будь-який поліноміальний алгоритм стає більш ефективним, ніж будь-який експоненційний. Для лінійного алгоритму зростання швидкодії комп'ютера в 10 разів дозволяє за той же час розв'язати задачу, розмір якої в 10 разів більший. Для експоненційного алгоритму з основою 2 цей же розмір можна збільшити лише на 3 одиниці.

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

<== попередня сторінка	\|	наступна сторінка ==>
Ємна та часова складність. Поліноміальна зв’язність.	\|	Класи P та NP

Не знайшли потрібну інформацію? Скористайтесь пошуком google:

Генерація сторінки за: 0.004 сек.