3. Додають цей зв'язок і відповідний вузол в дерево.

4. Повторювати кроки 2, 3 до тих пір, поки всі вузли не опиняться в дереві.

5.3 Найкоротший маршрут

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3.1 Інші задачі пошуку найкоротшого маршруту

Описані вище алгоритми пошуку найкоротшого маршруту обчислювали всі найкоротші шляхи з кореневого вузла до всієї решти вузлів в мережі. Існує безліч інших типів задачі знаходження найкоротшого маршруту.

5.3.1.1 Двохточковий найкоротший маршрут

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

Інший спосіб полягає у використовуванні методу установки міток, який зупинявся б, коли буде знайдений шлях до кінцевого вузла. Алгоритм установки міток додає до дерева найкоротшого маршруту тільки ті шляхи, які обов'язково повинні в ньому знаходитися, отже, в той момент, коли алгоритм додасть кінцевий вузол в дерево, буде знайдений шуканий найкоротший маршрут. В алгоритмі, який обговорювався раніше, це відбувається, коли алгоритм видаляє кінцевий вузол із списку можливих вузлів.

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

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

5.3.1.2 Обчислення найкоротшого маршруту для всіх пар

У деяких програмах може бути потрібно швидко знайти найкоротший маршрут між всіма парами вузлів в мережі. Якщо потрібно обчислити велику частину з N² можливих шляхів, може бути швидше обчислити всі можливі шляхи замість того, щоб знаходити тільки ті, які потрібні.

Можна записати найкоротші маршрути, використовуючи два двовимірні масиви, Dist і InLinks. В комірці Dist[I][J] знаходиться найкоротший маршрут з вузла I у вузол J, а в комірці InLinks[I][J] - зв'язок, який веде до вузла J в найкоротшому шляху з вузла I у вузол J.

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

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

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

Легко зауважити, що найкоротший маршрут між вузлами J і K, який використовує тільки перші I вузлів, включає вузол I, тільки якщо Dist[J][K]> Dist[J][I]+Dist[I][K]. Інакше найкоротшим маршрутом буде попередній найкоротший маршрут, який використовував тільки перші I-1 вузлів. Це означає, що коли алгоритм розглядає вузол I, вимагається тільки перевірити виконання умови Dist[J][K]> Dist[J][I]+Dist[I][K]. Якщо ця умова виконується, алгоритм поновлює найкоротший маршрут з вузла J у вузол K. Інакше старий найкоротший маршрут між цими двома вузлами залишився б таким.

5.3.1.3 Штрафи за повороти

У деяких мережах, особливо мережах вулиць, корисно додати штраф і заборони на повороти. В мережі вулиць автомобіль повинен уповільнити рух перед тим, як виконати поворот. Поворот ліворуч може займати більше часу, ніж поворот праворуч, або рух вперед. Деякі повороти можуть бути заборонені або неможливі через наявність роздільної смуги. Ці аспекти можна врахувати, вводячи в мережу штрафи за повороти.

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

Поміщаючи інформацію про штрафи безпосередньо в конфігурацію мережі, уникають необхідності модифікувати алгоритми пошуку найкоротшого маршруту. Ці алгоритми знаходитимуть правильні найкоротші маршрути з врахуванням штрафів за повороти. При цьому доведеться все ж таки злегка змінити програми, щоб врахувати розбиття вузлів на декілька частин.

Попередній метод буде не дуже ефективним, якщо потрібно ввести штрафи за повороти для більшості вузлів в мережі. Буде краще створити абсолютно нову мережу, яка включатиме інформацію про штрафи.

Для кожного зв'язку між вузлами А і B в початковій мережі в новій мережі створюється вузол AB;

Якщо в початковій мережі відповідні зв'язки були сполучені, то отримані вузли також з'єднуються між собою. Наприклад, нехай в початковій мережі один зв'язок сполучав вузли А і B, а інший - вузли B і С. Тоді в новій мережі потрібно створити зв'язок, який сполучає вузол AB з вузлом BC;

Ціна нового зв'язку складається з ціни зв'язку в початковій мережі і штрафу за поворот.

5.3.2 Застосування методу пошуку найкоротшого маршруту

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

5.3.2.1 Розбиття на райони

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

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

5.3.2.2 Складання плану робіт

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

Деякі з цих задач можуть виконуватися одночасно, інші повинні виконуватися послідовно. Наприклад, можна одночасно проводити електрику і прокладати водопровід.

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

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

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

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

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

5.3.2.3 Планування колективної роботи

Нехай потрібно набрати декількох співробітників для відповідей на телефонні дзвінки, при цьому кожний з них буде зайнятий не весь день. При цьому потрібно, щоб сумарна зарплата була якнайменшою, і найнятий колектив співробітників відповідав на дзвінки з 9 ранку до 5 вечора.

Для побудови відповідної мережі, створюють один вузол для кожної робочої години. З'єднують ці вузли зв'язками, кожний з яких відповідає робочому часу співробітника. Якщо співробітник може працювати з 9 до 11, то зв'язок між вузлом 9:00 і вузлом 11:00, і присвоюють цьому зв'язку ціну, рівну зарплаті, одержуваній даним співробітником за відповідний час.

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

5.4 Максимальний потік

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

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

Для пошуку шляхів способів збільшення повного потоку, алгоритм перевіряє залишкову пропускну спроможність зв'язків. Залишкова пропускна спроможність зв'язку між вузлами I і J рівна максимальному додатковому потоку, який можна направити з вузла I у вузол J, використовуючи зв'язок між I і J і зв'язок між J і I. Цей сумарний потік може включати додатковий потік по зв'язку I-J, якщо в цьому зв'язку є резерв пропускної спроможності, або виключати частину потоку із зв'язку J-I, якщо по цьому зв'язку йде потік.

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

5.4.1 Застосування максимальних потоків

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

5.4.1.1 Непересічні шляхи

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

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

Потім обчислюють максимальний потік в мережі. Максимальний потік буде рівний кількості різних шляхів від джерела до стоку. Оскільки кожний зв'язок може нести одиничний потік, то жоден з шляхів, використаних при обчисленні максимального потоку, не може мати загальних зв'язків.

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

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

5.4.1.2 Розподіл робіт

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

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

Потім порівнюють навики кожного співробітника з навиками, необхідними для виконання кожного із завдань. Створюють зв'язок між кожним співробітником і кожним завданням, яке він здатний виконати, і присвоюють усім зв'язкам одиничну пропускну спроможність.

Створюють вузол-джерело і з'єднують його з кожним із співробітників зв'язком одиничної пропускної спроможності. Потім створюють вузол-стік і з'єднують з ним кожне завдання, знову за допомогою зв'язків з одиничною пропускною спроможністю.

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

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

6. Методи розробки алгоритмів

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

Алгоритми відшукання найкращого варіанту серед багатьох можливих називаються звичайно алгоритмами перебору. Задача програміста-розробника алгоритму ввести у алгоритм якомога більше „досвіду” - умов, що дозволяють зменшити кількість варіантів, які перебираються. Чим більш цілеспрямовано буде проводитись пошук, тим більше програма набуває інтелектуальних рис, тим швидше буде знайдено найкращий результат. Фактично більшість з методів є саме цілеспрямованим перебором варіантів і до „інтелектуальної” групи відноситься лише традиційно.

6.1 Метод частинних цілей

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

Наприклад задача сортування масиву прямим обміном. Алгоритм сортування зводиться до відшукання мінімуму у несортованій частині масиву та дописування його до сортованої частини.

Функція пошуку проекції точки на площину зводиться до двох:

пошуку рівняння прямої, перпендикулярної площині та такої, що проходить через задану точку;

пошуку точки перетину перпендикуляру та площини.

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

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

Ще один класичний приклад методу частинних цілей - „Ханойська вежа”.

Принц Шак'я-Муні (623-544 р.р. до Р.Хр.), якого ще називали Буддою, що означає „просвітлений”, під час одної з своїх подорожей заснував у Ханої (В'єтнам) монастир. У головному храмі монастиря стоїть три стержні. На одну з них Будда надягнув 64 дерев'яні диски, усі різного діаметру, причому найширший поклав униз, а решту впорядкував за зменшенням розміру.

Слід переставити піраміду з осі A на вісь C у тому ж порядку, користуючись віссю B, як допоміжною, та додержуючись наступних правил:

за один хід переставляти лише один диск з одної осі на іншу, а не декілька;

забороняється класти більший диск на менший, тобто впорядкованість на кожній осі має зберігатися.

Ченці монастиря перекладають, не зупиняючись ні на мить, щосекунди по одному диску й досі. Коли піраміду буде складено на осі C, наступить кінець світу.

Рекурсивний підхід до програмування можна застосувати, якщо розуміти вежу з n дисків, як вежу з n-1 диску, що стоїть ще на одному. Щоби переставити всю піраміду з A на C, слід n-1 - піраміду переставити з A на B, перекласти один - найбільший - диск з A на C, а потім n-1 - піраміду з B на C. Таким чином, якщо за дрібнішу задачу править та ж задача, тільки з меншим значенням параметрів, то ця форма алгоритму частинних цілей є рекурсивним алгоритмом.

Як переставити вежу з двох дисків з A на C?

переставити диск з A на B;

переставити диск з A на C;

переставити диск з B на C.

Повністю аналогічно, анітрохи не складніше, програмується повний алгоритм.

Щоби переставити вежу з n дисків (позначимо її B(n)) з A на C, слід:

B(n-1) переставити з A на B;

B(1) перекласти з A на C;

B(n-1) переставити з B на C;

Тому основна функція буде void Move (int n, int from, int to), де n - розмір піраміди (якщо n = 1, то це лише один диск); from, to - осі, між якими відбувається операція пересування.

Для програмування слід визначити множину осей. Нам треба буде їх назви виводити на друк, тому назвемо їх 1, 2, 3. Крім того, треба за двома заданими осями вміти визначати третю, щоб її використовувати як робочу. Це легко зробити за допомогою оператора:

third = 6 - from - to;

Результатом роботи програми при n = 1 будемо вважати виведення рядка тексту на екран:

„Переставити диск з ... на ...”.

Тепер програма, яка писатиме ченцям інструкцію на 600 мільярдів років наперед, матиме вигляд:

#include <iostream.h>

#define n 64

void Move(int, int, int);

void main(void)

{

Move (n, 1, 3); // Переставити піраміду з n дисків з 1-ї осі на 3-ю

}

void Move(int n, int from, int to)

{

int third;

if (n == 1)

cout << “Переставити диск з “ << from << “ на “ << to << endl;

else

{

third = 6 - from - to;

Move (n-1, from, third);

Move (1, from, to);

Move (n-1, third, to);

}

}

Усі рекурсивні алгоритми є реалізацією методу частинних цілей.

6.2 Динамічне програмування

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

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

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

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

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

6.3 Метод сходження

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

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

Розв'язок можна шукати різними шляхами. Але самим очевидним є відшукати спочатку просто який-небудь цикл, що може вважатися „хорошим”. Для цього, наприклад, можна з першого міста їхати у найближче, звідти - у найближче з тих, що залишилися і так далі. З останнього міста треба буде повернутися назад. Це - перша вершина. Далі можна спробувати поліпшити цей варіант. Якщо це вийде, то це буде нова висота. Найкоротший цикл шукається за допомогою досить складних алгоритмів.

Ще один приклад використання методу сходження - ітерації.

Знайти значення корінь квадратний для довільного дійсного x - u = sqrt(x).

Якщо u = sqrt(x), то x/u = u;

Якщо u < sqrt(x), то x/u > sqrt(x).

Тому будь-коли середнє між u та x/u ближче до sqrt(x), ніж u. Тому, почавши з будь-якого „близького” початкового значення u(0), можна поступово поліпшувати наближення: u(n+1) := ( u(n) + x / u(n) ) / 2 доти, поки не буде виконуватися умова |u(n)- x / u(n)| < eps.

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

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

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

6.4 Дерева розв'язків

Багато складних реальних задач можна змоделювати за допомогою дерев розв'язків. Кожний вузол дерева представляє один крок вирішення задачі. Кожна гілка в дереві представляє розв'язок, який веде до більш повного рішення. Листки є остаточним розв'язком. Мета полягає в тому, щоб знайти „найкращий шлях” від кореня дерева до листка при виконанні певних умов. Ці умови і значення поняття „найкращий” для шляху залежить від конкретної задачі.

Стратегію настільних ігор, таких як шахи, шашки, або „хрестики-нулики” можна змоделювати за допомогою дерев гри. Якщо в який-небудь момент гри існує 30 можливих ходів, то відповідний вузол у дереві гри матиме 30 гілок. Наприклад, для гри в „хрестики-нулики” кореневий вузол відповідає початковій позиції, при якій дошка порожня. Перший гравець може помістити хрестик в будь-яку з дев'яти кліток дошки. Кожному з цих дев'яти можливих ходів відповідає гілка дерева, яка виходить з кореня. Дев'ять вузлів на кінці цих гілок відповідають дев'яти різним позиціям після першого ходу гравця.

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

Як можна здогадатися, дерево гри навіть для такої простої гри росте дуже швидко. Якщо воно буде продовжувати рости таким чином, що кожний наступний вузол в дереві матиме на одну гілку менше попереднього, то повне дерево гри матиме 9! = 362880 листки. Тобто, в дереві буде 362880 можливих шляхів розв'язку, які відповідають можливим варіантам гри.

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

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

6.4.1 Мінімаксний пошук

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

Для кожного гравця, можна присвоїти кожній позиції один з чотирьох вагових коефіцієнтів. Якщо коефіцієнт рівний 4, то це значить, що гравець в цій позиції виграє. Якщо - 3, то з поточного положення на дошці неясно, хто з гравців виграє врешті-решт. 2 - означає, що позиція приводить до нічиєї. І, нарешті, - 1, означає, що виграє супротивник.

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

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

Програмно для визначення ваги позиції на дошці потрібна функція, яка рекурсивно викликає себе до тих пір, поки не відбудеться одна з трьох подій. По-перше, вона може дійти до позиції, в якій гравець виграє. В цьому випадку, вона присвоює позиції ваговий коефіцієнт 4, що вказує на виграш гравця, що виконав останній хід. По-друге, може знайти позицію, в якій жоден з гравців не може зробити наступний хід. Гра при цьому закінчується нічиєю, тому функція присвоює цій позиції - 2. І нарешті, функція може досягти заданої максимальної глибини рекурсії. В цьому випадку, процедура присвоює позиції - 3, що вказує на неможливість визначити переможця. Функція при цьому вибирає хід, який має якнайменшу вагу для супротивника.

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

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

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

6.4.2 Покращення пошуку в дереві гри

Якби для пошуку в дереві гри була б лише мінімаксна стратегія, то виконувати пошук у великих деревах було б дуже складно. Такі ігри, як шахи, настільки складні, що програма може провести пошук всього лише на декількох рівнях дерева. На щастя, існують декілька методів, які можна використати для пошуку у великих деревах.

По-перше, в програмі можуть бути записані початкові ходи, які вибрані експертами. Можна вирішити, що програма гри в „хрестики-нулики” повинна робити перший хід в центральну клітку. Це визначає першу гілку дерева гри, тому програма може ігнорувати всі шляхи, які не проходять через першу гілку. Це зменшує дерево гри в 9 разів.

Фактично, програмі не потрібно виконувати пошук в дереві до того, поки супротивник не зробить свій хід. У цей момент і комп'ютер, і супротивник вибрали кожний свою гілку, дерево, яке залишилося, стане набагато меншим, і міститиме менше ніж 7!=5040 шляхів. Прорахувавши наперед всього один хід, можна зменшити розмір дерева гри від четверті мільйона до менше ніж 5040 шляхів.

Аналогічно, можна записати відповіді на перші ходи, якщо супротивник ходить першим. Є дев'ять варіантів першого ходу, отже, потрібно записати дев'ять відповідних ходів. При цьому програмі не потрібно поводити пошук деревом, поки супротивник не зробить два ходи, а комп'ютер - один. Тоді дерево гри міститиме менше ніж 6! = 720 шляхів. Записано всього дев'ять ходів, а розмір дерева при цьому зменшується дуже сильно. Це ще один приклад просторово-часового компромісу. Використовування більшої кількості пам'яті зменшує час, необхідний для пошуку в дереві гри.

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

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

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

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

алгоритм програмний пошук сортування дані

6.4.3 Метод відпрацювання назад

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

Наприклад - пошук найкоротшого шляху. Буквально застосовуємо цей підхід у названій задачі. Дається граф, вершини якого - населені пункти, а кожній дузі приписано відстань між вершинами. Слід визначити найкоротший маршрут між двома заданими вершинами - a та b.

Визначивши відстані від b до найближчих, а вірніше, до усіх суміжних з нею вершин, шукаємо шляхи до цих вершин з a. Залишимо з усіх шляхів той, для якого сумарний шлях є найменшим.

Наступний приклад - сітковий графік, або бізнес-план. Для того, щоб у термін, визначений у контракті, здати замовнику роботу, слід вже за 3 дні підготувати зразки та надрукувати звіт. Щоб підготувати зразки, слід ще за день до того зробити ще деякі роботи. Щоб звіт було надруковано за три дні до терміну, слід почати друкувати щонайменше за три тижні двома принтерами. І так далі, аж до самого початку.

6.5 Програмування з поверненнями назад

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

6.5.1 Метод спроб та помилок

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

Розглянемо гру, в яку грають два гравці, наприклад, шахи, шашки чи „хрестики-нулики”. Гравці почергово роблять ходи, і стан гри відображається відповідним станом на дошці. Будемо вважати, що є скінчена кількість позицій на дошці і в грі передбачене певне „правило завершення”. З кожною такою грою можна асоціювати дерево, яке називається деревом гри. Кожний вузол такого дерева представляє певну позицію на дошці. Початкова позиція відповідає кореню дерева. Якщо позиція x асоціюється з вузлом n, тоді нащадки вузла n відповідають сукупності допустимих ходів із позиції x, і з кожним нащадком асоціюється відповідна результуюча позиція на дошці.

Листки цього дерева відповідають таким позиціям на дошці, з яких неможливо виконати хід, - або тому, що хтось з гравців вже отримав перемогу, або тому, що усі можливі ходи вже вичерпані. Кожному вузлу дерева відповідає певна ціна. На початку назначають ціни листкам. Нехай мова йде про гру „хрестики-нулики”. В такому випадку листкам назначається ціна -1, 0 і 1 в залежності від того, чи відповідає даній позиції програш, нічия або виграш.

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

Цей алгоритм покажемо на прикладі задачі, яка має назву „хід коня”.

На шахівниці nхn стоїть на полі (x, y) шаховий кінь. Слід знайти такий маршрут коня (який ходить згідно шахових правил), коли він обходить усю шахівницю, побувавши у кожній клітинці рівно один раз.

Загальна структура алгоритму буде така: на кожному кроці буде аналізуватися, чи можна ще зробити хід куди-небудь. Якщо так, то робимо хід, якщо ні, то повертаємося на один хід назад. Так робимо до тих пір, поки довжина ланцюга ходів не стане рівною n-1. Тоді це повний „хід коня”.

Загальний вигляд основної функції такого алгоритму:

// спроба ще одного ходу

{

// початкові установки

do

{

// вибір чергового ходу зі списку можливих ходів

if (хід годиться)

{

// запис ходу

if (дошку не заповнено)

{

// спроба ще одного ходу

if (невдача)

// витирання ходу

}

}

}

while (успішний хід) || (інших ходів немає)

}

Ця процедура є рекурсивною: зробивши свій хід, вона звертається до самої себе, передаючи сама собі, природно, нову позицію. Остаточна програма:

const n = 8; // Розмір щахівниці

// Масив допустимих ходів

int step[2][n] = {{2,1,-1,-2,-2,-1,1,2,},{1,2,2,1,-1,-2,-2,-1}};

// Дощка

int h[n][n] = {{0,0,0,0,0,0,0}, {0,0,0,0,0,0,0}, {0,0,0,0,0,0,0},

{0,0,0,0,0,0,0}, {0,0,0,0,0,0,0}, {0,0,0,0,0,0,0},

{0,0,0,0,0,0,0}, {0,0,0,0,0,0,0}};

bool Try(int, int, int);

void main(void)

{

bool Success; // Успішний хід

// Початкові координати коня

int x0 = 0;

int y0 = 0;

h[x0][y0] = 1;

Success = Try(2, x0, y0);

if (!Success)

cout << " Не вдалося ";

else

// Вивід результатів

}

bool Try(int i, int x, int y)

{

bool NextSuccess;

int u, v;

int k = 0; // Поточний можливий хід

do

{

NextSuccess = false;

// Визначення нового кроку за шаховими правилами

u = x + step[0][k];

v = y + step[1][k];

if ( (u>=0) && (u<n) && (v>=0) && (v<n) ) // Хід допустимий?

if (h[u][v]==0) // Поле не зайняте?

{

h[u][v] = i; // запис ходу

if (i<n*n)

{

NextSuccess = Try(i+1, u, v); // Наступний хід

if (!NextSuccess) // Хід неуспішний?

h[u][v] = 0; // Витирання ходу

}

else

NextSuccess = true;

}

k++;

}

while ( !NextSuccess && (k<8) );

return NextSuccess;

}

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

6.5.2 Реалізація пошуку з поверненням

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

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

1. Виграші є дійсними числами з обмеженого інтервалу, наприклад [-1, 1].

2. Константа більша, ніж будь-який додатній виграш, а - менша, ніж будь-який від'ємний виграш.

3. Дані типу modetype (тип режиму) можуть приймати два фіксовані значення - MIN, або MAX.

4. Передбачений тип даних boardtype (тип ігрової дошки), яка визначається способом представлення позицій на дошці.

5. Передбачена функція payoff (виграш), яка обчислює виграш для будь-якої позиції, яка є листком дерева.

float Search(boardtype B, modetype mode)

// Оцінює і повертає виграш для позиції В з передбачення,

// що наступним повинен ходити гравець 1 (mode=MAX) або гравець 2 (mode=MIN)

{

boardtype C; // нащадок позиції В

float Value; // тимчасове значення виграшу

if (B є листком) // 1

return payoff(B); // 2

else

{

if (mode==MAX) // 3

Value = -; // 4

Else

Value = ; // 5

For (для кожного сина С позиції В) // 6

{

if (mode==MAX) // 7

Value = max(Value, Search(C, MIN)); // 8

Else

Value = min(Value, Search(C, MAX)); // 9

return Value; // 10

}

}

}

6.5.3 Альфа-бета відсікання

Одна дуже проста умова дозволяє позбавитися від розгляду значної частини типового дерева гри. Цикл (6) в алгоритмі може ігнорувати певних нащадків, досить часто доволі велику їх кількість.

Загальне правило відсікання вузлів зв'язане з поняттям кінцевих і приблизних значень вузлів. Кінцеве значення - це то, що називають виграшем. Приблизне значення - це верхня межа значення вузла в режимі MIN, або нижня межа значення вузла в режимі MAX. Приведемо правила обчислення цих значень.

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

2. Якщо орієнтовне значення вузла в режимі MAX рівне v1, а кінцеве значення одного з його нащадків рівне v2, тоді встановити приблизне значення вузла рівним max(v1,v2). Якщо вузол знаходиться в режимі MIN - min(v1,v2).

3. Якщо p є вузлом в режимі MAX, і має батька q, а приблизні значення вузлів рівні v1 і v2, відповідно, причому v1<v2, тоді можна відсікти всіх нерозглянутих нащадків вузла p, якщо p є вузлом в режимі MAX, а q є, таким чином в режимі MIN, і v2<v1.

6.5.4 Метод гілок і границь

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