Visszalépéses keresés (algoritmus)

A Programozás Wiki wikiből

A visszalépéses keresés (Backtracking) olyan esetekben használható, amikor a keresési tér fastruktúraként képzelhető el, amiben a gyökérből kiindulva egy csúcsot keresünk. Számtalan ilyen probléma található, a labirintusokban történő útkeresés, bizonyos mintaillesztési feladatok, a könyvtárszerkezetben történő keresés, egyes logikai játékok (pl. Rubik kocka) kirakása is vizzavezethető erre a problémára.

Az algoritmus lényege, hogy a kezdőpontból kiindulva megtesz egy utat, és ha valahol az derül ki, hogy már nem juthat el a célig, akkor visszalép egy korábbi döntési ponthoz, és ott más utat választ.

Az alap algoritmus kódja C++ nyelven:

   // igazat ad, ha az útvonal nem a célba vezet
   // ilyenkor step egy rossz lépés sorszáma
   bool erroneous( const Path & path, int & step );
 
   // módosítja az útvonalat úgy, hogy 
   // a step-edik lépésben (vagy az előtt) más
   // irányt választ. Hamissal tér vissza, ha ez lehetetlen
   bool increase( Path & path, int step );
 
   // visszalépéses keresés
   bool backtrack( Path & path ) {
      int i;
      while( erroneous( path, i ) {
         if ( ! increase( path, i )) 
            return false;
      } 
      return true;
   }

Ha az útvonalak valamiképpen sorbarendezhetők, és tudjuk biztosítani, hogy az increase függvény későbbi utat generáljon minden esetben, akkor (véges problématérben) az algoritmus biztosan véget ér.

Ha az erroneous függvény ezen felül mindig a legutolsó rossz döntés sorszámát adja vissza, és az increase nem hagy ki utakat, akkor az algoritmus megtalálja az első jó megoldást.

Ha az út érvényessége és a következő lépés meghatározásához elég a pillanatnyi helyet ismerni, akkor az útvonal ábrázolható veremmel. Bizonyos feladatok könnyebben kezelhetők, ha ilyenkor a programnyelv beépített vermét használjuk, és egy rekurzívan hívott függvénynek paraméterként csak az útvonal utolsó elemét adjuk át.

Pl. Visszalépéses keresés bináris fában:

   #include <string>
   using namespace std;
 
   // igazat ad, ha n célpont
   bool isgoal( const Node & n );
 
   // visszalépéses keresés bináris fában
   string bintreesearch( Node * n ) {
      string res="";
      if ( !n ) return res;
      if ( isgoal( *n ) ) return "goal";
      res = bintreesearch( n->left );
      if ( res != "" ) return res.insert( 0, "left " );
      res = bintreesearch( n->right );
      if ( res != "" )  return res.insert( 0, "right " );
      return "";
   }

A rekurzív megoldás átláthatóbbá teheti a kódot, de figyelni kell arra, hogy a programnyelv verme sem végtelen. Ha az utak hossza túlságosan nagy, az ilyenkor a program megszakadásához vezethet.

Ha a probléma nem fastruktúrával, hanem kört is tartalmazó gráffal írható le, akkor az érintett helyek halmazát is tárolni kell keresés közben. Erre szolgálnak a gráfkereső algoritmusok.