Sortierfunktion -> Blocks World <- Rekursiv..

P

Powlell

0
Wir haben in unseren Kurs folgendes Problem zu lösen :

Implementieren Sie ein Planungssystem für einen Roboter, der Blöcke gleicher
Größe von einer Startkonstellation in eine Zielkonstellation bewegt.
Die Blocks World besteht aus einer endlichen Menge von (unterscheidbaren)
Plätzen P = {p1, . . . , pn}und einer endlichen Menge von (unterscheidbaren)
Blöcken B = {b1, . . . , bm}.

blwo.jpg


Der Roboter kann immer nur den obersten Block auf einem Platz nehmen
und auf einen anderen Platz, d. h. auf den obersten Block dieses anderen
Platzes ablegen. Diese Aktion heißt ein gültiger Zug.
Zu berechnen ist eine Folge von Zügen, die die Startkonstellation in die
Zielkonstellation überführt.

===
Wir haben die Eingabe und Ausgabe Funktionen fertig geschrieben.. Die Start- oder Zielkonstellation wird in einen 2d vector gespeichert...

Uns fehlt momentan der Ansatz für eine rekursive Sortierfunktion.. Vielleicht kann uns jemand weiter helfen...



.
 
also ganz spontan würde ich dir raten, dir mal die "türme von hanoi" anzusehen. das ist fast genau dein problem. du musst es nur so abwandeln, dass du am ende nicht die blöcke von einem stapel auf einen anderen gemacht hast, sondern dass die blöcke auf einem stapel gleiche gewichte haben. die änderung sollte aber nicht so umfangreich sein
 
Ich würd so ran gehen:
Vergleiche obenliegende Ausgangsblöcke mit Blöcken, die nach unten bzw. auf die letzte verfügbare Ebene gehören, dann dementsprechend bewegen.

Das wären in dem Beispiel dann:
3; 2
4
1
5
6
 
Das Problem mit den Hanoi Türmen haben wir uns angeschaut. Jedoch ist bei uns das Problem, dass nicht nur 3 Plätze zur verfügung stehen sondern min. 3 aber auch beliebig viele... z.B 10 Plätze...

Eine iterative Lösung haben wir uns schon überlegt, jedoch würde unser Prof. gerne eine rekursive sehen
 
rekursiv? ok, dann ebend eine andere idee. (laufzeit ist hier aber nicht grad berauschend!)

1. du fängst z.b. links an.
2. nimm dir den obersten block an
3. gucke, ob du dessen gewicht bereits weiter links auf einem stapel hast
3a. wenn ja, bewege den block dort hin (für die rekursion wichtig, ansonsten im ersten schritt natürlich egal).
3b. kein passender stapel gefunden:
3b1 block war der einzige auf dem stapel: liegen lassen und rekursiv den nächsten stapel aufrufen.
3b2 es gibt noch mehr blöcke: lege block einen stapel weiter nach rechts

schritt 2 und 3 führst du iterativ aus, bis alle blöcke weg sind oder du den letzten block stehen lassen konntest.

rekursion läuft über die stapel.

achtung, der algo ist noch nicht ganz korrekt! problem ist z.b. der letzte stapel. musst du dort nämlich umsortieren, kannst du die einzelnen blöcke nicht weiter nach rechts verschieben. da musst du dir also noch etwas überlegen.

ich denke mal, diese idee könnte man gut erweitern, so dass eure aufgabenstellung erfüllt wird. aber wie gesagt, die laufzeit ist nicht gerade berauschend
 
erstmal danke für deine Hilfe...

was meinst du mit Gewicht?

Auf jeden Platz können beliebig viele Blöcke gestapelt werden.
Ich kann z.B alle Blöcke auf Platz 1 packen.. (Sinnlos aber möglich)
 
gewicht = größe ;) sorry, hatte das beim schreiben falsch im hinterkopf, da ich zur zeit in der uni mit algorithmen, die gewichte haben, gequält werde. letztendlich ist das aber egal, da ich dir ja eh nur pseudocode gegeben habe, den du eh noch verfeinern musst. sollte nur so ungefähr eine grundidee geben, auf der du aufbauen könntest, wenn du magst und dir keine bessere einfällt
 
Um antworten zu können musst du eingeloggt sein.
Zurück
Oben