13   Kombinatorische Suche und Heuristiken

Literatur: Meist aus Kapitel 5 von [Ski97].

Inhalt Backtracking ·Einschr"ankung der Suche ·Heuristiken

• Backtracking: systematisches Ablaufen/Generieren aller m"oglichen L"osungen/Konfigurationen (``exhaustiv'') (vgl. Graphsuche)
• m"oglichst keine L"osung doppelt generieren
• Darstellung
  • Konfiguration A = (a₁, a₂,..., a_n), mit a_i Î S_i f"ur jede Position i Î {1,..., n}
  • Þ Suchraum, Konfigurationsraum: Õ_i=1ⁿ S_i.
• Suchen mittels Backtracking:
  • erweitere eine Teill"osung (a₁,... a_k) f"ur ein k £ n mit jeweils allen Elementen f"ur Position k+1 (allen Elementen aus S_k+1
  • falls keine Erweiterung m"oglich: Backtracking
• Vergleiche: Tiefensuche bei Graphsuche

• Backtracking: konstruiert einen Baum von Teill"osungen.
  • Knoten: Teill"osungen
  • Kanten: zwischen Teill"osungen a und a', falls a' aus a durch einen Erweiterungsschritt des Algorithmusses erzeugt wurde

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

• Naheliegend: rekursive Tiefensuche zur Durchlaufen
• Vergleiche: Tiefensuche auf Graphen: die Mengen S_k sind "uber die Nachbarschaften/Adjazenzen gegeben
• andere Durchlaufordnungen f"ur komb. Suche m"oglich, meist Tiefensuche am besten ( Speicherplatz)²⁹

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

• Generierung aller Permutationen von {1,... n}:
  • ``anwendbar'' bei Problemem wie Handlungsreisender<sup>30</sup>
  • Suchraum der Gr"o"se n!
  • Darstellung: Array A, S<sub>i</sub>: Menge der Elemente die nicht in A[1] bis A[n-1] auftauchen
  • volle L"osung (d.h. eine Permutation): k = n +1
  • Bild: Lauf des Backtracking-Algorithmusses
• Generierung aller Teilmengen einer Menge {1,..., n}
  • ``anwendbar'' u.a. bei Problemen der Logik/boolesche Algebra/Schaltkreisentwurf
  • Suchraum der Gr"o"se 2ⁿ
  • Darstellung: boolescher Array,³¹ S_k = {,}.
  • Bild: Lauf durch den Suchraum
• Konstruktion aller Pfade eines Graphen
• etc.

• Pruning
  • exhaustive/komb. Suche: findet L"osung, falls existent
  • aber: leidet unter kombinatorischer Explosion
  • Problemabh"angig: oft Einschr"ankung des Suchraums m"oglich
  • Þ Pruning = ``Stutzen'' des Suchbaumes: Abbruch der Exploration des Suchraumes, sobald man erkennt, da"s eine Teill"osung nicht mehr zu einer vollst"andigen L"osung erweitert werden kann.
  • wichtige (und selbstverst"andliche) algorithmische Optimierungsmethode
  • problemabh"angig
  • Beispiel: Problem des Handlungsreisenden:
    • schlecht: alle n!-Permutationen der St"adte ausrechnen, danach die Kosten der entsprechende Rundreisen
    • besser: bei Rundreise startend von v<sub>1</sub>: falls keine Kante von v<sub>1</sub> nach v<sub>2</sub>: generiere die (n-2)! Permutationen mit Pr"afix v<sub>1</sub>, v<sub>2</sub> ... nicht.
    • besser: die bislang beste Rundreise mit Kosten k Þ keine Exploration von Teil-Rundreisen mit gleichgro"sen oder h"oheren Kosten<sup>32</sup>
• Ausnutzen von Symmetrie
  • wichtiger Speziallfall von Pruning
  • Beispiel: Handlungsreisender: es reicht, einen Startknoten auszuw"ahlen (Rundreisen sind ``rotationssymmetrisch'')

• Bandwidth minimization
• Problem
  • gegeben: Graph G = (V, E), bzw. seine Adjazenzmatrix
  • gesucht welche Permutation p der Knoten aus V minimiert die L"ange der l"angsten Kante, wenn die Kanten linear angeordnet werden.

    min p

    {

    max (i,j)Î E

    |p(i) - p(j)|)}

• Anwendungen:
  • L"osungen linearer Gleichungen (Gausselimination); Bandbreite: max. Abstand eines nicht-Null Eintrags von der Hauptdiagonalen³³
  • Schaltkreisentwurf
  • ``Linearisierung'' von verzeigerten Strukturen (z.B. optimale (d.h, minimale Suchzeit) Speicherung von Hypertextdokumenten)
• NP-vollst"andig³⁴

• oft f"ur Optimierungsprobleme³⁵
• oft wichtig in der Praxis
• allerdings: allgemeine Heuristiken meist geschlagen von problemspezifischen Heuristiken
• Simulated Annealing
• genetische Algorithmen
• Neuronale Netze
• ...