Finden aller Lösungen

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

  • Finden aller Lösungen

    hallo leute,


    habe da ein Problem. und zwar habe ich ein Labyrinth mit scheme erstellt. Dieses Labyrinth ist nach der Tiefensuche im Backtrackingverfahren aufgebaut. Jetzt wollte ich das Labyrinth so umformen, dass es alle wege anzeigt. könntet ihr mir in diesem Punkt weiterhelfen. Ich weiss, dass ich dazu einen akku benötige. wo jedoch sollte dieser angebracht werden? werde das programm am 12.12. so gegen 8:00 uhr reinstellen. hoffe, dass ihr mir dabei helfen könnt.


    vielen dank im voraus.

    gruß

  • ; Man startet vom Punkt 0 und versucht im Irrgarten auf den Zielpunkt 25 zu gelangen.

    ;Zum Starten gebe ein : (suche "Start" "Ziel" laby)


    ---------------------------------------------------------
    (define laby '((1) (0 2 6) (1 7) (4 8)
    (3 9) (10) (1 11)
    (2 8 12) (3 7 13) (4)
    (5 15) (6) (7 13) (8 12 14)
    (13 19) (10 20) (17 21) (16 18 22)
    (17 19 23) (14 18 24) (15) (16 25) (17)
    (18)(19) (21) ))


    (define (Fortsetzungen Pfad Irrgarten)

    (list-ref Irrgarten (car Pfad)))

    (define (suche Start Ziel Irrgarten)

    (define (suche Pfad)
    (cond ((eq? Ziel (car Pfad)) (reverse Pfad))
    ((memq (car Pfad) (cdr Pfad)) #F)
    (else (teste Pfad (Fortsetzungen Pfad Irrgarten)))))

    (define (teste Pfad Forts)
    (cond ((null? Forts) #F)
    ((suche (cons (car Forts) Pfad)))
    (else (teste Pfad (cdr Forts)))))

    (suche (list Start)))


    -------------------------------------------


    das Labyrinth sieht wie folgt aus:
    Im prinzip gibt es hier zwei Wege zum Ziel zu gelangen (von 0 zu 25).


    [Blockierte Grafik: http://www.bilder-space.de/thumb/4IAN1kcTkA6QIid.JPG]

  • mein vorschlag wäre wie folgt, aber das ist leider nicht richtig.

    ich wäre euch sehr dankbar, wenn ihr mir bei meinem Problem helfen könntet.


    (define laby '((1) (0 2 6) (1 7) (4 8)
    (3 9) (10) (1 11)
    (2 8 12) (3 7 13) (4)
    (5 15) (6) (7 13) (8 12 14)
    (13 19) (10 20) (17 21) (16 18 22)
    (17 19 23) (14 18 24) (15) (16 25) (17)
    (18)(19) (21) ))


    (define (Fortsetzungen Pfad Irrgarten)

    (list-ref Irrgarten (car Pfad)))

    (define (suche Start Ziel Irrgarten akku)

    (define (suche Pfad akku)
    (cond ((eq? Ziel (car Pfad)) (reverse Pfad akku))
    ((memq (car Pfad) (cdr Pfad)) #F )
    (else (teste Pfad (Fortsetzungen Pfad Irrgarten) akku))))
    (suche (list Start) akku))



    (define (teste Pfad Forts)
    (cond ((null? Forts)
    akku)
    ((suche (cons (car Forts) Pfad)))
    (else (teste Pfad (cdr Forts akku)))))

  • Hallo,

    kannst du bitte mal erklären, wie laby aufgebaut ist? Tiefensuche heißt eigentlich, daß jeder Knoten nur einmal auftaucht. Und auch ein Backtracking-Verfahren kann ich in der Definition irgendwie nicht erkennen. Ist laby fest vorgegeben, oder besteht die Möglichkeit, sich die Grafik gleich etwas anders als Datenstruktur abzuspeichern?

    Und bitte benutze beim nächsten Code-Posting den Code-Button oben, da sind nämlich Smileys im Text. :)


    Viele Grüße,

    Siracusa

  • also "laby" wird bei dem Aufruf berücksichtigt: ;Zum Starten gebe ein : (suche "Start" "Ziel" laby). Und desweiteren wird laby mit den Punkten definiert. Entschuldige, das hätte ich erwähnen müssen. es ist so wie du sagst, es taucht jeder Knoten nur einmal auf. Die Hilfsfunktion "eq?" (unten grün makiert) dient hierbei uir Feststellung, ob ein Sucherfolg eingetreten ist.


    ----------------------


    [code:1]
    (define laby '((1) (0 2 6) (1 7) (4 8)
    (3 9) (10) (1 11)
    (2 8 12) (3 7 13) (4)
    (5 15) (6) (7 13) (8 12 14)
    (13 19) (10 20) (17 21) (16 18 22)
    (17 19 23) (14 18 24) (15) (16 25) (17)
    (18)(19) (21) ))



    (define (Fortsetzungen Pfad Irrgarten)

    (list-ref Irrgarten (car Pfad)))

    (define (suche Start Ziel Irrgarten)

    (define (suche Pfad)
    (cond ((eq? Ziel (car Pfad)) (reverse Pfad))
    ((memq (car Pfad) (cdr Pfad)) #F)
    (else (teste Pfad (Fortsetzungen Pfad Irrgarten)))))


    ;Hilfsfunktionen:
    ; eq? Ziel: pr?ft, ob der Sucherfolg eingetreten ist.
    ; Wenn ja: Erstellung/Aufbereitung des Suchergebnisses
    ; Wenn nein: #F


    (define (teste Pfad Forts)
    (cond ((null? Forts) #F)
    ((suche (cons (car Forts) Pfad )))
    (else (teste Pfad (cdr Forts)))))

    (suche (list Start )))
    [/code:1][/code]

  • Ahhh, jetzt ist der Groschen gefallen! Man beachte die Implementierung von 'Fortsetzungen' und werfe gleichzeitig einen Blick auf die Grafik, dann ergibt die Definition des Labyrinths einen Sinn. :)

    [code:1](define laby '((1) ; <-- alle von Knoten 0 erreichbaren Knoten
    (0 2 6) ; von Knoten 1
    (1 7) ; von Knoten 2
    (4 8) ; etc. etc.
    (3 9) (10) (1 11) (2 8 12) (3 7 13) (4) (5 15) (6) (7 13)
    (8 12 14) (13 19) (10 20) (17 21) (16 18 22) (17 19 23)
    (14 18 24) (15) (16 25) (17)(18)(19) (21) ))[/code:1]
    Das war eine verwirrende Angabe am Anfang, denn die Tiefensuche mit Backtracking bezieht sich nicht auf den Aufbau des Labyrinthes, sondern auf das Finden eines Weges im Labyrinth.

    Dann zu deinem Ansatz: Das äußere suche braucht keinen akku als Eingabe zu erhalten, nur das innere (akku ist beim Start dann die leere Liste). Und beim inneren suche beim eq? sollte man nicht den Pfad zurückgeben, sondern auf den akku packen und weitertesten. Und dann muß teste auch akku als Argument haben, weil das den akku als Rückgabewert bei null? zurückgibt. Und irgendwo im teste (vermutlich beim Aufruf von suche) müßten alle Suchergebnisse mit den Ergebnissen vom rekursiven Aufruf von teste verbunden werden. Die ganze Suchfunktion liefert dann nicht mehr einen Pfad, sondern eine Liste von Pfaden. Irgendwie so müßte es funktionieren. :D


    Viele Grüße,

    Siracusa

  • habe deine vorschläge darauf übertragen. demnach müsste es so aussehen, oder??

    @ siracusa, wäre es vielleicht möglich über msn oder ähnlichem kontakt mit dir aufzunehmen. wäre super.

    vielen dank nochmal!!! :)

    [code:1]
    (define (Fortsetzungen Pfad Irrgarten)

    (list-ref Irrgarten (car Pfad)))

    (define (suche Start Ziel Irrgarten)

    (define (suche Pfad akku)
    (cond ((eq? Ziel (car Pfad)) akku))
    ((memq (car Pfad) (cdr Pfad)) #F)
    (else (teste Pfad (Fortsetzungen Pfad Irrgarten) akku))))

    (suche (list Start akku)))


    (define (teste Pfad Forts)
    (cond ((null? Forts) akku)
    ((suche (cons (car Forts))))
    (else (teste Pfad (cdr Forts) akku))))
    [/code:1]

  • Naja, eher so (ungetestet):

    [code:1](define (Fortsetzungen Pfad Irrgarten)

    (list-ref Irrgarten (car Pfad)))

    (define (suche Start Ziel Irrgarten)

    (define (suche Pfad akku)
    (cond ((eq? Ziel (car Pfad)) (concatenate (list akku) (teste Pfad (Fortsetzungen Pfad Irrgarten) akku))))
    ((memq (car Pfad) (cdr Pfad)) #F)
    (else (teste Pfad (Fortsetzungen Pfad Irrgarten) akku))))

    (define (teste Pfad Forts akku)
    (let ((ret (suche (cons (car Forts)) akku)))
    (cond ((null? Forts) akku)
    (ret (concatenate ret (teste Pfad (cdr Forts) akku)))
    (else (teste Pfad (cdr Forts) akku))))
    (suche (list Start) ())))
    [/code:1]
    Mußt mal testen und Fehler beseitigen, aber die grobe Richtung sollte stimmen.

  • erstmal Vielen Dank, dass du dir die Mühe gemacht hast!!!!
    :)
    nun habe ich ein kleines Problem mit einer Fehlermeldung, mit der ich nicht weiterkomme. es wird folgendes gezeigt. schon bevor ich etwas eingeben kann.

    p.s.: als Suche muss ich dann auf grund des Akkus eine leere Liste hinzufügen also: "(suche "startpunkt" Zielpunkt" laby '()) Stimmt doch, oder?

    nochmal danke!!!!



    begin (possibly implicit): no expression after a sequence of internal definitions in:
    (define (suche Pfad akku)
    (cond ((eq? Ziel (car Pfad)) (concatenate (list akku) (teste Pfad (Fortsetzungen Pfad Irrgarten) akku))))
    ((memq (car Pfad) (cdr Pfad)) #F)
    (else (teste Pfad (Fortsetzungen Pfad Irrgarten) akku))))


    edit:
    p.s. habe da noch in der inneren funktion vor der letzten klammer (suche Pfad'()) hinzufügt, damit die äißere durch die innere aufgerufen wird. Aber bei der Suche "(suche "startpunkt" Zielpunkt" laby '()), kommt nur eine leere Liste.