Previous Contents Next

13   Kombinatorische Suche und Heuristiken

Literatur: Meist aus Kapitel 5 von [Ski97].
Inhalt Backtracking Einschr"ankung der Suche Heuristiken
Backtracking
Backtracking (2)




backtrack(A) =       // A = Vektor/Array $(a_1,\ldots ,a_n)$
  compute $S_1$;     // m"ogliche Loesungen fuer 1. Position
  k := 1;
  while k > 0 
  do
    while $S_k \not= \emptyset$
    do
      $a_k$ = naechstes Element aus $S_k$;
      $S_k := S_k\without a_k$;
      if $A = (a_1,a_2,\ldots, a_k)$ Loesung, speichere sie fi;
      k := k+1;
      berechne S_k
    done;
    k := k-1                  // ``Backtrack''
  done



Backtracking (3)




backtrack-dfs(A,k) =
  if   $A  = (a_1,a_2,\ldots, a_k)$ Loesung, 
  then speichere sie
  else k := k+1;
       compute $S_{k}$;
       while $S_{k} \not= \emptyset$
       do
         Waehle ein Element $a$ aus $S_k$.
         $a_{k} := a$;
         $S_k := S_k\without a$;
         backtrack-dfs(A, k)
       done
   fi



Beispiele f"ur kombinatorische Suche
Beschr"ankung des Suchraumes
Beispiel: Bandbreitenminimisierung


allgemeine Heuristiken
February 5, 2002
Previous Contents Next