Backtracking

Der folgende Backtracking-Algorithmus bestimmt alle Wege, die von einem gegebenen Startknoten zu einem gegebenen Zielknoten führen. Es ist leicht einzusehen, dass dieser Algorithmus exponentielle Laufzeit haben muss.

Die Startmethode trifft dazu alle Vorbereitungen, um das Backtracking in Gang zu setzen.

public void sucheWeg(Graph g, String vonID, String nachID) {

    g.setAllVertexMarks(false); 

    Vertex vonKnoten = g.getVertex(vonID);
    Vertex nachKnoten = g.getVertex(nachID);

    List<Vertex> knotenliste = new List<Vertex>();
    vonKnoten.setMark(true); // Markiere den Startknoten
    knotenliste.append(vonKnoten);

    backtrack(g, vonKnoten, nachKnoten, knotenliste); // Starte die Rekursion!
}

Die zentrale Idee des eigentlichen Backtracking-Algorithmus besteht darin, dass ausgehend von einem bislang ermittelten Pfad mit seinem bisherigen Endknoten ein Weg beginnend mit dem bisherigen Endknoten und endend mit dem gegebenen Endknoten gefunden werden soll. Das Backtracking sorgt dafür, dass für jedes Zwischenergebnis (also jeden Zwischenpfad) alle weiteren möglichen Pfade gesucht werden.

private void backtrack(Graph g, Vertex vonKnoten, Vertex nachKnoten, List<Vertex> weg) {

    if (vonKnoten == nachKnoten) { // Ziel schon erreicht?
        String hilf = druckeWegAus(g, weg);
        System.out.println(hilf);
    }
    else {

        List<Vertex> nachbarKnoten = g.getNeighbours(vonKnoten);
        nachbarKnoten.toFirst();

        while (nachbarKnoten.hasAccess()) { // Bearbeite alle Nachbarknoten

            Vertex knoten = nachbarKnoten.getContent();

            if (!knoten.isMarked()) {
                knoten.setMark(true);
                weg.append(knoten);

                backtrack(g, knoten, nachKnoten, weg); // Suche ueber diesen Nachbarn weiter nach dem Ziel

                knoten.setMark(false);
                weg.toLast();
                weg.remove();
            }

            nachbarKnoten.next();
        }
    } 

}

Zum Ausdrucken eines vollständig gefundenen Pfades vom Start- zum Endknoten wird eine Hilfsmethode verwendet, die hier der Vollständigkeit halber mit angegeben ist.

private String druckeWegAus(Graph g, List<Vertex> wegliste) {

    // Bestimme zunaechst die Weglaenge
    double wegLaenge = 0;
    wegliste.toFirst();
    Vertex wegKnoten1 = wegliste.getContent();
    wegliste.next();

    while (wegliste.hasAccess()) {
        Vertex wegKnoten2 = wegliste.getContent();
        Edge e = g.getEdge(wegKnoten1, wegKnoten2);
        double distanz = e.getWeight();
        wegLaenge = wegLaenge + distanz;
        wegKnoten1 = wegKnoten2;
        wegliste.next();
    }

    // Baue Zeichenkette zusammen
    wegliste.toFirst();
    String s = wegLaenge + ": ";

    while (wegliste.hasAccess()) {
        Vertex wegKnoten = wegliste.getContent();
        s = s + wegKnoten.getID()+" ";
        wegliste.next();
    }

    return s+"\n";
}

results matching ""

    No results matching ""