1.3. Пошук у глибину і пошук у ширину

Серед різноманітних методів, за допомогою яких можна органі­зовувати пошук потрібної вершини на дереві перебору, а відтак і шляху до неї, прийнято виокремлювати дві основні стратегії:

• пошук у ширину;

• пошук у глибину (інші назви — перебір з поверненнями; бектрекінг).

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

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

На рис. 2, а показана послідовність перегляду вершин при пошуку в ширину, а на рис. 2, б – при пошуку в глибину.

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

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

а) б)

Рис. 2. Процедура пошуку в ширину (а) та пошуку в глибину (б)

2. Простір задач і простір станів

Методики планування цілеспрямованих дій прийнято розподі­ляти на два класи: планування в просторі станів і планування в прос­торі задач.

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

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

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

Класичним прикладом планування в просторі станів можна вважати задачу пошуку шляху від одного міста до іншого.

Планування в просторі задач передбачає декомпозицію початкової задачі на підзадачі, поки не буде досягнуто зведення до задач, для яких є готові алгоритми вирішення. Таку декомпозицію зручно уявляти собі у ви­гляді І/АБО-графа.

Існують методики комбінування методів пошуку в просторі станів і в просторі задач.