Brute-Force & Backtracking-Algorithmus

**mrhappiness** · 23.02.2003, 12:02

http://www.educeth.ch/informatik/vor.../backtracking/

hth!

**Chefkoch** · 23.02.2003, 12:25

Danke, Begriff Back-tracking ist jetzt klar, allerdings denke ich wäre eine Function die alle möglichen Lösungen durchrechnet angebrachter. So weit ich informiert bin heisst man soetwas Brute-force. Kann mir jemand einen Beispielcode geben?

**TBT** · 23.02.2003, 12:41

wie wäre es dafür mit Rekursion, dürfte mit 5-10 Zeilen erschlagen sein

**wahsaga** · 23.02.2003, 14:54

schriebst du nicht im ersten thread, dass das was für die schule sei?

wenn du nicht selber auf eine lösung kommst, dann sag deinem lehrer, dass du es mit dem was du dort bisher gelernt hast nicht lösen kannst, aber lass uns nicht hier deine hausaufgaben machen, um sie nachher stolz als dein werk zu präsentieren.

**Chefkoch** · 23.02.2003, 15:15

Hey wahsaga, nur damit eins klar ist, ich sagte das ist für die Schule, ich sagte jedoch nicht, dass wir in der Schule PHP programmieren oder?
Wir haben die Aufgabe für Erdkunde herauszufinden, wie die Fläche zu stande kommt, welche Hilfsmittel wir hierfür verwenden bleibt uns überlassen.

**Titus** · 23.02.2003, 16:21

Auch wenn du alle Lösungen suchst, ist Backtracking schneller als brute force. Denn wenn die Flächensumme zu groß wird, geht das backtracking einen oder mehrere Schritte zurück.
Das ist natürlich ein wenig schwieriger zu implementieren als die Variante, die nur eine Lösung findet.

Ein paar Tipps zur Implementation:

1. Sortier die Werte absteigend; damit kriegst du eine möglichst kurze Kombination
und verhindest zu aufwendiges Zurueckgehen - mehr als ein Schritt wird bei der eine-Lösung-Variante nie nötig sein.

2. Du solltest dir beim Sortieren dir Indizes merken, aus deren Werten du deine Testsumme zusammen setzt. arsort ist dafür gut.

Die an sich schönen Array-Funktionen kannst du für das wandern im Werte-Array nicht gebrauchen, da dabei die Schlüssel verloren gehen.
Und du brauchst zwei Stacks (einen für Keys, den anderen für die Werte);
auf denen arbeitest du mit array_push und array_pop.

Die alle-Lösungen-Variante kannst du beschleunigen, indem du Teilsummen suchst, die dem Wert eines anderen Elements entsprechen.
Ist dieser Wert in einer Lösung enthalten, so findet man weitere Lösungen, indem man ihn durch die Elemente der Teilsummen ersetzt.

Außerdem kannst du für allgemeinere Aufgaben noch ein paar Sonderfälle abfangen:
- Summe aller Werte = gesuchter Wert: nur eine Lösung, und zwar die maximale
- Summe aller Werte < gesuchter Wert: keine Lösung

**Titus** · 23.02.2003, 16:45

noch eins: Solltest du mal negative Werte dabei haben (bei diesem Problem nicht, aber wer weiß

), dann findet reines Backtracking unter Umständen keine einzige Lösung.
Auch die beiden Sonderfälle fallen weg.

Aber es geht immer noch schneller als mit brute force - man teile die Werte auf in zwei Arrays (eins mit positiven, eins mit negativen Werten); dann gibt es weitere Lösungswege:

z.B. brute force und backtracking gemischt
Man nehme das kleinere Array mit roher Gewalt vor:
alle möglichen Kombinationen werden in ein drittes Array gepackt, das nach der Summe der Werte aufgeschlüsselt ist.
diffsumme => array(kombi1, kombi2, ...)

dann sucht man für jede Summe+Differenzsumme die Lösungen im größeren Array per Backtracking.

z.B. geschachteltes Backtracking
Backtracking im großen Array wie gehabt, aber:
Ist die Summe zu groß, geht es erst einen Schritt zurück, wenn die Differenz zum gesuchten Betrag größer ist als die Summe der Werte im kleinen Array.
Bis dahin wird im kleinen Array nach Lösungen für die Differenz gesucht - natürlich auch per Backtracking.
Die Ergebnisse werden dann im oben erwähnten dritten Array gespeichert, für den Fall dass diese Differenz noch einmal auftritt.

**Chefkoch** · 23.02.2003, 19:30

Vielen Dank für die ausführlich Antwort, ich denke jetzt bekomm ichs hin.

Brute-Force & Backtracking-Algorithmus