|
Пошук в глибину з ітеративним заглибленнямАлгори́тм пошуку́ в глибину́ з ітеративним заглибленням (англ. Iterative deepening depth-first search, IDDFS) — алгоритм для обходу дерева. Цей алгоритм є розвиненням алгоритму пошуку в глибину. Опис алгоритмуПошук з ітеративним заглибленням (або, точніше, пошук в глибину з ітеративним заглибленням) являє собою загальну стратегію, що часто використовується в поєднанні з пошуком в глибину, яка дозволяє знайти найкращу межу глибини. В дійсності в алгоритмі пошуку в глибину існує одна проблема - вибір правильної глибини, на якій треба зупинитись. Якщо вона буде занадто малою, то розв'язок не буде знайдено; якщо занадто великою, то можливо буде марно витрачено багато часу та ресурсів. Ці проблеми вирішуються шляхом поступового збільшення межі (котра спочатку стає рівною 0, потім 1, потім 2 і так далі) до тих пір, поки не буде знайдена ціль. Така подія відбувається після того, як межа глибини досягає значення d, глибини самого поверхневого цільового вузла. В пошуку з ітеративним заглибленням поєднуються переваги пошуку в глибину та пошуку в ширину. Як і пошук в глибину, він характеризується дуже скромними вимогами до пам'яті, а саме, значенням O(bd). Як і пошук в ширину, він є повним, якщо коефіцієнт розгалуження є скінченним, та оптимальним, якщо вартість шляху являє собою неспадну функцію глибини вузла. Властивості алгоритмуПошук з ітеративним заглибленням на перший погляд може здатися марнотратним, оскільки одні й ті ж самі стани формуються декілька разів (так як пошук кожного разу починається з початку). Але, як виявилося, такі повторні операції не є занадто дорогими. Причина цього в тому, що в дереві пошуку з одним і тим самим (або майже тим самим) коефіцієнтом розгалуження на кожному рівні більшість вузлів знаходяться на нижньому рівні, тому не має великого значення те, що вузли на верхніх рівнях формуються багаторазово. В пошуку з ітеративним заглибленням вузли на нижньому рівні (з глибиною d) формуються один раз, ті вузли, що знаходяться на рівні, що передує нижньому, формуються двічі, і так далі, аж до дочірніх вузлів кореневого вузла, котрі формуються d разів. Тому загальна кількість вузлів, що формуються, виражається наступною формулою: N(IDS) = (d)b + (d-1)b2 + … + (1)bd яка відповідає часовій складності порядку 0(bd). Цю кількість можна порівняти з кількістю вузлів, що формуються при пошуку в ширину: N(BFS) = b + b2 + … + bd + (bd+1-b) Слід зазначити, що при пошуку в ширину деякі вузли формуються на глибині d+1, а при ітеративному заглибленні цього не відбувається. Результатом цього є те, що пошук з ітеративним заглибленням фактично здійснюється швидше, ніж пошук в ширину, незважаючи на повторне формування станів.
W(IDS) = 50 + 400 + 3000 + 20 000 + 100 000 = 123 450 N(BFS) = 10 + 100 + 1000 + 10 000 + 100 000 + 999 990 = 1 111 100 Взагалі кажучи, ітеративне заглиблення - це метод неінформативного пошуку, якому слід надати перевагу в тих умовах, коли наявний великий простір пошуку, а глибина розв'язку невідома. Пошук з ітеративним заглибленням аналогічний до пошуку в ширину в тому плані, що в ньому при кожній ітерації перед переходом на наступний рівень досліджується повний рівень нових вузлів. ПрикладДля наступного графу:
пошук в глибину, що починається з A, припускаючи що ліві вузли в графі обираються перед правими, і припускаючи що пошук пам'ятає раніше відвідані вузли і не буде проходити по них знов, буде проходити вузли в такій послідовності: A, B, D, F, E, C, G. Використання такого ж пошуку, але не пам'ятаючи відвіданих вузлів, приведе до проходження вузлів в такому порядку: A, B, D, F, E, A, B, D, F, E, і т.д., тобто пошук потрапить до A, B, D, F , E циклу і ніколи не досягне C або G. Пошук з ітеративним заглибленням запобігає появі такого циклу і досягає таких вузлів на таких глибинах (припускаючи що пошук відбувається зліва направо, як і вище):
(Зауважимо, що пошуком з ітеративним заглибленням зараз розглядається C, коли звичайний пошук в глибину цього не зробив.)
(Відзначимо що пошук тепер бачить E через інший шлях, і петлі приходять до F двічі.)
Для цього графу, якщо буде додана більша глибина, два цикли "ABFE" і "AEFB" просто стануть довшими, перш ніж алгоритм здається і намагається пройти іншу гілку. АлгоритмАлгоритм пошуку з ітеративним заглибленням, в якому повторно застосовується пошук з обмеженням глибини при послідовному збільшенні меж. Він завершує свою роботу після того, як знаходиться розв'язок, або процедура пошуку з обмеженням глибини повертає значення failure, а це означає, що розв'язку не існує. IDDFS(root, goal)
{
depth = 0
repeat
{
result = DLS(root, goal, depth)
if (result is a solution)
return result
depth = depth + 1
}
}
Пошук з обмеженням глибини може здійснюватися рекурсивно наступним чином. Зверніть увагу, що потрібно тільки перевірити чи є вузол цільовим коли глибина нульова ( DLS(node, goal, depth)
{
if (depth == 0 and node == goal)
return node
else if (depth > 0)
for each child in expand(node)
DLS(child, goal, depth-1)
else
return no-solution
}
ІсторіяІтеративне чи прогресивне заглиблення вперше згадується Адріаном Де Гроотом в дисертації «Думка та вибір в шахах» (англ. Thought and choice in chess). Річард Корф про "відкриття" Пошуку в глибину з ітеративним заглибленням:
Споріднені алгоритмиСхожою до пошуку з ітеративним заглибленням є пошукова стратегія під назвою пошук з ітеративним подовженням. Такий пошук працює зі збільшенням(або обмеженням) вартості шляхів замість збільшення(обмеження) глибини. Він відкриває вузли в порядку зростання вартості шляху, тому першим цільовим вузлом є вузол з найдешевшою вартістю шляху. Але пошук з ітеративним подовженням несе істотні накладні витрати, що робить його менш корисним, ніж ітеративний пошук з заглибленням. ЛітератураСтюарт Рассел, Питер Норвиг Искусственный интеллект: современный подход. — М.: Вильямс, 2007. С. 1424. ISBN 0-13-790395-2 Див. також
|
