Branch and Bound

[Vorheriges Kapitel] [Vorherige Seite] [Inhaltsverzeichnis] [Nächste Seite] [Nächstes Kapitel]

TSM.om
PROCEDURE Solve(VAR (* read-only *) problem: Problem;
                state: State; city: City;
                VAR solution: State);
BEGIN
   Travel(problem, state, city);
   IF state.nofvisits = problem.nofcities THEN
      IF MinimalSoFar(problem, state, solution) THEN
         solution := state;
      END;
   ELSIF (solution.minlen = -1) OR
      (state.length + state.minleft < solution.minlen) THEN
      city := 0;
      WHILE city < problem.nofcities DO
         IF ~(city IN state.visited) THEN
            Solve(problem, state, city, solution);
         END;
         INC(city);
      END;
   END;
END Solve;

*Wenn nach einem Optimum oder einer Verbesserung gesucht wird, lassen sich viele Zweige abschneiden, die nur noch schlechtere Lösungen produzieren können.
 
*Diese Technik nennt sich Branch-And-Bound-Verfahren.
 

[Vorheriges Kapitel] [Vorherige Seite] [Inhaltsverzeichnis] [Nächste Seite] [Nächstes Kapitel]
Copyright © 1999 Andreas Borchert, in HTML konvertiert am 29.06.1999