Frage von Donner12344323, 68

Übersetzung des Backtracking-Algorithmus Färbung?

Hallo zusammen,

für mein Matheseminar muss ich den Backtracking Algorithmus verstehen (siehe Bild). Um ehrlich zu sein hab ich jedoch keine richtige Ahnung von Java. Kann mir jemand erklären, was in den einzelnen Schritten des Algorithmuses passiert?

Tausend dank euch, ihr helft mir damit ungemein.

Lieben Gruß Johanna

Antwort
von ralphdieter, 11

Der Code ist in Pascal geschrieben, wobei jemand übel reingepfuscht hat: Die Variable color wurde teilweise auf deutsch übersetzt, die Herkunft von n (=|V|) muss man erraten, und noch ein paar andere Dinge.

Der Kern steht in der Funktion versuche(): Hier werden (rekursiv) alle ungefärbten Knoten eingefärbt und dann true zurückgegeben; wenn das nicht geht, wird kein weiterer Knoten gefärbt und false zurückgegeben.

Die Implementierung ist allerdings so schlecht, dass ich Backtracking besser direkt erkläre:

Backtracking:

Gegeben: Diskrete Variablen x = (x₁, x₂, ...)
               eine boolsche Bedingung erlaubt(x)

Gesucht: Eine Belegung von x mit erlaubt(x)

Eine rekursive Implementierung mit Backtracking funktioniert so:

löse():
  WENN alle x_i belegt sind:
  return erlaubt(x)
  SONST
  wähle ein unbelegtes x_i
FÜR ALLE Werte w von x_i:
belege x_i := w
WENN löse():
return true
# alles erfolglos durchprobiert :-(
x_i := unbelegt
return false

Salopp auf das Färbeproblem bezogen läuft das so ab:

Schnapp Dir einen ungefärbten Knoten und gib ihm eine Farbe. Dann löse das Restproblem. Wenn's nicht klappt, versuch's mit einer anderen Farbe; und wenn Du alle Farben erfolglos durchprobiert hast, entfärbe den Knoten und gib auf. (Der Aufrufer wird's dann mit einer anderen Vorbelegung versuchen. Das nennt man dann Backtracking.)

Zu beachten ist, dass x global ist und die x_i neben den ordentlichen Werten auch unbelegt (null, -1, o.ä.) sein können. Sobald eine Lösung gefunden ist, steht sie in diesem globalen x. Der Algorithmus wird dann beendet, und eine zweite Lösung ist danach nicht ohne weiteres erreichbar.

Effektiv werden alle Belegungen von x vollständig bis zur erstbesten Lösung enumeriert. Dabei bietet sich Rekursion an, aber es geht auch mit einer einfachen Schleife. Auf jeden Fall kann das schon bei kleinen Problemen ziemlich lang dauern. Eine Möglichkeit zur Beschleunigung drängt sich hier so stark auf, dass sie oft in einem Atemzug mit Backtracking genannt wird:

Backtracking mit Cut:

erlaubt(x) prüft eine vollständige Belegung von x. Oft kann man daraus eine Funktion werte(x, x_i) ableiten, die eine sinnvolle Teilmenge von Werten für x_i bestimmt, nachdem x schon teilweise belegt ist.

Statt "FÜR ALLE w" heißt das dann nur noch "FÜR w∈werte(x, x_i)".

Im Färbeproblem darf man nur Farben setzen, die nicht in der Nachbarschaft vorkommen. Das schränkt die Suche massiv ein, wenn z.B. schon x₁ und x₂ benachbart sind:

  • Die Rohversion enumeriert nach x₁=blau, x₂=blau alle Belegungen für x₃... und verwirft sie gleich wieder.
  • Die verbesserte Version überspringt den Wert x₂=blau sofort und wählt eine andere Farbe.

So erschlägt man viele Probleme, bei denen eine vollständige Enumeration viel zu lange dauern würde. Und als Bonus kann man die Funktion erlaubt(x) abkürzen, indem man voraussetzt, dass nur passende werte(x, x_i) benutzt wurden. Im Färbeproblem reicht es sogar, immer eine Farbe zu wählen, die von den bisher belegten Nachbarn verschieden ist. Unter dieser Voraussetzung ist erlaubt(x) immer wahr. In Deinem Code steht da nur noch "q:=true".

Weitere Verbesserungen:

Auch mit Cut ist der Lösungsraum in der Praxis noch viel zu groß, um ihn ganz zu durchsuchen. Deshalb baut man Heuristiken ein:

  • Welche Variable x_i wird als nächstes belegt? Am besten ist eine, bei der ein zielführender Wert leicht erraten werden kann. Im Färbeproblem wird das wohl der Knoten mit den wenigsten unbelegten Nachbarn und/oder den wenigsten noch erlaubten Farben sein.
  • In welcher Reihenfolge belegt man x_i mit Werten? Der vielversprechendste sollte wohl zuerst kommen. Beim Färbeproblem sehe ich allerdings nichts, was eine bestimmte Farbe vor einer anderen auszeichnen könnte.

Mit geschickten Heuristiken findet man oft schnell eine Lösung, selbst wenn der gesamte Lösungraum gigantisch groß ist. Aber eine Garantie gibt es dafür nicht.

Kritik am Code:

  • versuche(): Die Abbruchbedingung steht nicht am Anfang der Rekursion. Das verkompliziert den Code und funktioniert nicht bei leeren Graphen.
  • versuche() ist eigentlich eine boolsche Funktion. Warum ist sie als Prozedur mit Argument "var q: boolean" implementiert?
  • versuche() bekommt den nächsten zu belegenden Knoten i als Argument übergeben. Aber eigentlich sollte die Funktion diesen selbst aussuchen.
  • möglich(x, x_i, w) untersucht bei jeder Farbe w alle Nachbarn von x_i. Das ist bei vielen Farben und vielen Nachbarn nicht effizient. Eine Funktion werte(x, x_i) kann alle w in einem Rutsch prüfen.
  • Der Graph G wird gar nicht verwendet, und die Funktion möglich() zaubert die Nachbarn j von Knoten i aus dem Hut.

Insgesamt sieht es so aus, als ob da jemand gerade Pascal lernt und das Prinzip der Rekursion noch nicht ganz begriffen hat...

Kommentar von Donner12344323 ,

Oh das hat mir sehr viel weitergeholfen.
Ganz lieben Dank dir!

Keine passende Antwort gefunden?

Fragen Sie die Community