C - Backtracking Algorithmus: Weg zum Ausgang

Diese Seite verwendet Cookies. Durch die Nutzung unserer Seite erklären Sie sich damit einverstanden, dass wir Cookies setzen. Weitere Informationen

  • C - Backtracking Algorithmus: Weg zum Ausgang

    Moin!
    Ich habe eine Aufgabe die wie folgt aussieht!

    Die Voraussetzungen sieht wie folgt aus:

    Ich habe folgende baumartige Struktur:

    Quellcode

    1. typedef struct {
    2. int left, right;
    3. } pair;
    6. pair paare[] = {
    7. {1, 2}, {3, 4}, {5, 6}, {-1, 7},
    8. {8, 9}, {10, 11}, {12,-1}, {-1,-1},
    9. {13, 14}, {-1,-1}, {-1,-1}, {-1,-1},
    10. {-1,-1}, {15, 16}, {-1,-1}, {-1,-1}, {-2,-2}
    11. };
    Alles anzeigen


    1. Der Baum ist von 0 bis n-1 durchnummeriert.
    2. Knoten, die keinen linken bzw. rechten Sohn besitzen, haben stattdessen den Wert -1
    3. Die Wurzel hat den Wert 0
    4. Der Ausgänge besitzen den Wert -2

    Ich soll jetzt beginnend vom Eingang (0) einen Ausgang mittels Backtracking finden.
    Ich habe versucht den "Baum" zu zeichnen:
    [Blockierte Grafik: http://bildupload.sro.at/a/images/5.1.a_baum.JPG]

    (Keine Gewähr, dass er richtig ist)

    Mein Code sieht wie folgt dazu aus:



    Quellcode

    1. #include<stdio.h>
    3. typedef struct {
    4. int lnode, rnode;
    5. } node_t;
    7. node_t tree[] = {
    8. {1, 2}, {3, 4}, {5, 6}, {-1, 7},
    9. {8, 9}, {10, 11}, {12,-1}, {-1,-1},
    10. {13, 14}, {-1,-1}, {-1,-1}, {-1,-1},
    11. {-1,-1}, {15, 16}, {-1,-1}, {-1,-1}, {-2,-2}
    12. };
    15. int SearchExit (node_t *T, int node_no)
    16. {
    17. static int x=1;
    18. if(T[node_no].lnode==-2 || T[node_no].rnode==-2)
    19. {
    20. if(T[node_no].lnode==-2)
    21. printf("Ausgang beim linken Kind von Knoten %d gefunden\n",node_no);
    23. if(T[node_no].rnode==-2)
    24. printf("Ausgang beim rechten Kind von Knoten %d gefunden\n",node_no);
    25. return 1;
    26. }
    30. // zu erst immer links gehen
    31. //if(T[node_no].lnode!=1){
    32. if(SearchExit(T,(node_no+1))==1){ // nächster LINKER knoten - WIE?!??!?! UND vergleich auf 1 ist auch falsch, so ist sie immer wahr und er gibt automatisch die zeilen aus
    33. printf("%2d. Knoten: %d | LINKS\n",x++,node_no);
    34. return 1;
    35. }
    37. //}
    39. //if(T[node_no].rnode!=1){
    40. if(SearchExit(T,(node_no+1))==2){
    41. printf("%2d. Knoten: %d | RECHTS\n",x++,node_no);
    42. return 2;
    43. }
    45. //}
    49. return 0;
    51. }
    53. int main ( void )
    54. {
    57. if ( SearchExit(tree, 0) == 1 )
    58. printf("Ausgang gefunden!\n");
    59. else
    60. printf("Ausgang nicht gefunden!\n");
    63. return 0;
    64. }
    Alles anzeigen


    Nun hab eich ein problem!
    Er findet zwar den Ausgang, aber irgendwie scheint er immer nur die erste bedingung anzuwählen! Er geht gar nicht in die zweite Bedingung für den rechten Knoten rein!!
    Und er durckt jeden knoten aus! Dass das Programm jeden Knoten durchgeht, ist mir klar, aber soll nur den richtigen Weg ausdrucken!

    Kann mir mal jemand helfen?
    ich komme einfach nicht weiter!

    gruß

  • Diesen links/rechts Vergleich machst du einzig und allein beim Element mit dem Ausgang.
    Den gibst du dann auf höchste Ebene weiter und du gehst immer links.

    Auch das schrittweise erhöhen von node_no ist eigentlich falsch. An dieser Stelle musst du nach links oder rechts gehen. Also rnode oder lnode einsetzen.

    Quellcode

    1. int SearchExit (node_t *T, int node_no) {
    2. if(T[node_no].lnode == -2 || T[node_no].rnode == -2) {
    3. //Es gibt eine Lösung
    4. return 1;
    5. } else if(T[node_no].rnode > -1 && SearchExit(T, T[node_no].rnode) == 1){
    6. printf("(%d) rechts gehts weiter zu: %d\n", node_no, T[node_no].rnode);
    7. return 1;
    8. } else if(T[node_no].lnode > -1 && SearchExit(T,T[node_no].lnode) == 1) {
    9. printf("(%d) links gehts weiter zu: %d\n", node_no, T[node_no].lnode);
    10. return 1;
    11. }
    13. return 0;
    14. }
    Alles anzeigen


    Die Ausgabe musst du dir halt umgedreht denken ;-)
    (0) links gehts weiter zu: 1
    (1) rechts gehts weiter zu: 4
    (4) links gehts weiter zu: 8
    (8) links gehts weiter zu: 13
    (13) rechts gehts weiter zu: 16
    Ausgang gefunden!


    Bleibt offen, ob du alle Ausgänge mit allen Wegen willst?

  • okay, so geht den linken bzw. rechten Knoten im nächsten Element weiter.

    Aber nun habe ich eine Frage:

    Quellcode

    1. else if(T[node_no].rnode > -1 && SearchExit(T, T[node_no].rnode) == 1){


    Die erste Überpfüung verstehe ich. Dann kommt ja der nächste rekursive Aufruf. Ich muss doch eigentlich angeben, dass das Array, hier T, ein Element weiter geht.

    Also müsste es doch eigentlich node_no+1 sein,oder? Ich verstehe das nicht, denn die Funktion wird anfangs mit node_no=0 aufgerufen und während des ersten Aufrufs wird node_no ja gar nicht erhöht, wieso dann beim nächsten rekursiven Aufruf???

    Also diese Zeile SearchExit(T, T[node_no].rnode) macht mir Probleme.

  • Auch wenn dein Code rekursiv verschachtelt ist. Eigentlich hast du nur eine for-Schleife die alle Knoten prüft ob sie im Endzustand sind. Das hätte auch mit einer for-Schleife funktioniert. Du hast eben eine Zählervariable als Index des Arrays.
    Hat Knoten0 ein Ende, hat Knoten 1 ein Ende, hat Knoten 2 ein Ende, hat Knoten 3 ein Ende....


    Mein Script arbeitet aber anders. Ich prüfe nicht schrittweise jeden Knoten im Baum sondern navigiert eben nach links und rechts und prüft ob man über einen anderen Knoten ins Ziel kommt. Ich habe also die Werte links/rechts als Index des Arrays.

    * Wir sind in Knoten 0 und haben die Wahl zu Knoten1 oder 2 zu gehen
    * Komme ich über Knoten1 zum Ziel?
    ** Wir sind im Knoten 1 und haben die Wahl zwischen Knoten 3 und 4
    *** Komme ich über Knoten 3 zum Ziel?
    **** Wir sind im Knoten 3 und haben die Wahl....
    *** Komme ich über Knoten 4 zum Ziel?
    * Komme ich über Knoten2 zum Ziel?
    ** Wir sind im Knoten 2 und haben die Wahl zwischen Knoten 5 und 6
    *** Komme ich über Knoten 5 zum Ziel?
    **** Wir sind im Knoten 5 und haben die Wahl....
    *** Komme ich über Knoten 6 zum Ziel?

  • ja, das verstehe ich ja!

    Ich meine, wie kann es denn sein, dass die Funtkion immer ein Element weiter im Array geht!

    Habe ich das so zu verstehen?

    Also beim ersten Aufruf von SearchExit wird sie mit dem ganzen Baum also ab {1, 2} aufgerufen und das erste Element was geprüft wird, ist {1, 2}!

    Dann wird doch mit diesem Aufruf "SearchExit(T, T[node_no].rnode)" der ganze Baum nochmals übergeben, also wieder von {1, 2} beginnend, und die rechte Seite des 1. Elements {1, 2} überprüft, oder?!

    Also wie geht er denn auf das zweite element ({3, 4}) über? node_no bleibt ja immer 0 (null).


    ODER

    Erster Aufruf von SearchExit mit dem ganzen Baum von {1, 2} und ab da wird der Baum nochmals aufgerufen???? also dass dann das erste element, weil node_no ja immer noch 0 ist, {3, 4} ist???

    Wenn das so sein sollte? habe ich immer noch ein problem! T ist ein Zeiger auf die Struktur und der Baum wird ja dadurch nicht reduziert, sondern wird immer ganz von Anfang an von {1, 2} übergeben! Also müsste er eigentlich immer nur das erste Element {1, 2} überprüfen!!

    oh man, ich hasse rekursion... :(

  • Ja, es wird immer der ganze Baum übergeben. Aber es werden eben nicht immer 1 und 2 überprüft.

    quote]Also wie geht er denn auf das zweite element ({3, 4}) über? node_no bleibt ja immer 0 (null). [/quote]
    Er geht nicht auf das zweite Array Element sondern auf das nächste Element.
    node_no bleibt nicht null, sondern wird in diesem Fall 3 (links) bzw. 4 (rechts)

    Das nach links/rechts gehen würde ich normalerweise auch in einer rekursiven Struktur mit Zeigern machen:

    Quellcode

    1. typedef struct _node{
    2. int *content;
    3. struct _node *prev;
    4. struct _node *next;
    5. } node;


    Aber wenn du mit Indizes arbeitest, kannst du den Baum nicht jedesmal minimieren.

  • ah, ich glaube, jetzt habe ich es :lol:

    Ich habe mal den Aufrufbaum zu diesem Code gezeichnet, damit ich es verstehe ;). Kannst du mal überprüfen, ob das hinkommt?

    Quellcode

    1. int SearchExit (node_t *T, int node_no)
    2. {
    3. static int x=1;
    4. if(T[node_no].lnode==-2 || T[node_no].rnode==-2)
    5. {
    6. printf("%d. Knoten: %2d\n",x++, node_no);
    8. return 1;
    9. }
    11. // linker weg
    12. else if(T[node_no].lnode>-1 && SearchExit(T,T[node_no].lnode)==1) {
    13. printf("%d. Knoten: %2d\n",x++, node_no);
    15. return 1;
    16. }
    17. // rechter weg
    18. else if(T[node_no].rnode>-1 && SearchExit(T, T[node_no].rnode)==1){
    19. printf("%d. Knoten: %2d\n",x++, node_no);
    21. return 1;
    22. }
    23. return 0;
    25. }
    Alles anzeigen



    [Blockierte Grafik: http://bildupload.sro.at/a/images/1-wegsuche.JPG]

    und nach dem Aufruf mit -2 geht es eben in die erste if-Bedingung!
    RICHTIG,ne?!?! :D

    nachtrag: ich habe die rechte hälfte, also letzte if-bedingung vergessen (//rechter weg). Diese wird ausgeführt, wenn schließlich SE[T,1] vom Stack fliegt. Die wird natürlich auch noch einmal durchgegangen, wenn ich mich nicht irre!