Бектрекинг

Из Википедије, слободне енциклопедије

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

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

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

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

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

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

Опис метода[уреди]

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

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

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

Псеудокод[уреди]

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

  1. root(P) - враћа парцијалног кандидата који је корен стабла.
  2. reject(P, c) - враћа буловску вредност тачно уколико парцијални кандидат с није вредан проширења.
  3. accept(P, c) - враћа тачно уколико је кандидат с целокупно решење проблема Р, у супротном враћа нетачно.
  4. first(P, c) - генерише прво проширење кандидата c.
  5. next(P, s) - генерише следеће проширење кандидата, после проширења s.
  6. output(P, c) - користи кандидата c као прикладно решење.

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

procedure bt(c)
   if reject(P,c) then return
   if accept(P,c) then output(P,c)
   sfirst(P,c)
   while s ≠ Λ do
     bt(s)
     snext(P,s)

Разматрања имплементације[уреди]

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

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

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

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

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

Функције 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)
   klength(c)
   if k = n
     then return Λ
     else return (c[1], c[2], ..., c[k], 1)
 function next(P,s)
   klength(s)
   if s[k] = m
     then return Λ
     else return (s[1], s[2], ..., s[k-1], 1 + s[k])

Где је length(c) број елемената низа с. Позив reject(P,c) би требало да врати тачно уколико функција F не може бити задовољена било којим низом од n бројева који почињу са k елемената из с. Да би алгоритам био ефикасан мора постојати начин да детектујемо ову ситуацију, а без набрајања свих mn-k n-торки.

На пример уколико је F конјункција неколико буловских променљивих,F = F[1] \wedge F[2] \wedge \cdots \wedge F[p], и сваки F[i] зависи само од малог подскупа променљивих x[1], ..., x[n], тада би функција reject могла просто да провери терме F[i] који зависе само од подскупа x[1], ..., x[k] и врати тачно уколико било који од ових терма врате нису тачни. У ствари reject мора само да провери оне терме који зависе од x[k], будући да ће терми који зависе од x[1], ..., x[k-1] бити тестирани даље приликом извршавања алгоритма.

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

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

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

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

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

[1][2][3]

Референце[уреди]

Литература[уреди]

  • Brassard, Gilles; Bratley, Paul (1995). Fundamentals of Algorithmics. Prentice-Hall. 
  • Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald R.; Stein, Cliff (1990). Introduction to Algorithms. McGraw-Hill. 
  • Gurari, Eitan (1999). „Backtracking algorithms“. CIS 680: DATA STRUCTURES. 
  • Knuth, Donald E. (1968). The Art of Computer Programming. Addison-Wesley. 

Спољашње везе[уреди]

  • HBmeyer.de, Interactive animation of a backtracking algorithm
  • Sample Java Code, Sample code for backtracking of 8 Queens problem.