Grundlegendes zum Backtracking in C ++

12

Ich verstehe die Grundlagen von C ++ gut und verstehe auch, wie Rekursion funktioniert. Ich bin auf bestimmte Probleme gestoßen, wie das klassische Acht-Königinnen-Problem und das Lösen eines Sudoku mit Backtracking.

Mir ist klar, dass ich in dieser Hinsicht ziemlich verloren bin. Ich kann mich anscheinend nicht mit dem Konzept abfinden, wieder in den Rekursionsstapel zurückzukehren und erneut zu beginnen, um das Problem zu lösen. Mit Stift und Papier scheint es einfach zu sein, aber wenn es darum geht, Code dafür zu schreiben, bin ich verwirrt, wie ich anfangen soll, diese Probleme in Angriff zu nehmen.

Es wäre hilfreich, wenn es ein Tutorial für Anfänger zum Zurückverfolgen gäbe oder wenn es ein gutes Buch gäbe, in dem dies behandelt wurde. Wenn jemand Licht in dieses Thema bringen oder mir Links zu anständigen Referenzen geben kann, wäre ich sehr dankbar.

Und ja, ich weiß, dass es in funktionalen Sprachen einfacher ist, aber ich möchte die Implementierung auch in imperativen Sprachen verstehen.

nikhil
quelle
Ich denke, das ist eine gute Frage, aber ich denke, es wäre besser, die Bitte zu betonen, jemandem das Zurückverfolgen zu erklären, indem er nach Tutorials oder anderen Ressourcen fragt. Eine ausführliche Erklärung der Art der Antwort schlägt jeden Tag eine Liste von Referenzen.
Adam Lear
Es wäre perfekt, wenn jemand eine detaillierte Erklärung geben könnte, aber ich hätte auch nichts dagegen, Referenzen nachzulesen. Ich weiß nur nicht, wo ich anfangen soll.
Nikhil

Antworten:

9

... Ich kann mich anscheinend nicht an das Konzept erinnern, wieder in den Rekursionsstapel zurückzukehren und erneut zu beginnen , um das Problem zu lösen.

Beim Backtracking fängst du nicht wieder an. Stattdessen durchlaufen Sie alle Optionen in der aktuellen Situation.

Denken Sie darüber nach, eine Lösung für ein Labyrinth zu finden. An einem Punkt, an dem Sie zwei verschiedene Pfade haben, versuchen Sie zuerst den linken. Wenn der linke nicht zum Ausgang führt, kehren Sie zum Punkt zurück und versuchen den anderen Weg. So funktioniert Backtracking. In 8 Q und anderen Problemen, bei denen Backtracking verwendet werden kann, liegt der verwirrende Teil in der Problemdomäne - wie Sie Ihre Optionen in einer bestimmten Situation deterministisch durchlaufen können.

BEARBEITEN : Das Folgende ist ein Pseudocode, der das Verständnis von Backtracking erleichtert.

# depending on the problem, backtracking is not necessarily calling the
# method itself directly. for now, let's just stick with the simple case.

def backtracking(state)
  option_list = state.get_all_options
  option_list.each {|option|
    state.apply option
    return resolved if state.is_resolved
    return resolved if backtracking(state) == resolved
    state.undo option
  }
  return not_resolved
end

Für 8Q frage:

  • state.get_all_options würde eine Liste der möglichen Positionen für die nächste Dame zurückgeben
  • state.is_resolved würde testen, ob alle Königinnen auf dem Brett sind und ob sie gut miteinander umgehen können.
  • state.apply und state.undo ändern die Karte, um eine Positionierung anzuwenden oder rückgängig zu machen.
Kodismus
quelle
Der erste rekursive Code, den ich (1984 mit Pascal) für eine Aufgabe geschrieben habe, war ein Labyrinthlösungsalgorithmus.
Gerry
Kennen Sie eine einfache Aufgabe, bei der ich tatsächlich Code schreiben kann, um das Gefühl für dieses Zeug zu bekommen.
Nikhil
@nikhil: fragst du, ob es ein einfaches Problem gibt? Es ist besser, Pseudocode zu schreiben, um das generische Routing von Backtracking zu demonstrieren. Ich werde es später in einer Antwort versuchen.
Codism
Ja genau, das wird am hilfreichsten sein.
Nikhil
Vielen Dank, ich habe in letzter Zeit ein paar Sachen gelesen. Langsam aber stetig verbessert sich mein Verständnis.
Nikhil
5

Sie haben ein Programm gesehen, um einen binären Baum zu durchlaufen, richtig? Es sieht aus wie das:

void walk(node* p){
  if (p == NULL) return;  // this is backtracking
  else if (WeWin(p)){
    // print We Win !!
    // do a Throw, or otherwise quit
  }
  else {
    walk(p->left);   // first try moving to the left
    walk(p->right);  // if we didn't win, try moving to the right
                     // if we still didn't win, just return (i.e. backtrack)
  }
}

Da ist dein Backtracking.

Du brauchst eigentlich keinen physischen Baum. Alles, was Sie brauchen, ist eine Möglichkeit, einen Zug zu machen und ihn später rückgängig zu machen oder zu sagen, ob Sie gewonnen haben oder ob Sie nicht weiter gehen können.

Mike Dunlavey
quelle
1
Können Sie keinen Bool / Int zurückgeben, um zu überprüfen, ob die Lösung im Teilbaum gefunden wurde? else{return walk(p->left)||walk(p->right));}keine Notwendigkeit für das erwartete Ergebnis zu werfen
Ratschen-Freak
@ratchet: Auf jeden Fall. Das ist auch eine sehr gute Möglichkeit. (Ich habe nur versucht, das Beispiel zu
vereinfachen
@MikeDunlavey Schneiden ist jedoch in der Praxis ziemlich wichtig.
1.