Повна версія

Головна arrow Природознавство arrow ІНТЕЛЕКТУАЛЬНІ СИСТЕМИ

  • Увеличить шрифт
  • Уменьшить шрифт


<<   ЗМІСТ   >>

СТРАТЕГІЯ ПОШУКУ В ШИРИНУ

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

Ідея алгоритму пошуку в ширину полягає в наступному: початкова вершина графа приймається за початок вирішального шляху; а далі завжди, коли належить вибрати з декількох альтернативних вершин ту, в яку слід перейти з поточної вершини для продовження пошуку вирішального шляху, потрібно вибрати найменш «глибоку» з них, т. е. ту, яка розташована ближче інших до початкової вершини. Терміни «найменш глибока» і «ближче» тут також слід розуміти в сенсі «довжини» ребра. Зауважимо, на противагу пошуку в глибину стратегія пошуку в ширину вибирає на кожному кроці з усіх альтернативних вершин найближчу до початкової вершини.

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

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

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

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

Мал. 8

Виділений шлях [a, c, f - це перший знайдений вирішальний шлях, він же - найкоротший. Другим вирішальним шляхом є шлях а, Ь, е, /, що виходить продовженням пошуку в ширину. У цьому прикладі друге рішення виходить практично повним перебором. Також повний перебір буде потрібно, якщо необхідно побудувати все вирішальні шляхи.

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

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

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

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

 
<<   ЗМІСТ   >>