Azərbaycanca
Беларускі
Dansk
Deutsch
Española
Français
Indonesia
Italiana
日本語
Қазақ
Lietuvos
Nederlands
Português
Русский
සිංහල
แบบไทย
Türkçe
Українська
中國人
United State
Afrikaans
Алгори́тм пошуку́ в глибину́ з ітеративним заглибленням (англ. 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, а при ітеративному заглибленні цього не відбувається. Результатом цього є те, що пошук з ітеративним заглибленням фактично здійснюється швидше, ніж пошук в ширину, незважаючи на повторне формування станів.
Наприклад, якщо b = 10 і d = 5, то відповідні оцінки кількості вузлів приймають наступні значення:
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.
Пошук з ітеративним заглибленням запобігає появі такого циклу і досягає таких вузлів на таких глибинах (припускаючи що пошук відбувається зліва направо, як і вище):
- 0: A
- 1: A (повторно), B, C, E
(Зауважимо, що пошуком з ітеративним заглибленням зараз розглядається C, коли звичайний пошук в глибину цього не зробив.)
- 2: A, B, D, F, C, G, E, F
(Відзначимо що пошук тепер бачить E через інший шлях, і петлі приходять до F двічі.)
- 3: A, B, D, F, E, C, G, E, F, B
Для цього графу, якщо буде додана більша глибина, два цикли "ABFE" і "AEFB" просто стануть довшими, перш ніж алгоритм здається і намагається пройти іншу гілку.
Алгоритм
Алгоритм пошуку з ітеративним заглибленням, в якому повторно застосовується пошук з обмеженням глибини при послідовному збільшенні меж. Він завершує свою роботу після того, як знаходиться розв'язок, або процедура пошуку з обмеженням глибини повертає значення failure, а це означає, що розв'язку не існує.
IDDFS(root, goal) { depth = 0 repeat { result = DLS(root, goal, depth) if (result is a solution) return result depth = depth + 1 } } Пошук з обмеженням глибини може здійснюватися рекурсивно наступним чином. Зверніть увагу, що потрібно тільки перевірити чи є вузол цільовим коли глибина нульова (depth == 0), тому що коли глибина більша за нуль (depth > 0), DLS(пошук з обмеженням глибини) відкриває вузли, які він вже проходив у попередній ітерації IDDFS(пошук з ітеративним заглибленням).
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). Річард Корф про "відкриття" Пошуку в глибину з ітеративним заглибленням:
 | Пошук в глибину з ітеративним заглибленням був без сумніву відкритий декілька разів незалежно один від одного. Перше використання алгоритму, що було задокументовано в літературі - це в програмі "Atkin's Chess 4.5 program". Берлінер відзначав, що пошук в ширину поступається алгоритму пошуку в глибину з ітеративним заглибленням. |  |
Споріднені алгоритми
Схожою до пошуку з ітеративним заглибленням є пошукова стратегія під назвою пошук з ітеративним подовженням. Такий пошук працює зі збільшенням(або обмеженням) вартості шляхів замість збільшення(обмеження) глибини. Він відкриває вузли в порядку зростання вартості шляху, тому першим цільовим вузлом є вузол з найдешевшою вартістю шляху. Але пошук з ітеративним подовженням несе істотні накладні витрати, що робить його менш корисним, ніж ітеративний пошук з заглибленням.
Література
Стюарт Рассел, Питер Норвиг Искусственный интеллект: современный подход. — М.: Вильямс, 2007. С. 1424.
Див. також
 | Це незавершена стаття про алгоритми. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algori tm poshuku v glibinu z iterativnim zagliblennyam angl Iterative deepening depth first search IDDFS algoritm dlya obhodu dereva Cej algoritm ye rozvinennyam algoritmu poshuku v glibinu Opis algoritmuPoshuk z iterativnim zagliblennyam abo tochnishe poshuk v glibinu z iterativnim zagliblennyam yavlyaye soboyu zagalnu strategiyu sho chasto vikoristovuyetsya v poyednanni z poshukom v glibinu yaka dozvolyaye znajti najkrashu mezhu glibini V dijsnosti v algoritmi poshuku v glibinu isnuye odna problema vibir pravilnoyi glibini na yakij treba zupinitis Yaksho vona bude zanadto maloyu to rozv yazok ne bude znajdeno yaksho zanadto velikoyu to mozhlivo bude marno vitracheno bagato chasu ta resursiv Ci problemi virishuyutsya shlyahom postupovogo zbilshennya mezhi kotra spochatku staye rivnoyu 0 potim 1 potim 2 i tak dali do tih pir poki ne bude znajdena cil Taka podiya vidbuvayetsya pislya togo yak mezha glibini dosyagaye znachennya d glibini samogo poverhnevogo cilovogo vuzla V poshuku z iterativnim zagliblennyam poyednuyutsya perevagi poshuku v glibinu ta poshuku v shirinu Yak i poshuk v glibinu vin harakterizuyetsya duzhe skromnimi vimogami do pam yati a same znachennyam O bd Yak i poshuk v shirinu vin ye povnim yaksho koeficiyent rozgaluzhennya ye skinchennim ta optimalnim yaksho vartist shlyahu yavlyaye soboyu nespadnu funkciyu glibini vuzla Vlastivosti algoritmuPoshuk z iterativnim zagliblennyam na pershij poglyad mozhe zdatisya marnotratnim oskilki odni j ti zh sami stani formuyutsya dekilka raziv tak yak poshuk kozhnogo razu pochinayetsya z pochatku Ale yak viyavilosya taki povtorni operaciyi ne ye zanadto dorogimi Prichina cogo v tomu sho v derevi poshuku z odnim i tim samim abo majzhe tim samim koeficiyentom rozgaluzhennya na kozhnomu rivni bilshist vuzliv znahodyatsya na nizhnomu rivni tomu ne maye velikogo znachennya te sho vuzli na verhnih rivnyah formuyutsya bagatorazovo V poshuku z iterativnim zagliblennyam vuzli na nizhnomu rivni z glibinoyu d formuyutsya odin raz ti vuzli sho znahodyatsya na rivni sho pereduye nizhnomu formuyutsya dvichi i tak dali azh do dochirnih vuzliv korenevogo vuzla kotri formuyutsya d raziv Tomu zagalna kilkist vuzliv sho formuyutsya virazhayetsya nastupnoyu formuloyu N IDS d b d 1 b2 1 bd yaka vidpovidaye chasovij skladnosti poryadku 0 bd Cyu kilkist mozhna porivnyati z kilkistyu vuzliv sho formuyutsya pri poshuku v shirinu N BFS b b2 bd bd 1 b Slid zaznachiti sho pri poshuku v shirinu deyaki vuzli formuyutsya na glibini d 1 a pri iterativnomu zagliblenni cogo ne vidbuvayetsya Rezultatom cogo ye te sho poshuk z iterativnim zagliblennyam faktichno zdijsnyuyetsya shvidshe nizh poshuk v shirinu nezvazhayuchi na povtorne formuvannya staniv Napriklad yaksho b 10 i d 5 to vidpovidni ocinki kilkosti vuzliv prijmayut nastupni znachennya 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 Vzagali kazhuchi iterativne zagliblennya ce metod neinformativnogo poshuku yakomu slid nadati perevagu v tih umovah koli nayavnij velikij prostir poshuku a glibina rozv yazku nevidoma Poshuk z iterativnim zagliblennyam analogichnij do poshuku v shirinu v tomu plani sho v nomu pri kozhnij iteraciyi pered perehodom na nastupnij riven doslidzhuyetsya povnij riven novih vuzliv PrikladDlya nastupnogo grafu poshuk v glibinu sho pochinayetsya z A pripuskayuchi sho livi vuzli v grafi obirayutsya pered pravimi i pripuskayuchi sho poshuk pam yataye ranishe vidvidani vuzli i ne bude prohoditi po nih znov bude prohoditi vuzli v takij poslidovnosti A B D F E C G Vikoristannya takogo zh poshuku ale ne pam yatayuchi vidvidanih vuzliv privede do prohodzhennya vuzliv v takomu poryadku A B D F E A B D F E i t d tobto poshuk potrapit do A B D F E ciklu i nikoli ne dosyagne C abo G Poshuk z iterativnim zagliblennyam zapobigaye poyavi takogo ciklu i dosyagaye takih vuzliv na takih glibinah pripuskayuchi sho poshuk vidbuvayetsya zliva napravo yak i vishe 0 A 1 A povtorno B C E Zauvazhimo sho poshukom z iterativnim zagliblennyam zaraz rozglyadayetsya C koli zvichajnij poshuk v glibinu cogo ne zrobiv 2 A B D F C G E F Vidznachimo sho poshuk teper bachit E cherez inshij shlyah i petli prihodyat do F dvichi 3 A B D F E C G E F B Dlya cogo grafu yaksho bude dodana bilsha glibina dva cikli ABFE i AEFB prosto stanut dovshimi persh nizh algoritm zdayetsya i namagayetsya projti inshu gilku AlgoritmAlgoritm poshuku z iterativnim zagliblennyam v yakomu povtorno zastosovuyetsya poshuk z obmezhennyam glibini pri poslidovnomu zbilshenni mezh Vin zavershuye svoyu robotu pislya togo yak znahoditsya rozv yazok abo procedura poshuku z obmezhennyam glibini povertaye znachennya failure a ce oznachaye sho rozv yazku ne isnuye IDDFS root goal depth 0 repeat result DLS root goal depth if result is a solution return result depth depth 1 Poshuk z obmezhennyam glibini mozhe zdijsnyuvatisya rekursivno nastupnim chinom Zvernit uvagu sho potribno tilki pereviriti chi ye vuzol cilovim koli glibina nulova depth 0 tomu sho koli glibina bilsha za nul depth gt 0 DLS poshuk z obmezhennyam glibini vidkrivaye vuzli yaki vin vzhe prohodiv u poperednij iteraciyi IDDFS poshuk z iterativnim zagliblennyam DLS node goal depth if depth 0 and node goal return node else if depth gt 0 for each child in expand node DLS child goal depth 1 else return no solution IstoriyaIterativne chi progresivne zagliblennya vpershe zgaduyetsya Adrianom De Grootom v disertaciyi Dumka ta vibir v shahah angl Thought and choice in chess Richard Korf pro vidkrittya Poshuku v glibinu z iterativnim zagliblennyam Poshuk v glibinu z iterativnim zagliblennyam buv bez sumnivu vidkritij dekilka raziv nezalezhno odin vid odnogo Pershe vikoristannya algoritmu sho bulo zadokumentovano v literaturi ce v programi Atkin s Chess 4 5 program Berliner vidznachav sho poshuk v shirinu postupayetsya algoritmu poshuku v glibinu z iterativnim zagliblennyam Sporidneni algoritmiShozhoyu do poshuku z iterativnim zagliblennyam ye poshukova strategiya pid nazvoyu poshuk z iterativnim podovzhennyam Takij poshuk pracyuye zi zbilshennyam abo obmezhennyam vartosti shlyahiv zamist zbilshennya obmezhennya glibini Vin vidkrivaye vuzli v poryadku zrostannya vartosti shlyahu tomu pershim cilovim vuzlom ye vuzol z najdeshevshoyu vartistyu shlyahu Ale poshuk z iterativnim podovzhennyam nese istotni nakladni vitrati sho robit jogo mensh korisnim nizh iterativnij poshuk z zagliblennyam LiteraturaStyuart Rassel Piter Norvig Iskusstvennyj intellekt sovremennyj podhod M Vilyams 2007 S 1424 ISBN 0 13 790395 2Div takozhSpisok algoritmiv Poshuk u shirinu Obhid dereva Ce nezavershena stattya pro algoritmi Vi mozhete dopomogti proyektu vipravivshi abo dopisavshi yiyi