What is a Backtracking algorithm?

Backtracking is a generic algorithm that seeks, by brute force, possible solutions to computational problems (typically problems of satisfying constraints).

• Incrementally, search for solution candidates and abandon each partial candidate C when C can not result in a solution valid.
• When your search arrives at one end of the data structure, as a terminal node of a tree, the algorithm performs a setback typically implemented through a recursion.

ExampleAlgorithm

boolacabou=FALSE;backtrack(inta[],intk,intn){intc[MAXCANDIDATOS];/*Candidatosparaapróximaposição*/intncandidatos;/*Númerodecandidatosparaapróximaposição*/inti;/*Contador*/if(e_uma_solucao(a,k,n)){processar_solucao(a,k,n);}else{k=k+1;construir_candidatos(a,k,n,c,&ncandidatos);for(i=0;i<ncandidatos;i++){a[k]=c[i];backtrack(a,k,n);if(acabou)return;}}}

BasicFeatures:

• Foreachrecursivecallthereareseveraloptionsthatcanbefollowed.Eg:Manyverticesmaybenext.
• Severaldatainthesubsetofinputdatanotyetincludedinthesolutionarecandidates.Itmaybethattheyallareandtheremaybeaconstraintreducingthenumberofcandidates.Eg:Onlyneighboringverticesarecandidatestobenext.
• Thealgorithmcantryarecursivecallforeachofthecandidates(solutionforexhaustiveresearch).Eg:TravelingClerktriesallpaths.
• Thealgorithmcanchooseoneorafewdataaccordingtoanycriteria.
• Thesearchprocesscreatesarecursivecalltree.Egallpartialpathsofthesalesman.
• Leavesofthistreeareoftwotypes:
  • Representsapossiblesolutiontotheproblem.
  • Representapointwherethealgorithmcouldnotgoahead(failure)withouthurtingsomepreconditionsothatthesolutiongenerateduntilthenisvalid.Ex:Pathfounduntilnowistoolong,thoughtherearestillverticestogoby.

PositivePoints:

• Easilyimplementaproblemthatwouldotherwisebemuchmorecomplexthanifresolved.
• LanguagesoftheLogicalProgrammingArea(PROLOG,KL-ONE,OPS5)oftenhavesomebuilt-inmechanismthatsupportsbacktracking.

NegativePoints:

• Backtrackingprograms,unlessyouprogramconstraints,alwaysexecuteanexhaustivesearchandwilltendtocombinatorialexplosion.
• Backtrackingprogramsarebynature,Combinatorics!
• NeedlotsofmemoryintheStack,sincetheamountoflocalvariablescarriedbyeachrecursivecallisdirectlyproportionaltothesizeoftheproblem.
• Thismeansthattheamountofmemoryrequiredforabacktrackingprogramcangrowexponentiallywiththesizeoftheproblem.

Whereapplicable:

Backtrackingisapplicableinsolvingvariousknownproblems,amongwhichwecanhighlight:

• TravelingClerk
• HorseRiding
• N-Queens
• FindSolutionsSpace
• GrahamExamination
• PermutationsGeneration
• MazeProblems

OBS:Youshouldbeawareofthecombinatorialexplosion.

  

Source: Backtracking