Пошук в просторі станів

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

Пошук в ширину

Пошук в ширину — один з базових алгоритмів, що є основою багатьох інших. Наприклад, алгоритм Дейкстри пошуку найкоротших шляхів з одної вершини і алгоритм Прима пошуку мінімального остового дерева можуть розглядатися як узагальнення пошуку в ширину. Оскільки дерево є звичайним неорієнтованим графом то розглядати приклад обходу в ширину будемо саме на графах. Згідно з цим алгоритмом обхід вершин заданого графа G здійснюється в порядку їх віддаленості від деякої заздалегідь обраної, або зазначеної як початкова, вершини a (називається коренем пошуку в ширину). Інакше кажучи, спочатку відвідується сама вершина a, потім всі вершини, суміжні з a, тобто ті, які знаходяться від неї на відстані в одне ребро, потім вершини, що знаходяться від a на відстані в два ребра, і так далі.

Рис. 1. Неорієнтований граф G поданий у вигляді дерева.

Пошук в ширину в неорієнтованому графі

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

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

Зауваження: під час проходження графа з допомогою алгоритму обходу в ширину, кожній з вершин зіставляєтьс ціле число (глибина пошуку в ширину). Тобто, починаючи з вершини a, приписуємо їй номер 0. Кожній вершині з оточення вершини 0 приписуємо номер 1. Розглядаємо по черзі оточення всіх вершин з номером 1 і кожної з вхідних в ці оточення вершин (тобто суміжних з 1), ще не занумерованих, приписуємо номер 2. Розглядаємо оточення всіх вершин з номером 2 і так далі, поки можливо.

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

Пошук в глибину

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

Пошук в глибину в неорієнтованому графі

У загальному випадку, коли ми перейшли в будь-яку вершину графа, в нашому випадку це вершина b, виникають два варіанти можливих дій:

1. Якщо всі ребра, інцидентні b, вже переглянуті, то повертаємося до батьківської вершини для b і продовжуємо пошук з цієї вершини. Вершина b з цього моменту називатиметься повністю сканованою.
2. Якщо існують не переглянуті ребра, інцидентні b, то вибираємо одне з таких ребер, наприклад, (b,d) і орієнтуємо його з b в d. Ребро (b,d) з цього моменту вважатиметься переглянутим. При цьому, необхідно розглянути два випадки: якщо d раніше не була пройдена, то використовуючи ребро (b,d) переходимо у вершину d і продовжуємо пошук з неї. В цьому випадку ребро (b,d) називається ребром дерева, а вершина b — батьком вершини d; якщо d раніше була пройдена, то продовжуємо пошук іншого не пройденого ребра, інцидентного b. В цьому випадку ребро (b,d) називається зворотним ребром.

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

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

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

Гра у вісім

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

Рис. 2. JS-демонстрація вирішення задачі "Гра у вісім"