Пошук з вертанням (англ. backtracking), також пошук з поверненням — загальний алгоритм для знаходження всіх (або деяких) розв'язків деякої обчислювальної задачі, який поступово будує кандидатів на розв'язок, і відкидає кожного неповного кандидата c («вертається») як тільки визначає, що c не може бути доповненим до вірного розв'язку.
Огляд
Класичний приклад використання пошуку з вертанням — це задача про вісім ферзів, в який потрібно знайти розташування восьми ферзів на стандартній шахівниці таким чином, щоб жоден ферзь не атакував іншого. В звичайному підході пошуку з вертанням, неповні кандидати це розташування k ферзів в перших k рядах дошки, всі в різних рядах і стовпцях. Будь-який неповний розв'язок, що містить два ферзі, які атакують один одного має бути відкинутий, бо він не може бути доведеним до повного правильного розв'язку.
Пошук з вертанням може бути застосований тільки до задач, що дозволяють поняття «неповних кандидатів на розв'язок» і порівняно швидку перевірку на можливість доповнення кандидата до вірного розв'язку. Це корисно, наприклад, для знаходження значення у невпорядкованій таблиці. За можливості застосування, пошук з вертанням часто значно швидший ніж повний перебір всіх можливих кандидатів, через виключення великої кількості кандидатів однією перевіркою.
Пошук з вертанням — це важливе знаряддя для розв'язання проблеми відповідності обмеженням, таких як кросворди, судоку та багато інших головоломок. Часто це найзручніший (якщо не найефективніший) підхід для розбору, для задачі пакування рюкзака та інших задач комбінаторної оптимізації. Це також базис для так званих мов логічного програмування таких як Icon, Planner і Prolog. Пошук з вертанням також використовується в рушії змін (diff) для програмного забезпечення MediaWiki.
Пошук з вертанням покладається на подані користувачем процедури, які визначають задачу для розв'язання, природу неповних кандидатів і як вони доповнюються до повних кандидатів. Тому це швидше метаевристика ніж конкретний алгоритм — хоча, на відміну від інших метаевристик, вона гарантовано знаходить всі розв'язки скінченної проблеми за обмежений час.
Англомовний термін «backtrack» був винайдений американським математиком D. H. Lehmer в 1950-х. Піонерська мова опрацювання рядків SNOBOL (1962) можливо першою забезпечила вбудовані засоби загального пошуку з вертанням.
Опис методу
Алгоритм пошуку з вертанням перераховує множину неповних кандидатів що, в принципі, можуть бути доповнені кількома шляхами для отримання всіх можливих розв'язків даної задачі. Доповнення будується покроково, послідовністю кроків розширення кандидата.
Концептуально, неповні кандидати є вузлами деревоподібної структури, потенційне дерево пошуку. Кожний неповний кандидат є батьком кандидатів відмінних від нього на один крок розширення; листям дерева є кандидати які не можуть бути розширені далі.
Алгоритм пошуку з вертанням обходить це дерево пошуку рекурсивно, від кореня донизу, пошуком в глибину. В кожному вузлі c, алгоритм перевіряє чи може c бути доповнене до вірного розв'язку. Якщо ні, ціле піддерево з коренем в c пропускається (обрізається). Інакше, алгоритм (1) перевіряє чи є c вірним розв'язком, і якщо так повідомляє про це користувача; і (2) рекурсивно обходить усі піддерева c. Обидва тести і дочірні вузли кожного вузла визначаються за допомогою поданих користувачем процедур.
Внаслідок цього, актуальне дерево пошуку яке обходить алгоритм становить лише частину потенційного дерева. Загальна ціна алгоритму це кількість вузлів актуального дерева помножена на вартість отримання і обробки кожного вузла. Цей факт має бути врахованим коли обирається потенційне дерево і реалізується тест на обрізання.
Псевдокод
Для застосування пошуку з вертанням для певного класу задач, потрібно мати дані P для конкреної задачі, що має бути розв'язана, і шість підпрограм, корінь, відмова, прийняття, перший, наступний, і вихід. Ці підпрограми мають отримувати дані P як параметр і мають бути такими:
- корінь(«P»): повертає неповний кандидат в корені дерева пошуку.
- відмова(P,c): повертає істину тільки якщо неповний кандидат c невартий завершення.
- прийняття(P,c): повертає істину якщо c є розв'язком P, і хибу якщо ні.
- перший(P,c): продукує перше розширення кандидата c.
- наступний(P,s): продукує інше наступне розширення кандидата, після розширення s.
- вихід(P,c): прийняти розв'язок c з P, як підходяще для застосування.
Пошук з вертанням зводиться до виклику bt(root(P)), де bt наступна рекурсивна підпрограма:
procedure bt(c) якщо відмова(P,c) тоді вийти якщо прийняття(P,c) тоді вихід(P,c) s ← перший(P,c) доки s ≠ Λ робити bt(s) s ← наступний(P,s)
Див. також
- Prolog, Planner
- Зворотний перехід
- [en]
Примітки
- Дональд Кнут (1968). Мистецтво програмування. Addison-Wesley.
- Thomas H. Cormen; Charles E. Leiserson, Ronald R. Rivest, Cliff Stein (1990). Introduction to Algorithms. McGraw-Hill.
- Gurari, Eitan (1999). . Архів Backtracking algorithms оригіналу за 17 березня 2007. Процитовано 19 січня 2011.
- Rossi, Francesca; Beek, Peter Van; Walsh, Toby (August 2006). Constraint Satisfaction: An Emerging Paradigm. Handbook of Constraint Programming. Foundations of Artificial Intelligence. Амстердам: Elsevier. с. 14. ISBN . Процитовано 30 грудня 2008.
Bitner and Reingold credit Lehmer with first using the term 'backtrack' in the 1950s.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Poshuk z vertannyam angl backtracking takozh poshuk z povernennyam zagalnij algoritm dlya znahodzhennya vsih abo deyakih rozv yazkiv deyakoyi obchislyuvalnoyi zadachi yakij postupovo buduye kandidativ na rozv yazok i vidkidaye kozhnogo nepovnogo kandidata c vertayetsya yak tilki viznachaye sho c ne mozhe buti dopovnenim do virnogo rozv yazku OglyadKlasichnij priklad vikoristannya poshuku z vertannyam ce zadacha pro visim ferziv v yakij potribno znajti roztashuvannya vosmi ferziv na standartnij shahivnici takim chinom shob zhoden ferz ne atakuvav inshogo V zvichajnomu pidhodi poshuku z vertannyam nepovni kandidati ce roztashuvannya k ferziv v pershih k ryadah doshki vsi v riznih ryadah i stovpcyah Bud yakij nepovnij rozv yazok sho mistit dva ferzi yaki atakuyut odin odnogo maye buti vidkinutij bo vin ne mozhe buti dovedenim do povnogo pravilnogo rozv yazku Poshuk z vertannyam mozhe buti zastosovanij tilki do zadach sho dozvolyayut ponyattya nepovnih kandidativ na rozv yazok i porivnyano shvidku perevirku na mozhlivist dopovnennya kandidata do virnogo rozv yazku Ce korisno napriklad dlya znahodzhennya znachennya u nevporyadkovanij tablici Za mozhlivosti zastosuvannya poshuk z vertannyam chasto znachno shvidshij nizh povnij perebir vsih mozhlivih kandidativ cherez viklyuchennya velikoyi kilkosti kandidativ odniyeyu perevirkoyu Poshuk z vertannyam ce vazhlive znaryaddya dlya rozv yazannya problemi vidpovidnosti obmezhennyam takih yak krosvordi sudoku ta bagato inshih golovolomok Chasto ce najzruchnishij yaksho ne najefektivnishij pidhid dlya rozboru dlya zadachi pakuvannya ryukzaka ta inshih zadach kombinatornoyi optimizaciyi Ce takozh bazis dlya tak zvanih mov logichnogo programuvannya takih yak Icon Planner i Prolog Poshuk z vertannyam takozh vikoristovuyetsya v rushiyi zmin diff dlya programnogo zabezpechennya MediaWiki Poshuk z vertannyam pokladayetsya na podani koristuvachem proceduri yaki viznachayut zadachu dlya rozv yazannya prirodu nepovnih kandidativ i yak voni dopovnyuyutsya do povnih kandidativ Tomu ce shvidshe metaevristika nizh konkretnij algoritm hocha na vidminu vid inshih metaevristik vona garantovano znahodit vsi rozv yazki skinchennoyi problemi za obmezhenij chas Anglomovnij termin backtrack buv vinajdenij amerikanskim matematikom D H Lehmer v 1950 h Pionerska mova opracyuvannya ryadkiv SNOBOL 1962 mozhlivo pershoyu zabezpechila vbudovani zasobi zagalnogo poshuku z vertannyam Opis metoduAlgoritm poshuku z vertannyam pererahovuye mnozhinu nepovnih kandidativ sho v principi mozhut buti dopovneni kilkoma shlyahami dlya otrimannya vsih mozhlivih rozv yazkiv danoyi zadachi Dopovnennya buduyetsya pokrokovo poslidovnistyu krokiv rozshirennya kandidata Konceptualno nepovni kandidati ye vuzlami derevopodibnoyi strukturi potencijne derevo poshuku Kozhnij nepovnij kandidat ye batkom kandidativ vidminnih vid nogo na odin krok rozshirennya listyam dereva ye kandidati yaki ne mozhut buti rozshireni dali Algoritm poshuku z vertannyam obhodit ce derevo poshuku rekursivno vid korenya donizu poshukom v glibinu V kozhnomu vuzli c algoritm pereviryaye chi mozhe c buti dopovnene do virnogo rozv yazku Yaksho ni cile pidderevo z korenem v c propuskayetsya obrizayetsya Inakshe algoritm 1 pereviryaye chi ye c virnim rozv yazkom i yaksho tak povidomlyaye pro ce koristuvacha i 2 rekursivno obhodit usi piddereva c Obidva testi i dochirni vuzli kozhnogo vuzla viznachayutsya za dopomogoyu podanih koristuvachem procedur Vnaslidok cogo aktualne derevo poshuku yake obhodit algoritm stanovit lishe chastinu potencijnogo dereva Zagalna cina algoritmu ce kilkist vuzliv aktualnogo dereva pomnozhena na vartist otrimannya i obrobki kozhnogo vuzla Cej fakt maye buti vrahovanim koli obirayetsya potencijne derevo i realizuyetsya test na obrizannya Psevdokod Dlya zastosuvannya poshuku z vertannyam dlya pevnogo klasu zadach potribno mati dani P dlya konkrenoyi zadachi sho maye buti rozv yazana i shist pidprogram korin vidmova prijnyattya pershij nastupnij i vihid Ci pidprogrami mayut otrimuvati dani P yak parametr i mayut buti takimi korin P povertaye nepovnij kandidat v koreni dereva poshuku vidmova P c povertaye istinu tilki yaksho nepovnij kandidat c nevartij zavershennya prijnyattya P c povertaye istinu yaksho c ye rozv yazkom P i hibu yaksho ni pershij P c produkuye pershe rozshirennya kandidata c nastupnij P s produkuye inshe nastupne rozshirennya kandidata pislya rozshirennya s vihid P c prijnyati rozv yazok c z P yak pidhodyashe dlya zastosuvannya Poshuk z vertannyam zvoditsya do vikliku bt root P de bt nastupna rekursivna pidprograma procedure bt c yaksho vidmova P c todi vijti yaksho prijnyattya P c todi vihid P c s pershij P c doki s L robiti bt s s nastupnij P s Div takozhProlog Planner Zvorotnij perehid en PrimitkiDonald Knut 1968 Mistectvo programuvannya Addison Wesley Thomas H Cormen Charles E Leiserson Ronald R Rivest Cliff Stein 1990 Introduction to Algorithms McGraw Hill Gurari Eitan 1999 Arhiv Backtracking algorithms originalu za 17 bereznya 2007 Procitovano 19 sichnya 2011 Rossi Francesca Beek Peter Van Walsh Toby August 2006 Constraint Satisfaction An Emerging Paradigm Handbook of Constraint Programming Foundations of Artificial Intelligence Amsterdam Elsevier s 14 ISBN 978 0 444 52726 4 Procitovano 30 grudnya 2008 Bitner and Reingold credit Lehmer with first using the term backtrack in the 1950s