Бектрекинг — разлика између измена
Садржај обрисан Садржај додат
м . |
м razne izmene; козметичке измене |
||
Ред 5:
Бектрекинг може бити од користи само у проблемима код којих можемо применити концепт "одабира одговарајућих кандидата" и код којих релативно брзо можемо испитати да ли одређен кандидат може бити валидни део решења. Када је применљив бектрекинг је често много бржи од класичног набрајања решења грубом силом, најчешће због тога што елиминише велики број кандидата у сваком кораку.
Бектрекинг је важна техника за решавање проблема задовољивости, и слагалица као што су укрштене речи, судоку, и многе друге. Често ова стратегија је најзгоднија при парсирању текста (понекад и најефикаснија), као и при решавању проблема ранца и комбинаторним оптимизацијама неких проблема. Такође бектрекинг је база за такозване логичке програмске језике као што су ајкон, планер и пролог.
Бектрекинг зависи од фунција које су типа "црне кутије" које дефинишу проблем који треба решити, природу кандидата које узимамо у обзир, и то како ови кандидати постају део решења. Важно је напоменути да је бектрекинг више хеуристика него тачно одређени алгоритам, ипак, за разлику од осталих хеуристика, он гарантује проналажење свих решења за неки коначан проблем, у одређеном временском року.
Термин "бектрекинг" увео је амерички математичар Д. Х. Лемер 50-их година 20-ог века. Један од пионира језика за обраду низова карактера СНОБОЛ (из 1962. године) био је први који је применио уграђене механизме засноване на бектрекингу.
== Опис метода ==
Ред 17:
Концептуално, парцијални кандидати су чворови дрвоидне структуре која се назива "стабло претраге потенцијалних кандидата“. Сваки парцијални кандидат је родитељ свих кандидата који произилазе из њега употребом једног корака проширења; листови су они чворови, који представљају кандидате који се више не могу проширити.
Бектрекинг алгоритми прелазе стабло рекурзивно, од корена ка листовима. За сваки чвор, алгоритам проверава може ли он бити део валидног решења, уколико не цело подстабло почевши од овог чвора се прескаче (одсеца). У супротном [[алгоритам]] проверава да ли је сам чвор
целокупно решење, и уколико јесте јавља се кориснику, и штампају се сви његови потомци рекурзивно. Ова два упита као и потомци сваког чвора се дефинишу од стране корисника. Тако да је стварно дрво претраге које се користи приликом извршавања алгоритма у ствари само део целокупног стабла претраге потенцијалних кандидата. Сложеност алгоритма је број чворова који се испита помножен са ценом провере и проласка кроз сваки чвор. Ово је чињеница коју треба узети у обзир приликом одређивања стабла претраге и имплементације упита за одсецање грана.
Ред 45:
да функција ''bt()'' испусти нека решења. Функција може претпоставити да функција ''reject(P,t)'' враћа нетачно за сваког предак ''t'' кандидата ''с'' у стаблу.
Са друге стране ефикасност алгоритма зависи да функција ''reject'' враћа вредност тачно за кандидате што ближе корену. Уколико ова функција стално враћа нетачно то решење би било еквивалентно употреби алгоритма грубе силе.
Функција ''accept(P,c)'' треба да врати вредност тачно уколико је ''с'' потпуно решење проблема ''Р'', нетачно у супротном. Може претпоставити да су кандидат ''с'' и сви његови преци у стаблу прошли функцију ''reject''.
Ред 51:
Приметимо да уопштени псеудокод не претпоставља да су решења увек листови у стаблу претраге. Другим речима потврђује да се решење за ''Р'' може даље проширити да би допринели другим решењима.
Функције ''first'' и ''next'' користе бектрекинг алгоритме да би дошли до наследника кандидата ''с'' у стаблу. Позив ''first(P,c)'' треба да врати првог наследника чвора ''с'', а позив ''next(P,s)'' следећег брата чвора ''s'' у стаблу. Обе функције треба да врате вредност ''null'', овде представљен као ''Λ'', уколико ови чворови не постоје.
Функције ''root, first'' и ''next'' заједно одређују скуп парцијалних кандидата стабла. Оне се требају изабрати тако да се свако решење проблема налази негде у стаблу, а да се ниједан кандидат не појави двапут. Такође треба обезбедити што ефикаснију ''reject'' функцију.
Ред 93:
''x[1], ..., x[k]'' и врати тачно уколико било који од ових терма врате нису тачни. У ствари ''reject'' мора само да провери оне терме који зависе од ''x[k]'', будући да ће терми који зависе од ''x[1], ..., x[k-1]'' бити тестирани даље приликом извршавања алгоритма.
Ако претпоставимо да је функција ''reject'' имплементирана као горе, онда ''accept(P,c)'' једино треба да провери да ли је ''с'' комлетан, то јест да ли има ''n'' елемената.
Генерално увек је боље прво сортирати низ како би почињао са најкритичнијим члановима.
Такође могуће је дозволити функцији ''next'' да одреди променљиву које ће бити додељена приликом проширења кандидата, на основу вредности променљивих које су му додељене.
Да би обезбедили минималне вредности при повратку бектрекинг алгоритми користе "траг променљиве", односно памте последње промене података. Ефикаском имплементацијом може се избећи креирање непотребних трагова када за то нема потребе.
Алтернатива трага проманљиве је коришћење времена последње промене. Уколико је време последње промене приликом упита веће није потребно мењати вредност променљивој приликом враћања, због тога што је ажурирана пре него што се упит појавио.
{{sfn|Knuth|1968|p=}}{{sfn|Cormen|Leiserson|Rivest|Stein|1990|p=}}{{sfn|Gurari|1999|p=}}
Ред 113:
== Литература ==
{{Refbegin|2}}
* {{Cite book |ref= harv|
* {{Cite book |ref= harv|
* {{Cite book|ref=harv|last=Gurari|first=Eitan|title=CIS 680: DATA STRUCTURES|url=http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680.html|edition=|year=1999|publisher=|location=|chapter=Backtracking algorithms|chapterurl=http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html#QQ1-51-128|id=|access-date=29. 10. 2012|archive-url=https://web.archive.org/web/20110608185149/http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680.html|archive-date=08. 06. 2011|url-status=dead|df=}}
* {{Cite book |ref= harv|last=Knuth| first = Donald E. | title = The Art of Computer Programming|url=| edition = |year=1968| publisher = Addison-Wesley| location = |id=}}
| |||