Бектрекинг и груба сила
У наставку ћемо разматрати проблеме следећег типа:
Испитати да ли постоји неки комбинаторни објекат (често представљен торком бројева) који задовољава неке дате услове. Овакви проблеми се називају проблеми задовољавања ограничења (енгл. constraint satisfaction problems, CSP). На пример, потребно је проверити да ли постоји неки подскуп датог скупа бројева чији је збир једнак датој вредности.
Међу свим комбинаторним објектима који задовољавају неке дате услове наћи најбољи тј. наћи онај објекат на коме је вредност неке дате функције минимална или максимална. Овакви проблеми се називају проблеми оптимизације уз ограничења (енгл. constraint optimization problems, COP). Ови проблеми се називају и проблеми комбинаторне оптимизације.
Овакви проблеми се често решавају разним варијантама алгоритама претраге у којима се набрајају и проверавају неки кандидати за решења.
Алгоритми грубе силе подразумевају да се у претрази исцрпно наброје сви кандидати за решење и да се за сваког од њих провери да ли задовољава услов (ако је потребно пронаћи било који елемент који задовољава дати услов) или да ли је оптималан (ако је потребно пронаћи елемент који минимализује или максимализује дату циљну функцију). Сви кандидати се понекада могу набројати једноставно, угнежђеним петљама, док је некада потребно користити неки сложенији поступак за набрајање одређене фамилије комбинаторних објеката (комбинација, пермутација, варијација, подскупова, партиција итд. али и других, специфичних фамилија комбинаторних објеката).
Алгоритми претраге са повратком тј. бектрекинг (енгл. backtracking) побољшавају технику грубе силе тако што врше провере и током генерисања кандидата за решења и тако што се одбацују парцијално попуњени кандидати, за које се може унапред утврдити да се не могу проширити до исправног тј. оптималног решења. Дакле, бектрекинг подразумева да се током обиласка у дубину дрвета којим се представља простор потенцијалних решења одсецају они делови дрвета за које се унапред може утврдити да не садрже ни једно решење проблема тј. да не садрже оптимално решење, при чему се одсецање врши и у чворовима блиским корену који могу да садрже и само парцијално попуњене кандидате за решења. Дакле, уместо да се чека да се током претраге стигне до листа (или евентуално унутрашњег чвора који представља неког кандидата за решење) и да се провера задовољености услова или оптималности врши тек тада, приликом претраге са повратком провера се врши у сваком кораку и врши се провера парцијално попуњених решења (обично су то неке парцијално попуњене торке бројева).
На пример, ако се проверава да ли постоји подскуп неког скупа чији је збир елемената једнак датом броју и ако се установи да прва два елемента полазног скупа имају збир већи од тог броја, тај део простора претраге се одмах може одсећи и нема потребе генерисати све подскупове у којима су та два прва елемента укључена (јер унапред знамо да ниједан од њих неће представљати задовољавајуће решење).
Ефикасност алгоритама заснованог на овом облику претраге увелико зависи од квалитета критеријума на основу којих се врши одсецање. Иако обично сложеност најгорег случаја остаје експоненцијална (каква је по правилу код алгоритама грубе силе тј. исцрпне претраге), пажљиво одабрани критеријуми одсецања могу одсећи јако велике делове претраге (који су често такође експоненцијалне величине у односу на димензије улазног проблема) и тиме значајно убрзати процес претраге.
Нагласимо и да неки аутори не праве експлицитну разлику између алгоритама грубе силе (исцрпне претраге) и алгоритама претраге са повратком и да у алгоритме типа претраге са повратком убрајају све алгоритме у којима се дрво које садржи сва потенцијална решења обилази у дубину.
Формулишимо општу схему рекурзивне имплентације претраге са
повратком. Претпостављамо, једноставности ради, да су параметри
процедуре претраге тренутни низ v (у коме се смештају торке
бројева који представљају кандидате за решења) и дужина тренутно
попуњеног дела низа k, при чему је низ алоциран тако да се
у њега може сместити и најдуже решење. Такође, претпостављамо да на
располагању имамо функцију odsecanje која проверава да ли
је тренутна торка смештена у низ (на првих k позиција)
кандидат да буде решење или део неког решења. Претпостављамо и да знамо
да ли тренутна торка представља решење (то утврђујемо функцијом
jestePotencijalnoResenje, међутим, у реалним ситуацијама се
тај услов често сведе или на то да је увек тачан, што се дешава када је
сваки чвор дрвета потенцијални кандидат за решење или на то да је тачан
само у листовима, што се детектује тако што се провери да је
k достигло дужину низа v). На крају,
претпостављамо и да за сваку торку дужине k можемо
експлицитно одредити све кандидате за вредност на позицији
k (позивом функције kandidati(v, k)).
Рекурзивну претрагу тада можемо реализовати наредним (псеудо)кодом.
void pretraga(const vector<int>& v, int k) {
if (odsecanje(v, k))
return;
if (jesteResenje(v, k))
ispisi(v, k);
for (int x : kandidati(v, k)) {
v[k] = x;
pretraga(v, k+1);
}
}Алтернативно, провере уместо на улазу у функцију можемо вршити пре рекурзивних позива (чиме се мало штеди на броју рекурзивних позива, али се понекад имплементација може мало закомпликовати).
void pretraga(vector<int>& v, int k) {
if (jesteResenje(v, k))
ispisi(v, k);
for (int x : kandidati(v, k)) {
v[k] = x;
if (!odsecanje(v, k+1)) {
pretraga(v, k+1);
}
}
}Рекурзије је могуће ослободити се уз коришћење стека.
У свим чворовима који представљају кандидате за решење (то су обично
потпуно попуњене торки бројева) потребно је потпуно прецизно испитати да
ли је текући кандидат исправно тј. оптимално решење. То значи да у
претходном коду функција jesteResenje мора потпуно прецизно
да детектује да ли трентуна торка јесте или није исправно тј. оптимално
решење (нити сме исправно решење да прогласи неисправним, јер ће се тада
оно пропустити, нити сме неисправно решење да прогласи исправним, јер ће
се тада оно грешком појавити у списку решења). Са друге стране, у
чворовима у којима се проверавају парцијално попуњена решења, провера
критеријума одсецања не мора бити потпуно прецизна — са једне стране
допуштено је да се не одсеку делови дрвета у којима нема решења (тиме
алгоритам остаје коректан, али је неефикаснији), међутим, ако се
одсецање изврши морамо бити апсолутно сигурни да се у одсеченом делу
дрвета не налази ниједно исправно решење тј. да се не налази се
оптимално решење. У претходном коду то значи да када функција
odsecanje врати вредност тачно, морамо бити апсолутно
сигурни да се тренутна торка смештена на првих k позиција у
низу v не може никако допунити до исправног тј. оптималног
решења (јер бисмо у супротном пропустили нека решења). Са друге стране,
та функција може да врати вредност нетачно практично било када и тиме
неће бити нарушена коректност (али се нарушава ефикасност). У пракси се
понекад дешава да је веома компликовано направити функцију
odsecanje која потпуно прецизно одређује да ли се торка
може продужити до траженог решења проблема тако да се задовољавамо
критеријумима одсецања који се могу релативно једноставно проверити, а
гарантују коректност.
Додатно убрзавање алгоритма може да се направи ако се на неки начин
може дефинисати функција која понекад може да погоди вредност
x коју треба уписати на позицију k, без
испробавања различитих кандидата. На пример, ако се приликом попуњавања
магичног квадрата (квадрата у ком су бројеви распоређени тако да све
врсте, све колоне и обе дијагонале имају исти, унапред познат, збир) у
некој врсти попуне сви елементи осим једног, лако можемо да израчунамо
која вредност мора да буде уписана на том преосталом месту. Такве кораке
зовемо кораци закључивања (енгл. inferrence). Ни у овом
случају није потребна потпуна прецизност. Само је битно обезбедити да
када се закључивањем предложи нека конкретна вредност, да је остале
могућности безбедно одсећи, јер се међу њима не крије ниједно исправно
решење. Са друге стране, ако је закључивање превише компликовано
остварити у неком кораку претраге, оно се може прескочити (алгоритам је
коректан и без икаквог облика закључивања).
Претходне функције исписују сва решења проблема тј. све торке које задовољавају дате услове. Претрагу је могуће прекинути и након проналаска првог решења (тада функција обично враћа податак о томе да ли јесте или није пронашла решење у делу дрвета који претражује).
bool pretraga(const vector<int>& v, int k) {
if (odsecanje(v, k))
return false;
if (jesteResenje(v, k)) {
ispisi(v, k);
return true;
}
for (int x : kandidati(v, k)) {
v[k] = x;
if (pretraga(v, k+1))
return true;
}
return false;
}С обзиром на то да се исцрпна претрага, али и претрага са одсецањем често реализују алгоритмима претраге у дубину и у ширину, приказаћемо неколико задатака који користе ове алгоритме.
Код решавања оптимизационих проблема, одсецање може да наступи и када се процени да у делу дрвета које се тренутно претражује не постоји решење које је боље од најбољег тренутно пронађеног решења. Дакле, решења пронађена у досадашњем делу претраге се користе да би се одредиле границе на основу којих се врши одсецање у другим деловима претраге. Овакав облик оптимизације назива се понекад гранање са ограничавањем (енгл. branch and bound).
Бектрекинг и груба сила
У наставку ћемо разматрати проблеме следећег типа:
Испитати да ли постоји неки комбинаторни објекат (често представљен торком бројева) који задовољава неке дате услове. Овакви проблеми се називају проблеми задовољавања ограничења (енгл. constraint satisfaction problems, CSP). На пример, потребно је проверити да ли постоји неки подскуп датог скупа бројева чији је збир једнак датој вредности.
Међу свим комбинаторним објектима који задовољавају неке дате услове наћи најбољи тј. наћи онај објекат на коме је вредност неке дате функције минимална или максимална. Овакви проблеми се називају проблеми оптимизације уз ограничења (енгл. constraint optimization problems, COP). Ови проблеми се називају и проблеми комбинаторне оптимизације.
Овакви проблеми се често решавају разним варијантама алгоритама претраге у којима се набрајају и проверавају неки кандидати за решења.
Алгоритми грубе силе подразумевају да се у претрази исцрпно наброје сви кандидати за решење и да се за сваког од њих провери да ли задовољава услов (ако је потребно пронаћи било који елемент који задовољава дати услов) или да ли је оптималан (ако је потребно пронаћи елемент који минимализује или максимализује дату циљну функцију). Сви кандидати се понекада могу набројати једноставно, угнежђеним петљама, док је некада потребно користити неки сложенији поступак за набрајање одређене фамилије комбинаторних објеката (комбинација, пермутација, варијација, подскупова, партиција итд. али и других, специфичних фамилија комбинаторних објеката).
Алгоритми претраге са повратком тј. бектрекинг (енгл. backtracking) побољшавају технику грубе силе тако што врше провере и током генерисања кандидата за решења и тако што се одбацују парцијално попуњени кандидати, за које се може унапред утврдити да се не могу проширити до исправног тј. оптималног решења. Дакле, бектрекинг подразумева да се током обиласка у дубину дрвета којим се представља простор потенцијалних решења одсецају они делови дрвета за које се унапред може утврдити да не садрже ни једно решење проблема тј. да не садрже оптимално решење, при чему се одсецање врши и у чворовима блиским корену који могу да садрже и само парцијално попуњене кандидате за решења. Дакле, уместо да се чека да се током претраге стигне до листа (или евентуално унутрашњег чвора који представља неког кандидата за решење) и да се провера задовољености услова или оптималности врши тек тада, приликом претраге са повратком провера се врши у сваком кораку и врши се провера парцијално попуњених решења (обично су то неке парцијално попуњене торке бројева).
На пример, ако се проверава да ли постоји подскуп неког скупа чији је збир елемената једнак датом броју и ако се установи да прва два елемента полазног скупа имају збир већи од тог броја, тај део простора претраге се одмах може одсећи и нема потребе генерисати све подскупове у којима су та два прва елемента укључена (јер унапред знамо да ниједан од њих неће представљати задовољавајуће решење).
Ефикасност алгоритама заснованог на овом облику претраге увелико зависи од квалитета критеријума на основу којих се врши одсецање. Иако обично сложеност најгорег случаја остаје експоненцијална (каква је по правилу код алгоритама грубе силе тј. исцрпне претраге), пажљиво одабрани критеријуми одсецања могу одсећи јако велике делове претраге (који су често такође експоненцијалне величине у односу на димензије улазног проблема) и тиме значајно убрзати процес претраге.
Нагласимо и да неки аутори не праве експлицитну разлику између алгоритама грубе силе (исцрпне претраге) и алгоритама претраге са повратком и да у алгоритме типа претраге са повратком убрајају све алгоритме у којима се дрво које садржи сва потенцијална решења обилази у дубину.
Формулишимо општу схему рекурзивне имплентације претраге са
повратком. Претпостављамо, једноставности ради, да су параметри
процедуре претраге тренутни низ v (у коме се смештају торке
бројева који представљају кандидате за решења) и дужина тренутно
попуњеног дела низа k, при чему је низ алоциран тако да се
у њега може сместити и најдуже решење. Такође, претпостављамо да на
располагању имамо функцију odsecanje која проверава да ли
је тренутна торка смештена у низ (на првих k позиција)
кандидат да буде решење или део неког решења. Претпостављамо и да знамо
да ли тренутна торка представља решење (то утврђујемо функцијом
jestePotencijalnoResenje, међутим, у реалним ситуацијама се
тај услов често сведе или на то да је увек тачан, што се дешава када је
сваки чвор дрвета потенцијални кандидат за решење или на то да је тачан
само у листовима, што се детектује тако што се провери да је
k достигло дужину низа v). На крају,
претпостављамо и да за сваку торку дужине k можемо
експлицитно одредити све кандидате за вредност на позицији
k (позивом функције kandidati(v, k)).
Рекурзивну претрагу тада можемо реализовати наредним (псеудо)кодом.
void pretraga(int[] v, int k) {
if (odsecanje(v, k))
return;
if (jesteResenje(v, k))
ispisi(v, k);
foreach (int x in kandidati(v, k)) {
v[k] = x;
pretraga(v, k+1);
}
}Алтернативно, провере уместо на улазу у функцију можемо вршити пре рекурзивних позива (чиме се мало штеди на броју рекурзивних позива, али се понекад имплементација може мало закомпликовати).
void pretraga(int[] v, int k) {
if (jesteResenje(v, k))
ispisi(v, k);
foreach (int x in kandidati(v, k)) {
v[k] = x;
if (!odsecanje(v, k+1)) {
pretraga(v, k+1);
}
}
}Рекурзије је могуће ослободити се уз коришћење стека.
У свим чворовима који представљају кандидате за решење (то су обично
потпуно попуњене торки бројева) потребно је потпуно прецизно испитати да
ли је текући кандидат исправно тј. оптимално решење. То значи да у
претходном коду функција jesteResenje мора потпуно прецизно
да детектује да ли трентуна торка јесте или није исправно тј. оптимално
решење (нити сме исправно решење да прогласи неисправним, јер ће се тада
оно пропустити, нити сме неисправно решење да прогласи исправним, јер ће
се тада оно грешком појавити у списку решења). Са друге стране, у
чворовима у којима се проверавају парцијално попуњена решења, провера
критеријума одсецања не мора бити потпуно прецизна — са једне стране
допуштено је да се не одсеку делови дрвета у којима нема решења (тиме
алгоритам остаје коректан, али је неефикаснији), међутим, ако се
одсецање изврши морамо бити апсолутно сигурни да се у одсеченом делу
дрвета не налази ниједно исправно решење тј. да се не налази се
оптимално решење. У претходном коду то значи да када функција
odsecanje врати вредност тачно, морамо бити апсолутно
сигурни да се тренутна торка смештена на првих k позиција у
низу v не може никако допунити до исправног тј. оптималног
решења (јер бисмо у супротном пропустили нека решења). Са друге стране,
та функција може да врати вредност нетачно практично било када и тиме
неће бити нарушена коректност (али се нарушава ефикасност). У пракси се
понекад дешава да је веома компликовано направити функцију
odsecanje која потпуно прецизно одређује да ли се торка
може продужити до траженог решења проблема тако да се задовољавамо
критеријумима одсецања који се могу релативно једноставно проверити, а
гарантују коректност.
Додатно убрзавање алгоритма може да се направи ако се на неки начин
може дефинисати функција која понекад може да погоди вредност
x коју треба уписати на позицију k, без
испробавања различитих кандидата. На пример, ако се приликом попуњавања
магичног квадрата (квадрата у ком су бројеви распоређени тако да све
врсте, све колоне и обе дијагонале имају исти, унапред познат, збир) у
некој врсти попуне сви елементи осим једног, лако можемо да израчунамо
која вредност мора да буде уписана на том преосталом месту. Такве кораке
зовемо кораци закључивања (енгл. inferrence). Ни у овом
случају није потребна потпуна прецизност. Само је битно обезбедити да
када се закључивањем предложи нека конкретна вредност, да је остале
могућности безбедно одсећи, јер се међу њима не крије ниједно исправно
решење. Са друге стране, ако је закључивање превише компликовано
остварити у неком кораку претраге, оно се може прескочити (алгоритам је
коректан и без икаквог облика закључивања).
Претходне функције исписују сва решења проблема тј. све торке које задовољавају дате услове. Претрагу је могуће прекинути и након проналаска првог решења (тада функција обично враћа податак о томе да ли јесте или није пронашла решење у делу дрвета који претражује).
bool pretraga(int[] v, int k) {
if (odsecanje(v, k))
return false;
if (jesteResenje(v, k)) {
ispisi(v, k);
return true;
}
foreach (int x in kandidati(v, k)) {
v[k] = x;
if (pretraga(v, k+1))
return true;
}
return false;
}С обзиром на то да се исцрпна претрага, али и претрага са одсецањем често реализују алгоритмима претраге у дубину и у ширину, приказаћемо неколико задатака који користе ове алгоритме.
Код решавања оптимизационих проблема, одсецање може да наступи и када се процени да у делу дрвета које се тренутно претражује не постоји решење које је боље од најбољег тренутно пронађеног решења. Дакле, решења пронађена у досадашњем делу претраге се користе да би се одредиле границе на основу којих се врши одсецање у другим деловима претраге. Овакав облик оптимизације назива се понекад гранање са ограничавањем (енгл. branch and bound).