ПЕРЕЛІК ЗНАНЬ ТА НАВИЧОК
Після опанування теми студент має знати:
• методи формування пояснень;
• види пояснень;
• продуктивність методів пошуку;
• різновиди алгоритму Apriori.
Має вміти:
• простежити й оцінити поводження системи;
• сформулювати задачі пошуку в просторі станів;
• охарактеризувати стратегію пошуку в просторі станів;
• здійснювати пошук асоціативних та секвенціальних закономірностей між пов’язаними подіями в базах знань.
ЗМІСТ ПИТАНЬ З ТЕМИ
7.1. Методи формування пояснень
Подання інформації про поводження ПСШІ в процесі формування ланцюжка логічного виведення пошуку рішення є важливим з таких причин:
— користувачі, котрі працюють із системою, мають потребу в підтвердженні того, що в кожному конкретному випадку рішення, до якого прийшла програма, в основному є коректним;
— інженери зі знань, які мають справу з формуванням бази знань, повинні переконатися, що сформульовані ними знання застосовано правильно, у тому числі й у випадку, коли існує прототип;
— експерти у ПРГ бажають простежити хід виведення рішень і спосіб використання тих відомостей, які з їхніх слів були введені в базу знань, що дозволить визначити, наскільки коректно відомості застосовуються в даній ситуації;
— програмісти, що супроводжують, налагоджують і модернізують систему, мають потребу в інструменті, що дозволяє зазирнути в «середину» системи на рівні більш високому, ніж виклик окремих мовних процедур.
— менеджер системи, який використовує експертну технологію, що зрештою несе відповідальність за наслідки рішення, прийнятого програмою, також має потребу в підтвердженні, що такі рішення є досить обґрунтованими.
Відсутність достатньої прозорості поводження системи не дозволить експерту вплинути на її продуктивність або дати пораду, як можна її підвищити. Простежування й оцінка поводження системи — завдання досить складне і для його виконання необхідні спільні зусилля експерта та фахівця з ПСШІ.
Для відображення послідовності дій ПСШІ і застосовуваних знань при побудові логічного виведення необхідні динамічні пояснення, тобто пояснення мають генеруватися в процесі виведення рішення. Для підвищення інтелектуальності експертної системи варто передбачити різні типи питань, на які користувач може одержати відповідь з різною детальністю пояснень.
Виокремлюють такі види пояснень:
• каузальні пояснення — найбільш важливі, розкривають причинно-наслідкові зв’язки між розглянутими поняттями, а також дозволяють спрямовувати процес розв’язання задачі на розуміння сутностей. Наприклад, для побудови умовиводів на підставі відношень спільності й відношень перетворення користувачеві необхідно пояснити, які логічні зв’язування використовувалися при побудові даного висновку і чому саме вони використовувалися системою;
• пояснення через закон — показують, на підставі якого закону, теорії або моделі побудовано висновок. При цьому пояснення будується на дедукції;
• функціональні пояснення (цільові, мотиваційні) будуються за принципом «X необхідно для імплікації Y», тобто виконувані системою кроки розуміються стосовно поставленої мети. Для цього слід закласти в систему знання експерта про ПРГ і знання про те, які відношення і чому активізуються в тому або іншому випадку.
Методи формування пояснень — призначені для пояснення вихідних даних у світлі закладених у систему знань і одержання відповідей на питання, як і чому система прийшла до певного висновку, чому вона розмірковувала саме так; чому рекомендація системи є правильною і т. ін.
Виокремлюють такі методи формування пояснень:
Метод фіксації ситуацій — є найбільш простим і базований на збереженні заздалегідь заготовлених текстів для фіксованого набору ситуацій. Ситуації, що потребують пояснення, виділяють під час проектування системи. З кожною ситуацією пов’язується деякий текст, що видається системою, якщо має місце відповідна ситуація. За використання такого методу формування пояснення керування їхнім породженням найчастіше здійснюється системою; при цьому підсистема пояснення не виокремлюється в окремий блок. Простота фіксації ситуацій є безсумнівною перевагою методу, а недоліки пов’язані з тим, що набір ситуацій, які пояснюються, зазвичай жорстко фіксується під час розроблення системи і його розширення вимагає додаткового програмування. Текст, що пояснює, алгоритмічно не залежить від ситуації, яка приводить до семантичних неузгодженостей при внесенні змін.
Метод трасування — використовується при породженні пояснень слід (трасу) судження, проведеного системою. Метод набув широкого використання для розроблення блоків пояснення в системах, базованих на поданні евристичного знання у формі продукцій. Слід цілеспрямованого судження являє собою ланцюжок правил, які застосовувалися. Можливості користувача зі вказівки того, що саме його цікавить, є обмеженими. Користувач може одержати пояснення того, навіщо потрібне досягнення певної мети (йому повідомляється правило, у якому ця мета знаходиться в позиції умови), а також пояснення того, як досягнення даної мети відбивається на постановці інших підцілей (йому повідомляється правило, у якому дана мета перебуває в позиції наслідку).
7.2. Пошук у просторі станів
Під час проектування інтелектуальної системи важливим є те, як здійснюється доступ до знань і як вони використовуються для пошуку рішення.
Пошук — процес формування системою послідовності дій, що дозволяють їй досягти своїх цілей. Перш ніж система зможе розпочати пошук рішень, має бути сформульована мета, а потім ця мета може використовуватися для формулювання задачі.
Процес розв’язання задач пошуку рішень в інтелектуальних системах, базованих на знаннях, як правило, являє собою розгляд
Стан — це колекція характеристик, що можуть використовуватися для визначення стану або статусу об’єкта.
Простір станів — це множина станів, за допомогою якої подаються переходи між станами, у яких може бути об’єкт. У результаті переходу об’єкт потрапляє з одного стану до іншого.
Простір станів зручно подавати у вигляді гіперграфа.
Гіперграф складається із множини вершин (вузлів) N і множини гіпердуг Н.
Вузол — це облікова структура даних, застосовувана для подання дерева пошуку. Кожен вузол має батьківський вузол, містить дані про стан і має різні допоміжні поля.
Листовий вузол — вузол, що не має нащадків у орієнтованому графі.
Периферія — колекція вузлів, що були сформовані, але ще не розгорнуті. Кожен елемент периферії являє собою лист.
Гіпердуга задається упорядкованою парою, у якій перший елемент є окремою вершиною з N, а другий — підмножиною множини N. Гіпердуги також називають k-коннекторами, де k — потужність множини породжених вершин.
Граф ТА/АБО (And/Or-Graph) — окремий випадок гіперграфа, у якому вузли з’єднані не окремими дугами, а множиною дуг. Щоб подати різні відношення графічно, на графах ТА/АБО розрізняють вузли: ТА (and) і АБО (or) (рис. 2.1.5). A ? B ? СA ? B ? С
Рис. 2.1.5. ТА/АБО-графи
ТА-вузли графа — вузли, що подають імплікацію передумов, пов’язаних оператором ТА. Дуги, що ведуть до цих вузлів, з’єднуються кривою. Крива, що з’єднує дуги, означає, що для доказу вузла мають бути істинними усі його передумови, з’єднані дугою.
АБО-вузли графа — вузли, що подають імплікацію передумов, пов’язаних оператором АБО. Дуги, які ведуть до цих вузлів, не
досить великої кількості різних варіантів рішень, кожне з яких можна зіставити певному стану.
Задачі пошуку в просторі станів можна сформулювати в термінах трьох найважливіших компонентів:
• вихідний стан проблеми;
• тест завершення — перевірка, чи досягнуто необхідний кінцевий стан або знайдено рішення проблеми;
• множина операцій, які можна використовувати для зміни поточного стану проблеми.
Простір пошуку може бути визначено такими під-аспектами: ? розміром простору пошуку — надає узагальнену характеристику складності задачі. Виокремлюють малі (до 10! станів) і великі (понад 10! станів) простори пошуку; ? глибиною простору пошуку — характеризується середнім числом послідовно застосовуваних правил, що перетворюють вихідні дані на кінцевий результат; ? шириною простору пошуку — середнім числом правил, придатних до виконання в поточному стані.
Стратегія пошуку в просторі станів — порядок, за яким відбувається розгортання станів. Стратегія пошуку має бути виражена у вигляді функції, що вибирає певним чином з периферії наступний вузол, який підлягає розгортанню. Хоча даний підхід концептуально є нескладним, він може виявитися дорогим з обчислювальної точки зору, оскільки функцію, передбачену в цій стратегії, можливо, доведеться застосувати до кожного елемента в зазначеній множині для вибору найкращого з них. Тому часто передбачається, що колекцію вузлів реалізовано у вигляді черги.
Стратегія прямого пошуку (forward chaining) — відповідає руху від вихідних вершин графа до цільової вершини.
Стратегія зворотного пошуку (backward chaining) — відповідає руху від цільової вершини до вихідних вершин. Якщо вершин-цілей мало, а вихідних багато, то зворотний пошук є більш природним і ефективним.
Стратегія двонаправленого пошуку (bi-directional chaining) — поєднує прямий пошук (рух від вихідних вершин до цільової) і зворотний пошук (рух від цільової вершини до вихідної) та намагається досягти певного загального для обох пошуків стану, зупиняючись після того, як два процеси пошуку зустрінуться на середині. У стратегії двонаправленого пошуку передбачається перевірка в одному чи в обох процесах пошуку кожного вузла перед його розгортанням для визначення того, чи не знаходиться він на периферії іншого дерева пошуку; у разі позитивного ре-
з’єднуються кривою, що вказує на те, що істина кожної з передумов є достатньою умовою для істинності висновку.
Часова складність двонаправленого пошуку визначається як Sk(b d/2 ), де b — коефіцієнт розгалуження (кількість вузлів на рівні), а d — глибина дерева пошуку (кількість рівнів). У пам’яті необхідно зберігати принаймні одне з дерев пошуку, для того щоб можна було виконати перевірку приналежності до іншого дерева, тому просторова складність також визначається як Sk(b d/2 ). Такі вимоги до простору є одним з найбільш істотних недоліків двонаправленого пошуку. Цей метод є повним за кінцевого коефіцієнта розгалуження b і оптимальним при однакових вартостях етапів, якщо обидва процеси пошуку здійснюються в ширину; інші сполучення методів можуть характеризуватися браком повноти або оптимальності того й іншого.
Схема пошуку на ТА/АБО-графі — спосіб руху по графу в напрямку, заданому стратегією пошуку. Розрізняють схеми сліпого (неінформованого) і спрямованого (інформованого) пошуків на графі, пов’язані з перебором альтернативних вершин-підцілей і організацією повернення.
На практиці сліпі методи пошуку використовують рідко, оскільки вони пов’язані з великими витратами ресурсів через комбінаторний вибух. Спрямовані методи пошуку використовують як оцінювання придатних альтернатив, так і точок повернення, тобто забезпечують керування поверненням.
Після вибору стратегії пошуку (на основі даних або від мети), оцінки графа і вибору методу пошуку подальший хід рішення буде залежати від конкретного завдання.
Результатом застосування будь-якого методу розв’язання задачі є або невдале завершення, або одержання рішення. Деякі методи можуть входити в нескінченний цикл і не давати жодного результату.
Методи пошуку на графах використовують ідеї пошуку з поверненнями.
Метод пошуку з поверненнями (backtracking) — це метод систематичної перевірки різних шляхів у просторі станів, за якого формується список недосліджених станів Open, для того щоб мати можливість повернутися до кожного з них; підтримується список переглянутих «невдалих» станів Closed, щоб застерегти метод від перевірки марних шляхів; підтримується список вузлів поточного шляху, що повертається після досягнення мети; кожен новий стан перевіряється на входження в ці списки, щоб запобігти зацикленню.
зультату перевірки вважається, що рішення знайдено. Перевірка приналежності вузла до іншого дерева пошуку може бути виконана за постійний час за допомогою хеш-таблиці.
Пошук з поверненнями запускається з початкового стану і проводиться певним шляхом доти, поки не досягне мети або не зайде в глухий кут. Якщо ціль досягнуто, пошук завершується, і як розв’язок задачі повертається шлях до цілі. Якщо ж пошук привів у тупикову вершину, то метод повертається в найближчу з пройдених вершин і досліджує всі її вершини-сестри, а потім спускається по одній з гілок, що ведуть від вершини-сестри. Цей процес описується таким рекурсивним правилом.
Якщо вихідний стан не задовольняє вимог цілі, то зі списку його нащадків обираємо першого нащадка, і до цієї вершини рекурсивно застосовуємо процедуру пошуку з поверненнями. Якщо в результаті пошуку з поверненнями в підграфі з коренем першого нащадка ціль не виявлено, то повторюємо процедуру для вершини-сестри — другого нащадка вихідного стану. Ця процедура триває доти, поки один з нащадків розглянутої вершини-сестри не виявиться цільовим вузлом, або не з’ясується, що розглянуто уже всіх можливих нащадків (усіх вершин-сестер). Якщо ж жодна з вершин-сестер вихідної вершини не привела до цілі, то повертаємося до предка вихідної вершини і повторюємо процедуру з вершиною-сестрою вихідної вершини і т. д.
Продуктивність методів пошуку оцінюють за допомогою таких показників:
• повнота — визначає гарантію виявлення методом рішення, якщо воно існує;
• оптимальність — властивість забезпечення методом знаходження оптимального рішення;
• часова складність — оцінка часу, за який метод знаходить рішення;
• просторова складність — оцінка обсягу пам’яті, необхідного для здійснення пошуку.
Часова і просторова складність завжди аналізуються з урахуванням визначеного критерію виміру складності задачі. Типовим критерієм для комп’ютерних наук є розмір графа простору станів, оскільки цей граф розглядається як явно задана структура даних, що є вхідною для програми пошуку. У штучному інтелекті, де граф іноді подається неявно за допомогою початкового стану та функції визначення нащадка і часто є нескінченним, складність виражається в термінах трьох величин: b — коефіцієнт розгалуження або максимальна кількість нащадків будь-якого вузла, d — глибина найповерхневішого цільового вузла та m — максимальна довжина будь-якого шляху в просторі станів. Часова складність часто виміряється в термінах кількості вузлів, вироб-
Пошуковий метод є допустимим, якщо для будь-якого графа він завжди обирає оптимальний шлях до рішення.
Ефективність методів пошуку визначається вартістю пошуку, що зазвичай залежить від часової складності, але може також включати вираз для оцінки використання пам’яті, або сумарною вартістю, у якій поєднуються вартість пошуку і вартість шляху знайденого рішення.
Стратегії неінформованого (сліпого) пошуку — стратегії, що не використовують додаткову інформацію про стани, крім тієї, котра подана у визначенні задачі. Вони здатні тільки виробляти нові стани-нащадки і відрізняти цільовий стан від нецільового.
Метод породження і перевірки (generate-and-test).
Крок 1. Генерувати новий стан, модифікуючи наявний.
Крок 2. Перевірити, чи не є стан кінцевим (рішенням). Якщо це так, то завершити роботу, інакше перейти до кроку 1.
Метод породження і перевірки має два основні варіанти: пошук у глибину та пошук у ширину. Відрізняються варіанти порядком формування станів на кроці 1.
Метод пошуку в ширину (breadth-first search) — це стратегія, у якій простір станів послідовно проглядається за рівнями: на кожному рівні, у свою чергу, послідовно проглядаються стани, подані вузлами цього рівня один за одним, і тільки якщо станів на даному рівні більше немає, метод переходить до наступного рівня (див. рис. 2.16 — пунктиром показано порядок перегляду вузлів).
Рис. 2.16. Граф, що демонструє роботу методу пошуку в ширину
люваних у процесі пошуку, а просторова складність — у термінах максимальної кількості вузлів, збережених у пам’яті.
Нехай s — вузол початкового стану, Open — список, що містить обрані, але необроблені вузли; Closed — список, що містить оброблені вузли. Тоді метод пошуку в ширину буде полягати у виконанні таких кроків:
Крок 1. Ініціалізація. Установити: Open = {s}, Closed = ?.
Крок 2. Якщо Open = ?, то припинити виконання — шляху до цільового стану на графі не існує; у протилежному випадку — перейти до кроку 3.
Крок 3. Видалити з Open крайній ліворуч стан x.
Крок 4. Якщо x — ціль, то закінчити пошук і сформувати результат — шлях, породжений простежуванням покажчиків від вузла x до вузла s; у протилежному випадку виконати кроки 4.1–4.4.
Крок 4.1. Згенерувати стан-нащадок x.
Крок 4.2. Помістити x у список Closed.
Крок 4.3. Виконати перевірку на цикл — виключити нащадок x, якщо він уже є в списку Open або Closed.
Крок 4.4. Помістити інші нащадки в правий кінець списку Open, створюючи в такий спосіб чергу.
Крок 5. Перейти до кроку 2.
На кожній ітерації методу пошуку в ширину генеруються всі дочірні вершини стану x і записуються в список Open, що діє як черга й обробляє дані в порядку надходження: стани додаються в список праворуч, а видаляються ліворуч. У такий спосіб у пошуку беруть участь стани, що знаходяться в списку Open найдовше, забезпечуючи пошук у ширину. Дочірні стани, що були вже записані в списки Open або Closed, відкидаються.
Коли ціль знайдено, метод може відновити шлях рішення, простежуючи його у зворотному напрямі від мети до початкового стану по батьківських станах. Оскільки пошук у ширину знаходить кожний стан за найкоротшим шляхом і зберігає першу версію кожного стану, цей шлях від початку до цілі є найкоротшим. Методи, що мають таку властивість, називають розв’язними (admissible).
Пошук у ширину є повним, оптимальним за однакових вартостей етапів і характеризується часовою та просторовою складністю Sk(b d+1 ), де b — кількість вузлів на рівні, d — кількість рівнів. У зв’язку з такою просторовою складністю в більшості випадків він стає практично незастосовним. За пошуку в ширину найбільш складною проблемою порівняно зі значним часом виконання є забезпечення потреб у пам’яті. Загалом задачі пошуку з експонентною складністю неможливо вирішити за допомогою неінформованих методів у всіх екземплярах цих задач, крім найменших.
Метод пошуку за критерієм вартості — модифікація пошуку в ширину, що є оптимальною за будь-якої функції визначення вартості етапу. При пошуку за критерієм вартості враховується не кількість етапів, що є у шляху, а тільки їх сумарна вартість. Якщо вартості всіх етапів є рівними, такий пошук ідентичний пошуку в ширину. Він є повним, якщо коефіцієнт розгалуження b є кінцевим, і оптимальним, якщо вартість кожного кроку перевищує певне позитивне граничне значення е — ця умова означає, що вартість шляху завжди зростає в міру проходження цим шляхом.
Метод розгортає вузли в порядку зростання вартості шляху, віддаючи пріоритет розгортанню вузла з найменшою вартістю шляху. Тому перший цільовий вузол, обраний для розгортання, являє собою оптимальне рішення.
Пошук за критерієм вартості спрямовується з урахуванням вартостей шляхів, а не значень глибини в дереві пошуку, тому його складність не може бути легко охарактеризована в термінах b і d.
Часова і просторова складність цього методу в найгіршому виякій переглядаються стани на одному шляху — розгортається найглибший вузол у поточній периферії дерева пошуку, у результаті чого пошук безпосередньо переходить на найглибший рівень дерева пошуку, на якому вузли не мають нащадків. У міру того, як ці вузли розгортаються, вони видаляються з периферії, тому надалі пошук переходить до наступного найповерхневішого вузла, що все ще має недосліджених нащадків (див. рис. 2.17
падку становить [] eC bSk */1+ , тобто може бути набагато більшою, ніж d , де С * — вартість оптимального рішення, е — вартість кожної дії. Це пов’язано з тим, що процедури пошуку за критерієм вартості можуть і часто виконують перевірку великих дерев, які складаються з дрібних етапів, перш ніж перейти до дослідження шляхів, у котрі входять великі, але, можливо, більш корисні етапи. Безумовно, як[] () deC bbSk= +/*1 . що усі вартості етапів є рівними, то [] deC bbSk= +/*1 . що усі вартості етапів є рівними, то [] deC bbSk= +/*1 . падку становить [] () eC bSk */1+ , тобто може бути набагато більшою, ніж b d , де С * — вартість оптимального рішення, е — вартість кожної дії. Це пов’язано з тим, що процедури пошуку за критерієм вартості можуть і часто виконують перевірку великих дерев, які складаються з дрібних етапів, перш ніж перейти до дослідження шляхів, у котрі входять великі, але, можливо, більш корисні етапи. Безумовно, якщо усі вартості етапів є рівними, то [] () deC bbSk= +/*1 .
Метод пошуку в глибину (depth-first search)
— це стратегія, у
— пунктиром показано порядок перегляду вузлів).
Нехай s — вузол початкового стану, Open — список, що містить обрані, але необроблені вузли; Closed — список, що містить оброблені вузли. Тоді метод пошуку в глибину буде полягати у виконанні таких кроків:
Крок 1. Ініціалізація. Установити: Open = {s}, Closed = ?.
Крок 2. Якщо Open = ?, то припинити виконання — шляху до цільового стану на графі не існує; у протилежному випадку — перейти до кроку 3.
Крок 2. Якщо Open = ?, то припинити виконання — шляху до цільового стану на графі не існує; у протилежному випадку — перейти до кроку 3.
Крок 1. Ініціалізація. Установити: Open = {s}, Closed = ?.
Крок 2. Якщо Open = ?, то припинити виконання — шляху до цільового стану на графі не існує; у протилежному випадку — перейти до кроку 3.
Крок 3. Видалити з Open крайній ліворуч стан x.
Крок 4. Якщо x — ціль, то закінчити пошук і сформувати результат — шлях, породжений простежуванням покажчиків від вузла x до вузла s; у протилежному разі — виконати кроки 4.1—4.4.
Крок 4.1. Згенерувати стан-нащадок x.
Крок 4.2. Помістити x у список Closed.
Крок 4.3. Виконати перевірку на цикл — виключити нащадок x, якщо він уже є в списку Open або Closed.
Крок 4.4. Помістити інші нащадки в лівий кінець списку Open, створюючи в такий спосіб стек.
Крок 5. Перейти до кроку 2.
Рис. 2.17. Граф, що демонструє роботу методу пошуку в глибину
При пошуку в глибину після дослідження стану спочатку необхідно оцінити всіх його нащадків та їхніх нащадків, а потім досліджувати кожну з вершин-сестер. Пошук у глибину за можливістю поглиблюється в зону пошуку. Якщо подальші нащадки стану не знайдені, розглядаються вершини-сестри. У цьому методі стани-нащадки додаються і видаляються з лівого кінця списку Open, тобто список Open реалізований як стек магазинного типу. У разі організації списку Open у вигляді стека перевага віддається «наймолодшим» (нещодавно згенерованим станам).
Пошук у глибину не є ні повним, ані оптимальним і характеризується часовою складністю Sk(b m ) та просторовою складністю Sk(bm), де b — коефіцієнт розгалуження, m — максимальна глибина будь-якого шляху в просторі станів.
Пошук у глибину швидко проникає в глибини простору. Якщо відомо, що шлях рішення буде довгим, то пошук у глибину не витрачатиме час на пошук великої кількості поверхневих станів на графі.
Пошук у глибину ефективний для зон пошуку з високим ступенем зв’язаності, оскільки йому не потрібно запам’ятовувати усі вузли даного рівня в списку Open.
Недоліком пошуку в глибину є те, що в ньому може бути зроблено неправильний вибір і перехід у тупикову ситуацію, пов’язану з проходженням униз по дуже довгому (чи навіть нескінченному) шляху, тоді як інший варіант міг би привести до рішення, що знаходиться недалеко від кореня дерева пошуку.
Метод пошуку з поверненнями — один з варіантів пошуку в глибину, що використовує менше пам’яті. При пошуку з поверненнями щоразу формується тільки один нащадок, а не всі разом; у кожному частково розгорнутому вузлі запам’ятовується інформація про те, який нащадок має бути сформований наступним. Отже, потрібно тільки Sk(m) пам’яті, а не Sk(bm). За пошуку з поверненнями застосовується ще один прийом, який дає змогу заощаджувати пам’ять (і час); ідея його полягає в тому, що при формуванні нащадка має безпосередньо модифікуватися опис поточного стану, а не здійснюватись його попереднє копіювання. При цьому потреба в пам’яті скорочується до обсягу, необхідного для збереження тільки одного опису стану і Sk(m) дій. Однак для успішного застосування даного прийому потрібно мати можливість скасовувати кожну модифікацію при поверненні, виконуваному для формування наступного нащадка. У розв’язанні задач з об’ємними описами станів застосування зазначених методів модифікації стає найважливішим фактором успіху.
Метод пошуку з обмеженням глибини — проста модифікація рекурсивного методу пошуку в глибину. Під час пошуку з обмеженням глибини на пошук у глибину накладається встановлена межа глибини l. Це означає, що вузли на глибині l розглядаються так, ніби вони не мали нащадків.
Функція RDLS(вузол node, межа глибини l) повертає рішення result або індикатор невдачі: failure (указує на відсутність рішення), cutoff (свідчить про те, що на заданій межі глибини рішення немає).
Початковий виклик функції: RDLS (початковий стан node, l).
Крок 1. Установити прапор відсутності рішення на поточній
глибині: cutoff_occurred = хибність.глибині: cutoff_occurred = хибність.
Крок 2. Якщо вузол node є цільовим, то зупинення, повернути як рішення вузол node.
Крок 3. Якщо глибина вузла node дорівнює l, то зупинення, повернути як рішення індикатор невдачі cutoff.
Крок 4. Згенерувати нащадків вузла node. Для кожного нащадка successor вузла node виконувати кроки 4.1–4.2.
Крок 4.1. Установити: result = RDLS (successor, l).
Крок 4.2. Якщо result = cutoff, то установити: cutoff_occurred = true, у противному випадку — якщо result ? failure, то зупинення, повернути як рішення result.
Крок 5. Якщо cutoff_occurred = true, то зупинення, повернути індикатор невдачі cutoff; у протилежному випадку — зупинення, повернути індикатор невдачі failure.
Застосування межі глибини дозволяє вирішити проблему нескінченного шляху. На жаль, у цьому підході також уводиться додаткове джерело неповноти, якщо буде обране значення l < d, іншими словами, якщо найповерхневіша ціль виходить за межі глибини. Така ситуація цілком імовірна, якщо значення d невідомо. Крім того, пошук з обмеженням глибини буде неоптимальним при виборі значення l > d. Його часова складність дорівнює Sk(b l ), а просторова складність — Sk(bl). Пошук у глибину може розглядатись як окремий випадок пошуку з обмеженням глибини, за якого l = ?.
Метод пошуку в глибину з ітеративним поглибленням — загальна стратегія, що дозволяє знайти найкращу межу глибини. Це досягається поступовим збільшенням межі глибини від 0 із кроком 1 доти, поки не буде знайдено ціль. Така подія відбувається після того, як межа глибини досягає значення d — глибини найбільш поверхневого цільового вузла. На кожній ітерації метод виконує пошук у глибину з урахуванням поточного граничного числа рівнів. При цьому при переході від однієї ітерації до іншої інформація про простір станів не зберігається. Метод припускає виконання таких кроків:
Крок 1. Установити поточний рівень глибини: d = 0.
Крок 2. Установити: result = RDLS (початковий вузол, d).
Крок 3. Якщо result ? cutoff, то зупинення, повернути як рішення result.
Крок 4. Установити: d = d + 1. Перейти до кроку 2.
Пошук з ітеративним поглибленням повторно застосовує пошук з обмеженням глибини, реалізований функцією RDLS, за послідовного збільшення меж. Він завершує свою роботу після того, як виявляється рішення, або функція пошуку з обмеженням
