Бектрекинг — разлика између измена
Садржај обрисан Садржај додат
мНема описа измене |
м Разне исправке; козметичке измене |
||
Ред 6:
Бектрекинг може бити од користи само у проблемима код којих можемо применити концепт "одабира одговарајућих кандидата" и код којих релативно брзо можемо испитати да ли одређен кандидат може бити валидни део решења. Када је применљив бектрекинг је често много бржи од класичног набрајања решења грубом силом, најчешће због тога што елиминише велики број кандидата у сваком кораку.
Бектрекинг је важна техника за решавање проблема задовољивости, и слагалица као што су укрштене речи, судоку, и многе друге. Често ова стратегија
Бектрекинг зависи од фунција које су типа "црне кутије" које дефинишу проблем који треба решити, природу кандидата које узимамо у обзир, и то како ови кандидати постају део решења. Важно је напоменути да је бектрекинг више [[хеуристика]] него тачно одређени [[алгоритам]], ипак, за разлику од осталих [[хеуристика]], он гарантује проналажење свих решења за неки коначан проблем, у одређеном временском року.
Термин "бектрекинг" увео је амерички математичар Д. Х. Лемер 50-их година 20-ог века. Један од пионира језика за обраду низова карактера СНОБОЛ (из 1962. године) био је први који је применио уграђене механизме засноване на бектрекингу.
== Опис метода ==
Бектрекинг [[алгоритми]] генеришу скуп парцијалних кандидата, који могу бити комплетирани на различите начине тако да добијемо сва могућа решења датог проблема. Комплетирање решења се врши постепено, кроз низ корака проширења.
Ред 21:
целокупно решење, и уколико јесте јавља се кориснику, и штампају се сви његови потомци рекурзивно. Ова два упита као и потомци сваког чвора се дефинишу од стране корисника. Тако да је стварно дрво претраге које се користи приликом извршавања алгоритма уствари само део целокупног стабла претраге потенцијалних кандидата. Сложеност алгоритма је број чворова који се испита помножен са ценом провере и проласка кроз сваки чвор. Ово је чињеница коју треба узети у обзир приликом одређивања стабла претраге и имплементације упита за одсецање грана.
== Псеудокод ==
Да би применили бектрекинг на одређену класу проблема, морамо обезбедити податке за проблем Р који представља једну практичну инстанцу проблема из те класе, и процедуре: ''root, reject, accept, first, next,'' и ''output''. Ове процедуре треба да узимају вредности параметара Р и враћају следеће вредности:
Ред 42:
''s'' ← ''next''(''P'',''s'')
== Разматрања имплементације ==
Функција ''reject'' треба да враћа тачно само уколико је сигурно да ниједно проширење кандидата ''с'' није део решења проблема ''Р''. Уколико функција не може ово да закључи треба да врати вредност нетачно. Уколико функција невалидно врати вредност тачно то може проузроковати
Ред 57:
Функције ''root, first'' и ''next'' заједно одређују скуп парцијалних кандидата стабла. Оне се требају изабрати тако да се свако решење проблема налази негде у стаблу, а да се ниједан кандидат не појави двапут. Такође треба обезбедити што ефикаснију ''reject'' функцију.
== Варијанте са раним заустављањем ==
Горе приказани [[алгоритам]] можемо модификовати тако да стане после проналаска првог решења, одређеног броја решења, одређеног броја испитаних кандидата или утрошеног задатог процесорског времена.
== Примери ==
Типични примери су:
* Слагалице као проблем осам дама, судоку, укрштене речи, пег солитер.
* Комбинаторне оптимизације као што су парсирање и проблем ранца.
* Логички програмски језици који користе бектрекинг да би генерисали одговоре.
* Бектрекинг се такође примењује код софтвера за поређење верзија за Медиавики.
Испод је приказан проблем задовољивости.
== Задовољивост ==
Општи проблем задовољивости трага за низом природних бројева ''x = (x[1],x[2], ..., x[n])'', из неког интервала ''{1, 2, ..., m}'', који задовољавају произвољну буловску функцију ''F''.
За ову класу проблема, инстанцни подаци ''Р'' биће ''m'' и ''n'' и предикат ''F''. У типичном бектрекинг алгоритму дефинишемо листу парцијалних кандидата као листу природних бројева ''c = (c[1],c[2], ... c[k])'', за било које ''k'' између ''0'' и ''n'', који ће бити додељени првим ''k'' променљивама ''x[1],x[2], ..., x[k]''. Корен стабла ће бити празан низ. Функције ''first'' и ''next''
'''function''' ''first''(''P'',''c'')
Ред 103:
Да би обезбедили минималне вредности при повратку бектрекинг алгоритми користе "траг променљиве", односно памте последње промене података. Ефикаском имплементацијом може се избећи креирање непотребних трагова када за то нема потребе.
Алтернатива трага проманљиве је коришћење времена последње промене. Уколико је време последње промене приликом упита веће није потребно мењати вредност променљивој приликом враћања, због тога што је ажурирана пре него што се упит појавио.
{{sfn|Knuth|1968|p=}}{{sfn|Cormen|Leiserson|Rivest|Stein|1990|p=}}{{sfn|Gurari|1999|p=}}
Ред 112:
== Литература ==
{{Refbegin|2}}
*
| last1 = Brassard
| first1 = Gilles
Ред 125:
| isbn =
}}
*
| last1 = Cormen
| first1 = Thomas H.
Ред 142:
| isbn =
}}
*
| last = Gurari
| first = Eitan
Ред 155:
| chapterurl = http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch19.html#QQ1-51-128
}}
*
| last = Knuth
| first = Donald E.
Ред 168:
{{Refend}}
== Спољашње везе ==
* [http://www.hbmeyer.de/backtrack/backtren.htm -{HBmeyer.de], Interactive animation of a backtracking algorithm}-
* [http://github.com/kapild/Permutations -{Sample Java Code], Sample code for backtracking of 8 Queens problem.}-
[[Категорија:Алгоритми претраживања]]
| |||