1.1. Повний перебір
Існує очевидний і досить універсальний метод вирішення оптимізаційних задач, який може бути застосований, якщо множина припустимих рішень М обмежена. Це – метод повного перебору, який полягає у переборі всіх можливих варіантів. Метод дає гарантований розв'язок якщо множина М скінчена (ситуація, характерна для дискретного програмування), та існує ефективний алгоритм породження будь-якого елемента з М та обчислення на цьому елементі цільової функції.
Таким чином, ми маємо типову загальноінтелектуальну процедуру. Якщо інтелектуальна система потрапляє в нову ситуацію і намагається планувати подальші дії, вона може спробувати звести задачу планування цілеспрямованих дій до оптимізаційної задачі (для цього, очевидно, достатньо визначити множину припустимих рішень М і цільову функцію f(x)). Якщо ця вдається, повний перебір варіантів у більшості випадків дозволить отримати оптимальне рішення.
Але повний перебір має очевидний недолік: для більшості практичних ситуацій кількість варіантів, які доводиться перебирати, надто велика, і реалізувати метод за прийнятний час не вбачається можливим. Тому розвиваються методи і алгоритми, які дозволяють скоротити такий перебір.
У той самий час далеко не завжди слід шукати саме оптимальне рішення. Часто достатньо обмежитися рішенням субоптимальним (наближеним до оптимального) або просто припустимим. У таких випадках достатньо виробити якесь правило, яке б виключало застосування повного перебору і для більшості вхідних даних давало б прийнятний результат. У цьому полягає суть евристичних алгоритмів.
Втім далеко не будь-яка інтелектуальна задача припускає очевидне зведення до оптимізаційної, оскільки часто не вдається записати в явному вигляді цільову функцію або обмеження.
1.3. Евристичний пошук
Багато практичних задач може бути вирішено на основі евристичного пошуку, яким прийнято називати процедуру систематизованого перебору на основі послідовного аналізу можливих варіантів та оцінки їх наслідків. Можна навести таку загальну схему евристичного пошуку:
1. Вибрати певну дію з області можливих дій.
2. Здійснити дію; це приведе до зміни ситуації.
3. Оцінити нову ситуацію.
4. Якщо досягнуто успіху – кінець; якщо ні – повернутися на крок 1 і розпочати спочатку.
Здійснити дію можна реально (і тоді йдеться про стратегію спроб і помилок) або уявно (і тоді можна говорити про попереднє планування, яке повинно передувати дійсному прийняттю рішення).
Одним з важливих варіантів евристичного пошуку є метод послідовних поліпшень. Основну його ідею можна сформулювати так: якщо маємо певне наближення до рішення xk , то застосовуємо деяку процедуру переходу до іншого наближення xk+1, яке буде кращим за попереднє. На методі послідовних поліпшень грунтується більшість основних методів дослідження операцій.
Розглянемо задачу про виконуваність булевого виразу, яка формулюється так: для будь-якого булевого виразу від п змінних знайти хоча б один набір значень змінних (x1, ...,xn), за якого цей вираз приймає значення 1.
Найпростіша схема евристичного пошуку для цієї задачі може мати такий вигляд: спочатку надаємо одне з двох можливих значень (0 або 1) першій змінній х1, потім другій і т. д. Коли будуть розставлені значення всіх змінних, ми можемо визначити значення булевого виразу. Якщо він дорівнює 1, задача вирішена. Якщо ні – потрібно повернутися назад і змінити значення деяких змінних.
Можна інтерпретувати цю задачу як задачу пошуку на певному дереві перебору. Кожна вершина цього дерева відповідає певному набору встановлених значень x1, ...,xk. Ми можемо встановити змінну xk+1 в 0 або 1, тобто маємо вибір з двох дій. Тоді кожній з цих дій відповідає одна з двох дуг, які йдуть від цієї вершини. Вершина x1, ...,xk має двох синів x1, ...,xk 0 i x1, ...,xk 1.
Рис.1. Дерево перебору для задачі про виконуваність булевого виразу
При п = 3 дерево можливостей матиме вигляд, показаний на рис. 1 (вершини помічені наборами значень змінних, а дуги – рішеннями, які приймаються на черговому кроці). Вершини, що відповідають рішенням задачі для виразу (x1 x2) = x3, зафарбовані.
З рисунка видно, що вирішення задачі зводиться до перебору листів дерева з метою виявлення, які з них відповідають наборам, що перетворюють заданий булевий вираз у істинний. Для виразу (x1 x2) = х3 такими наборами будуть 000, 010, 100, 111.
Якщо п = 3, дерево має 23= 8 листів. У загальному ж випадку кількість можливих варіантів дорівнює 2n. Цей вираз експоненційно залежить від п і перебірний алгоритм має експоненційний характер.
Слід звернути увагу на те, що не будь-який перебірний алгоритм є експоненційним. Як приклад можна навести загальновідомий алгоритм пошуку найбільшого елемента в масиві. Незважаючи на його перебірний характер, він є не експоненційним, а лінійним.
Зі зростанням розмірності будь-який поліноміальний алгоритм стає ефективнішим, ніж будь-який експоненційний. Для лінійного алгоритму зростання швидкодії комп'ютера в 10 разів дозволяє за той же час розв'язати задачу, розмір якої в 10 разів перевищує попередню. Для експоненційного алгоритму з основою 2 цей же розмір можна збільшити лише на 3 одиниці.