Википедија

Бектрекинг — разлика између измена

Интерактиван преглед историје
← Старија изменаНовија измена →
Садржај обрисан Садржај додат
ВизуелноВикитекст
Autobot (разговор | доприноси)
1.572.075 измена
м Уклањање сувишних унутрашњих веза
Ред 1:
'''Бектрекинг''' ({{jez-eng|Backtracking}}) [[алгоритам]] или метод обрнуте [[Алгоритми претраживања|претраге]] предстаља приступ ''грубе силе'' у тражењу решења где се испробавају све могуће комбинације. Постепено се граде кандидати за решење а одбацују се сви кандидати за које се испостави да не воде до тачног решења. Због [[сложеност алгоритма|сложености]] неких проблема, [[алгоритам]] се често споро извршава па се користе [[algoritam|алгоритми]] пролагођенији за дати проблем, осим ако за проблем постоји добра [[хеуристика]] (интуитивнан начин налажења који често даје само приближно решење). [[Алгоритам]] пролазећи кроз све могуће ситуације даје прво решење, сва могућа решења, па и самим тим и оптимално решење.
 
Класични пример коришћења бектрекинга је проблем осам дама, код овог проблема трага се за распоредом осам дама на стандардној шаховској табли, тако да ниједна дама не напада било коју другу. При решавању проблема користи се бектрекинг приступ да су парцијални кандидати за решења сви распореди код којих је ''к'' дама постављено у првих ''к'' редова на табли, а свих ''к'' у различитим редовима и колонама. Било које овако генерисано решење које садржи две даме које се међусобно нападају бивају изостављена, будући да не могу бити део коначног решења.
Ред 7:
Бектрекинг је важна техника за решавање проблема задовољивости, и слагалица као што су укрштене речи, судоку, и многе друге. Често ова стратегија је најзгоднија при парсирању текста (понекад и најефикаснија), као и при решавању проблема ранца и комбинаторним оптимизацијама неких проблема. Такође бектрекинг је база за такозване логичке програмске језике као што су ајкон, планер и пролог.
 
Бектрекинг зависи од фунција које су типа "црне кутије" које дефинишу проблем који треба решити, природу кандидата које узимамо у обзир, и то како ови кандидати постају део решења. Важно је напоменути да је бектрекинг више [[хеуристика]] него тачно одређени [[алгоритам]], ипак, за разлику од осталих [[хеуристика]], он гарантује проналажење свих решења за неки коначан проблем, у одређеном временском року.
 
Термин "бектрекинг" увео је амерички математичар Д. Х. Лемер 50-их година 20-ог века. Један од пионира језика за обраду низова карактера СНОБОЛ (из 1962. године) био је први који је применио уграђене механизме засноване на бектрекингу.
Ред 17:
Концептуално, парцијални кандидати су чворови дрвоидне структуре која се назива "стабло претраге потенцијалних кандидата“. Сваки парцијални кандидат је родитељ свих кандидата који произилазе из њега употребом једног корака проширења; листови су они чворови, који представљају кандидате који се више не могу проширити.
 
Бектрекинг [[алгоритми]] прелазе стабло рекурзивно, од корена ка листовима. За сваки чвор, алгоритам проверава може ли он бити део валидног решења, уколико не цело подстабло почевши од овог чвора се прескаче (одсеца). У супротном [[алгоритам]] проверава да ли је сам чвор
целокупно решење, и уколико јесте јавља се кориснику, и штампају се сви његови потомци рекурзивно. Ова два упита као и потомци сваког чвора се дефинишу од стране корисника. Тако да је стварно дрво претраге које се користи приликом извршавања алгоритма у ствари само део целокупног стабла претраге потенцијалних кандидата. Сложеност алгоритма је број чворова који се испита помножен са ценом провере и проласка кроз сваки чвор. Ово је чињеница коју треба узети у обзир приликом одређивања стабла претраге и имплементације упита за одсецање грана.
 
Преузето из „https://sr.wikipedia.org/wiki/Бектрекинг”