Експоненційні алгоритми та перебір

Експоненційні алгоритми часто пов'язані з перебором різних варіантів розв'язання.

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

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

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

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

З рис.2 видно, що розв'язування задачі зводиться до перебору листків дерева з метою виявлення, які з них відповідають наборам, що перетворюють заданий булевий вираз на 1. Для виразу (x₁x₂) є х₃, такими наборами будуть 000, 010, 111.

Якщо n=3, дерево має 2³= 8 листів. У загальному ж випадку кількість можливих варіантів дорівнює 2ⁿ. Цей вираз експоненційно залежить від n, і перебірний алгоритм має експоненційний характер.

Описана вище схема алгоритму розв'язування цієї задачі має фундаментальний характер. Вона має назву бектрекінгу (інша назва - перебір з поверненням) і використовується для розв'язування найрізноманітніших перебірних задач (задача про вісім ферзів, задача про розфарбовування карти, автоматизація дедуктивних побудов тощо).

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

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

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

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

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

Машина Тьюринґа, що була описана А.Тьюринґом 193 6 року, є теоретичною моделлю обчислювальної машини. Машину Тьюринґа (МТ) (рисунок 3) слід розглядати як одну з можливих формалізацій поняття алгоритму. її робота може бути описана таким чином.

Розглянемо стрічку, розділену на окремі комірки; ця стрічка є потенційно нескінченною в обидва боки. У кожній комірці може бути записаний певний символ з деякого заданого алфавіту А. Машина Тьюринґа в будь-який момент часу може перебувати в певному стані (множина станів S є скінченною) і вказувати на певну комірку.

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

Програма машини Тьюринґа є послідовністю інструкцій, кожна з яких має вигляд

Цей запис читається так: якщо машина перебуває в стані s_l і зчитує символ a_i, вона повинна записати в поточну позицію символ a_k, перейти до стану s_m і зсунутися вправо (відповідає літері R), вліво (відповідає літері L) або зупинитися (відповідає літері H).

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

Приклад 1.9. Наведемо програму для машини Тьюринґа, яка обчислює функцію х+у, де х,у - натуральні числа. Необхідно домовитися про відображення цих чисел. Стандартним для машини Тьюринґа є подання натурального числа n послідовністю з n+1 одиниць.

Ідея реалізації такої програми могла б полягати у тому, щоб замінити крайній зліва та крайній справа символи ≪1≫ на ≪0≫, а роздільник ≪0≫ - на ≪1≫. Якби були доступні відповідні команди, це можна було б зробити просто і швидко, але ми обмежені жорсткими рамками машини Тьюринґа. За таких умов схема алгоритму полягає в такому: рухатися вправо до виявлення першої одиниці (початок першого числа); як тільки вона буде виявлена, замінити її на нуль і перейти в інший стан s₁. Потім рухатися вправо, поки 0, який розділяє два числа, не буде замінений на 1; при цьому знову змінити стан. Далі рухатися вправо до появи першого нуля (кінця другого доданку). Після цього зсунутися вліво, замінити останню 1 на 0 та зупинитися.

Наведений приклад показує, що машина Тьюринґа є дуже незручною для програмування. Ці незручності пов'язані з тим, що:

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

• неструктурованють записів на стрічці; заздалегідь невідомо, де закінчується одне число і починається інше;

• дуже обмежений набір команд; відсутні, наприклад, основні арифметичні операції.

Універсальну машину Тьюринґа можна неформально визначити як машину, яка може сприймати програму для обчислення будь-якої функції, яку, в принципі, можна обчислити за допомогою спеціалізованої машини М1 і надалі працювати, як машина М1. Можна довести, що таку машину можна побудувати.

Багатство можливостей конструкції Тьюринґа полягають у тому, що якщо якісь алгоритми А та В реалізуються машинами Тьюринґа, то можна будувати програми машин Тьюринґа, які реалізують композиції алгоритмів А та В, наприклад, виконати А, потім виконати В або виконати А знову. Якщо в результаті утворилося слово ≪так≫, то виконати В. У протилежному випадку не виконувати В або виконувати по черзі А, В, поки В не дасть відповідь ≪ні≫.

У інтуїтивному сенсі такі композиції є алгоритмами. Тому їхня реалізація за допомогою машини Тьюринґа служить одним із засобів обґрунтування універсальності конструкції Тьюринґа.

Реалізованість таких композицій доводиться у загальному вигляді, незалежно від особливостей конкретних алгоритмів А та В. Доведення полягає в тому, що вказується засіб побудови з програм А та В програми требаї композиції. Нехай, наприклад, треба побудувати машину А \cdot В, еквівалентну послідовному виконанню алгоритмів А та В. Поки виконується алгоритм А, у програмі A\cdot В працює частина А без урахування частини В. Коли алгоритм А дійде до кінця, то замість зупинки відбудеться перехід у перший стан частини В, і потім частина В буде працювати звичайним чином, наче частини А й не було.

Аналогічно конструюють й інші композиції машин Тьюринґа; щораз будуються загальні правила, які визначають, що на що змінювати у вихідних програмах.

Описуванняючи різноманітні алгоритми для машин Тьюринґа і стверджуючи реалізованість усіляких композицій алгоритмів, Тьюринґ переконливо показав розмаїтість можливостей запропонованої ним конструкції, що дозволило йому виступити з такою тезою:

Что делать, если нет взаимности? А теперь спустимся с небес на землю. Приземлились? Продолжаем разговор...

Что способствует осуществлению желаний? Стопроцентная, непоколебимая уверенность в своем...

ЧТО И КАК ПИСАЛИ О МОДЕ В ЖУРНАЛАХ НАЧАЛА XX ВЕКА Первый номер журнала «Аполлон» за 1909 г. начинался, по сути, с программного заявления редакции журнала...

Что делает отдел по эксплуатации и сопровождению ИС? Отвечает за сохранность данных (расписания копирования, копирование и пр.)...

Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте: