Back

ⓘ Бектрекинг



                                     

ⓘ Бектрекинг

Бектрекинг алгоритам или метод обрнуте претраге предстаља приступ грубе силе у тражењу решења где се испробавају све могуће комбинације. Постепено се граде кандидати за решење а одбацују се сви кандидати за које се испостави да не воде до тачног решења. Због сложености неких проблема, алгоритам се често споро извршава па се користе алгоритми пролагођенији за дати проблем, осим ако за проблем постоји добра хеуристика. Алгоритам пролазећи кроз све могуће ситуације даје прво решење, сва могућа решења, па и самим тим и оптимално решење.

Класични пример коришћења бектрекинга је проблем осам дама, код овог проблема трага се за распоредом осам дама на стандардној шаховској табли, тако да ниједна дама не напада било коју другу. При решавању проблема користи се бектрекинг приступ да су парцијални кандидати за решења сви распореди код којих је к дама постављено у првих к редова на табли, а свих к у различитим редовима и колонама. Било које овако генерисано решење које садржи две даме које се међусобно нападају бивају изостављена, будући да не могу бити део коначног решења.

Бектрекинг може бити од користи само у проблемима код којих можемо применити концепт "одабира одговарајућих кандидата" и код којих релативно брзо можемо испитати да ли одређен кандидат може бити валидни део решења. Када је применљив бектрекинг је често много бржи од класичног набрајања решења грубом силом, најчешће због тога што елиминише велики број кандидата у сваком кораку.

Бектрекинг је важна техника за решавање проблема задовољивости, и слагалица као што су укрштене речи, судоку, и многе друге. Често ова стратегија је најзгоднија при парсирању текста понекад и најефикаснија, као и при решавању проблема ранца и комбинаторним оптимизацијама неких проблема. Такође бектрекинг је база за такозване логичке програмске језике као што су ајкон, планер и пролог.

Бектрекинг зависи од фунција које су типа "црне кутије" које дефинишу проблем који треба решити, природу кандидата које узимамо у обзир, и то како ови кандидати постају део решења. Важно је напоменути да је бектрекинг више хеуристика него тачно одређени алгоритам, ипак, за разлику од осталих хеуристика, он гарантује проналажење свих решења за неки коначан проблем, у одређеном временском року.

Термин "бектрекинг" увео је амерички математичар Д. Х. Лемер 50-их година 20. века. Један од пионира језика за обраду низова карактера СНОБОЛ из 1962. године био је први који је применио уграђене механизме засноване на бектрекингу.

                                     

1. Опис метода

Бектрекинг алгоритми генеришу скуп парцијалних кандидата, који могу бити комплетирани на различите начине тако да добијемо сва могућа решења датог проблема. Комплетирање решења се врши постепено, кроз низ корака проширења.

Концептуално, парцијални кандидати су чворови дрвоидне структуре која се назива "стабло претраге потенцијалних кандидата". Сваки парцијални кандидат је родитељ свих кандидата који произилазе из њега употребом једног корака проширења; листови су они чворови, који представљају кандидате који се више не могу проширити.

Бектрекинг алгоритми прелазе стабло рекурзивно, од корена ка листовима. За сваки чвор, алгоритам проверава може ли он бити део валидног решења, уколико не цело подстабло почевши од овог чвора се прескаче одсеца. У супротном алгоритам проверава да ли је сам чвор целокупно решење, и уколико јесте јавља се кориснику, и штампају се сви његови потомци рекурзивно. Ова два упита као и потомци сваког чвора се дефинишу од стране корисника. Тако да је стварно дрво претраге које се користи приликом извршавања алгоритма у ствари само део целокупног стабла претраге потенцијалних кандидата. Сложеност алгоритма је број чворова који се испита помножен са ценом провере и проласка кроз сваки чвор. Ово је чињеница коју треба узети у обзир приликом одређивања стабла претраге и имплементације упита за одсецање грана.

                                     

2. Псеудокод

Да би применили бектрекинг на одређену класу проблема, морамо обезбедити податке за проблем Р који представља једну практичну инстанцу проблема из те класе, и процедуре: root, reject, accept, first, next, и output. Ове процедуре треба да узимају вредности параметара Р и враћају следеће вредности:

  • outputP, c - користи кандидата c као прикладно решење.
  • acceptP, c - враћа тачно уколико је кандидат с целокупно решење проблема Р, у супротном враћа нетачно.
  • nextP, s - генерише следеће проширење кандидата, после проширења s.
  • rejectP, c - враћа буловску вредност тачно уколико парцијални кандидат с није вредан проширења.
  • rootP - враћа парцијалног кандидата који је корен стабла.
  • firstP, c - генерише прво проширење кандидата c.

Бектрекинг алгоритам се онда своди на позив btrootP), где је bt следећа процедура:

procedure bt c if reject P, c then return if accept P, c then output P, c s ← first P, c while s ≠ Λ do bt s ← next P, s
                                     

3. Разматрања имплементације

Функција reject треба да враћа тачно само уколико је сигурно да ниједно проширење кандидата с није део решења проблема Р. Уколико функција не може ово да закључи треба да врати вредност нетачно. Уколико функција невалидно врати вредност тачно то може проузроковати да функција bt испусти нека решења. Функција може претпоставити да функција rejectP,t враћа нетачно за сваког предак t кандидата с у стаблу.

Са друге стране ефикасност алгоритма зависи да функција reject враћа вредност тачно за кандидате што ближе корену. Уколико ова функција стално враћа нетачно то решење би било еквивалентно употреби алгоритма грубе силе.

Функција acceptP,c треба да врати вредност тачно уколико је с потпуно решење проблема Р, нетачно у супротном. Може претпоставити да су кандидат с и сви његови преци у стаблу прошли функцију reject.

Приметимо да уопштени псеудокод не претпоставља да су решења увек листови у стаблу претраге. Другим речима потврђује да се решење за Р може даље проширити да би допринели другим решењима.

Функције first и next користе бектрекинг алгоритме да би дошли до наследника кандидата с у стаблу. Позив firstP,c треба да врати првог наследника чвора с, а позив nextP,s следећег брата чвора s у стаблу. Обе функције треба да врате вредност null, овде представљен као Λ, уколико ови чворови не постоје.

Функције root, first и next заједно одређују скуп парцијалних кандидата стабла. Оне се требају изабрати тако да се свако решење проблема налази негде у стаблу, да се ниједан кандидат не појави двапут. Такође треба обезбедити што ефикаснију reject функцију.



                                     

4. Варијанте са раним заустављањем

Горе приказани алгоритам можемо модификовати тако да стане после проналаска првог решења, одређеног броја решења, одређеног броја испитаних кандидата или утрошеног задатог процесорског времена.

                                     

5. Примери

Типични примери су:

  • Комбинаторне оптимизације као што су парсирање и проблем ранца.
  • Слагалице као проблем осам дама, судоку, укрштене речи, пег солитер.
  • Бектрекинг се такође примењује код софтвера за поређење верзија за Медиавики.
  • Логички програмски језици који користе бектрекинг да би генерисали одговоре.

Испод је приказан проблем задовољивости.

                                     

6. Задовољивост

Општи проблем задовољивости трага за низом природних бројева x = x бити тестирани даље приликом извршавања алгоритма.

Ако претпоставимо да је функција reject имплементирана као горе, онда acceptP,c једино треба да провери да ли је с комлетан, то јест да ли има n елемената.

Генерално увек је боље прво сортирати низ како би почињао са најкритичнијим члановима.

Такође могуће је дозволити функцији next да одреди променљиву које ће бити додељена приликом проширења кандидата, на основу вредности променљивих које су му додељене.

Да би обезбедили минималне вредности при повратку бектрекинг алгоритми користе "траг променљиве", односно памте последње промене података. Ефикаском имплементацијом може се избећи креирање непотребних трагова када за то нема потребе.

Алтернатива трага проманљиве је коришћење времена последње промене. Уколико је време последње промене приликом упита веће није потребно мењати вредност променљивој приликом враћања, због тога што је ажурирана пре него што се упит појавио.

Free and no ads
no need to download or install

Pino - logical board game which is based on tactics and strategy. In general this is a remix of chess, checkers and corners. The game develops imagination, concentration, teaches how to solve tasks, plan their own actions and of course to think logically. It does not matter how much pieces you have, the main thing is how they are placement!

online intellectual game →