Backtracking

Problemtyp

Aus einer gegebenen Menge von Teilen soll ein Objekt konstruiert werden.
Teile können miteinander unverträglich sein.
Teile dürfen mehrfach verwendet werden.
Die Reihenfolge, in der die Teile ausgewählt werden, ist egal.
Gesucht ist eine Lösung, die mit minimal vielen Teilen auskommt.

Varianten

Teile duerfen nur einfach verwendet werden.
Die Reihenfolge ist nicht egal.
Alle optimalen Lösungen sind gesucht.

Beispielproblem

IOI 1994 - Day 2 - Problem 2: The Buses

Instantiierung

Teile = Busrouten
Objekt = Fahrplan

Programmschema

part = Typ der Teile
N = maximale Größe des Objekts (in Teilen)
M = maximale Anzahl von verschiedenen Teilen

part cand[M];     /* zur Verfügung stehende Teile */ 
part sol[N];      /* aktuelle partielle Lösung    */
part bestsol[N];  /* beste bisher gefundene Lösung */
int best;         /* Wert der bisher besten Lösung */
int numcands;     /* Anzahl der zur Verfügung stehenden Teile */

void visit (int n, int start)
{
  int i;

  if (n>=best) return;  
  if (object is finished)
    {
      best = n;
      for (i=0; i<best; i++)
	bestsol[i] = sol[i];
      return;
    }
  if (n+1==best) return;    
  for (i=start; i<numcands; i++)
    if (part i is consistent with the current partial object)
      {
	sol[n] = cand[i];
	insert part i into object
	visit(n+1,i);
	remove part i from object
      }
}

int main()
{
  .
  .
  best = oo;
  visit(0,0);
  .
  .
}

Optimierung

Man sortiere die Teile zuerst absteigend nach ihrem Beitrag zur Lösung. Sei der Beitrag des i-ten Teils mit cand[i].value bezeichnet. Während des Backtrackings bezeichne gap eine untere Schranke für den Abstand von der aktuellen partiellen Lösung zur vollständigen Lösung. Dann kann abgebrochen werden, wenn (best-n-1)*cand[i].value < gap gilt.
Im Algorithmus sind folgende Änderungen vorzunehmen:


int cmp (const void* a, const void* b)
{
  return ((part*)b)->value - ((part*)a)->value;
}

void visit (int n, int start)
{
  .
  .
  for (i=start; i<numcands && (best-n-1)*cand[i].value>=gap; i++)
    if (part i is consistent with the current partial object)
      {
	...
      }
}

int main()
{
  .
  .
  qsort(cand,numcands,sizeof(part),cmp);
  best = 0;
  visit(0,0);
  .
  .
}

24.9.1996

Mark Dettinger