Повна версія

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

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


<<   ЗМІСТ   >>

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

Нехай деяка умовна завдання формалізована першим способом. Це означає, що задані

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

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

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

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

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

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

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

Виділені шляху [д, b, e, j] і [a, c, J] - це знайдені вирішальні шляхи, і [a, c, f - найкоротший вирішальний шлях, відшукувати, якщо продовжувати пошук в глибину до повного перебору всіх вершин графа .

Пошук в глибину часто працює добре, як в розглянутому прикладі на рис. 4, а. Але буває, що він дає збої, наприклад, зациклення, якщо не передбачений аналіз наявності циклів в орієнтованому графі простору станів розв'язуваної задачі. На рис. 4, б представлений граф, що містить цикли [d, h, d і ?, Е, i, Ь. Включення в алгоритм пошуку в глибину механізму виявлення циклів дозволить уникнути ситуацій зациклення. Механізм виявлення циклів повинен працювати так, щоб жодна з вершин, вже містяться в побудованому шляху, не розглядалася вдруге в якості можливої альтернативи продовження пошуку.

Мал. 4

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

Мал. 5

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

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

Найкоротша рішення виділено на рис. 6 жирними стрілками. Воно буде отримано подальшим продовженням пошуку рішень, поки не будуть знайдені всі рішення. Це продовження пошуку відзначено на рис. 6 пунктиром.

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

Пошук в глибину простий, легко програмується і найбільш адекватний рекурсивному стилю програмування, прийнятому в мові програмування Prolog. Останнє пояснюється тим, що, обробляючи мети, пролог-система переглядає альтернативи саме в глибину. Пошук в глибину (без механізму виявлення циклів) може бути запрограмований на мові Prolog наступним чином [9]:

вирішити (В, [В}): - мета (В).

вирішити (В, [В Реш 1]): - після (В, В]), вирішити (В1, Решт).

Рис. 7

Мал. 6 Рис. 7

Цей текст на мові Prolog означає: для того щоб знайти вирішальний шлях Реш (послідовність вершин у вигляді прологовского списку | В, 5 ,, ..., В до ) з початкової вершини В в деяку цільову вершину В до (цільові вершини А задаються фактами виду «мета (/ 4).»), необхідно:

  • - якщо В - це цільова вершина, то покласти Реш = [5],
  • - якщо для початкової вершини В існує вершина 51, в яку направлено ребро графа, що виходить з вершини В , то вирішальний шлях Реш = | 5 | РешЦ, де Реш 1 - вирішальний шлях, що починається з вершини 51 як з вихідної вершини.

Факти виду « після (В, В 1).» Визначають ребра, спрямовані з вершини В у вершину В 1. Предикат вирішити (В, Реш) описує взаємозв'язок між початковою вершиною В і вирішальним шляхом Реш, що починається з цієї вершини. Прологовская запис Реш = [В Реш 1] означає, що В - голова списку Реш, а Реш 1 - хвіст цього списку.

 
<<   ЗМІСТ   >>