Labyrinth mit der Breitensuche lösen

Hallo zusammen,

wir haben im Studium eine Aufgabe gestellt bekommen, an der ich gerade etwas verzweifle und ich hoffe ihr könnt mir diesbezüglich helfen.

Gegeben ist ein Labyrinth, das automatisch mit einer Breitensuche gelöst werden soll.

Der "Spielstein" wird in der Mitte platziert und von dort aus soll dann die Breitensuche beginnen. Das Spielfeld ist durch # begrenzt und auf dem Weg liegen ° die eingesammelt werden müssen. Das Spiel ist beendet, wenn alle ° eingesammelt sind.

Die Position des Spielsteins trage ich in eine Queue ein und durchlaufe danach eine while Schleife so lange, bis sie leer ist. In der Schleife wird immer das erste Koordinaten Paar aus der Queue gelöscht und in eine Hash Tabelle übertragen.

Zum Schluss habe ich dann eine Hash Tabelle, in der jedes Koordinaten Paar nur einmal vorkommt.

public void bSearch(int iAmount)
        {
            int[] result = new int[iAmount];
            Queue qList = new Queue(iAmount);

            Hashtable htList = new Hashtable();

            string sKoordinatenStart = ixC.ToString() + "," + iyC.ToString();
            string sKoordinatenInList = "";

            qList.Enqueue(sKoordinatenStart);
        
            while (qList.Count != 0)
            {
                // holt das erste Koordinatenpaar aus der Queue
                sKoordinatenInList = qList.Dequeue().ToString();
                
                string[] sarrKoordinaten = sKoordinatenInList.Split(',');                

                ixC = Convert.ToInt16(sarrKoordinaten[0]);
                iyC = Convert.ToInt16(sarrKoordinaten[1]);

                if (!(iarrFieldMirror[ixC, iyC - 1] == 1))
                {
                    iyC--;
                    if (!htList.ContainsKey(ixC.ToString() + "," + iyC.ToString()) && 
sKoordinatenStart != (ixC.ToString() + "," + iyC.ToString()))
                    {
                        qList.Enqueue(ixC.ToString() + "," + iyC.ToString());
                        htList.Add((object)ixC.ToString() + "," + iyC.ToString(), (object)sKoordinatenInList);
                        iyC++;
                        continue;
                    }
                    iyC++;
                }
                if (!(iarrFieldMirror[ixC, iyC + 1] == 1))
                {
                    iyC++;
                    if (!htList.ContainsKey(ixC.ToString() + "," + iyC.ToString()) && 
sKoordinatenStart != (ixC.ToString() + "," + iyC.ToString()))
                    {
                        qList.Enqueue(ixC.ToString() + "," + iyC.ToString());
                        htList.Add((object)ixC.ToString() + "," + iyC.ToString(), (object)sKoordinatenInList);

                        iyC--;
                        continue;
                    }
                    iyC--;
                }
                if (!(iarrFieldMirror[ixC - 1, iyC] == 1))
                {
                    ixC--;
                    if (!htList.ContainsKey(ixC.ToString() + "," + iyC.ToString()) &&
sKoordinatenStart != (ixC.ToString() + "," + iyC.ToString()))
                    {
                        qList.Enqueue(ixC.ToString() + "," + iyC.ToString());
                        htList.Add((object)ixC.ToString() + "," + iyC.ToString(), (object)sKoordinatenInList);

                        ixC++;
                        continue;
                    }
                    ixC++;
                }
                if (!(iarrFieldMirror[ixC + 1, iyC] == 1))
                {
                    ixC++;
                    if (!htList.ContainsKey(ixC.ToString() + "," + iyC.ToString()) && 
sKoordinatenStart != (ixC.ToString() + "," + iyC.ToString()))
                    {
                        qList.Enqueue(ixC.ToString() + "," + iyC.ToString());
                        htList.Add((object)ixC.ToString() + "," + iyC.ToString(), (object)sKoordinatenInList);
                        ixC--;
                        continue;
                    }
                    ixC--;
                }
            }

            Stack myStack = new Stack(htList.Count);

            // Stack füllen
            //for (int i = 0; i < htList.Count; i++)
            //  myStack.Push(htList[i]);

            foreach (string sValue in htList.Values)
            {
                myStack.Push(sValue);
            }
            PrintStack(myStack);


            //for (int i = 0; i < arrlKeys.Count; i++)
            //{
            //    if (sGetValue.Equals(String.Empty) || htList.ContainsKey(arrlKeys[i]))
            //    {
            //        sGetValue = htList[arrlKeys[i]].ToString();
            //    }
            //}
        }

So und jetzt kommt das Problem.
Wie kann ich jetzt das Labyrinth lösen?
In der Aufgabenstellung ist davon die Rede, dass man an diesem Punkt einfach Rückwärts durch die Hash Tabelle zurück zum Ausgangspunkt müsse und hätte somit den optimalen Weg gefunden, was ich jedoch nicht nachvollziehen kann, denn sobald ich an eine Stelle komme, an der ich schon mal durchgelaufen bin, bleibt das Spiel hängen.

Ich hoffe ich konnte mich einigermassen verständlich ausdrücken.

Danke und viele Grüsse

Hallo,

vllt hilft dir ja der Beitrag und dessen Antwort weiter

Das Programmier-Spiel: nette Übungsaufgaben für zwischendurch

Hallo gizzmo25,

Pacman lässt grüßen. 😃

Dadurch, dass nicht nur ein Weg von A nach B gesucht wird, sondern alle Futterstücke "gegessen" werden müssen, ist das nicht so ganz der Fall einer klassischen Breitensuche. Denn wenn es zwei verschiedene Wege gibt vom Start zu einem Punkt X gibt, reicht es nicht von Punkt X aus gemeinsam weiterzusuchen, sondern man muss für jeden Weg, der zu X führt separat weitersuchen (zumindest wenn die Menge der auf beiden Wegen gefressenen Futterstücke sich unterscheidet).

Daher würde ich den Ansatz, dass in der Hashtable (besser: Dictionary<>) jedes Koordinatenpaar nur einmal vorkommt, in Zweifel ziehen.

herbivore

Hallo ProGamer,

hm... vielen Dank jetzt hab ich dort etwas gesehen, was mir evtl. für später hilft, jedoch das Problem, das ich habe beschreibt er schön im letzten Satz.

Wenn es zwei Wege gibt, werden zwar beide eingezeichnet, die Länge wird allerdings nur von einem zurückgegeben.

Hallo herbivore,

vielen Dank für deine Antwort.
Der Meinung bin ich eben auch und daher meine Zweifel.

Leider wird das in der Aufgabenstellung aber explizit verlangt.

Ich hab mal versucht das Spiel in einen Baum zu übertragen, um es mir besser vorstellen zu können. (Aufgrund des Umfangs habe ich es nicht komplett aufgezeichnet).

Wenn eine Koordinate ein zweites mal auftritt, ist der Ast zu ende.

dort sieht man finde ich auch schön, dass es mit der Breitensuche meiner Meinung nach nicht so wirklich funktionieren kann.

Sehe ich das richtig?

viele Grüsse
Marco

Witzig, das ist meine Aufgabe, die es ins Internet geschafft hat.

Gut, ich kann beruhigt sein, die "Lösung" von oben ist höchstens ein Beispiel wie man es nicht machen sollte (allein die Strings und Stringarrays ??? Was zum Geier?)
Das einzig gute an der Lösung ist, dass sie in allen vier Richtungen irgendwas macht, immerhin.
Die Visualisierung ist gelungen, das kann ich auch noch positiv vermerken.

Ich glaube, Gizmo wie auch viele andere, die diese Aufgabe problematisch fanden, haben eine Sache nicht verstanden:

Auf dem Blatt steht ein wichtiger Satz wie:

"Fall ein Item gefunden wurde ist die Breitensuche fertig und bricht ab"

und den überlesen entweder viele, oder sie ignorieren ihn oder sie gehen mit völlig falschen Annahmen an die Sache ran. Oder ich habe die Aufgabe mistig formuliert, ist auch möglich (falls dann jemand einen Hinweis hat, wie es besser geht, nur zu !).
Die Schleife von oben bricht zumindest nicht ab sobald ein Item gefunden wird.

Man soll das Labyrinth nämlich schrittweise abarbeiten, d.h. ich suche das erste Item, laufe da hin.
Von dort aus suche ich das nächste item, laufe da hin. Dann suche ich das übernächste und laufe da hin. Usw., bis das Labyrinth irgendwann leer gefressen ist.

Die falsche Annahme, von der einige hier ausgingen, auch gizzmo vermutlich, ist dass man das Labyrinth auf einmal in einem Schritt mit einer einzigen Suche, einem Baum whatever leersuchen muss. Das geht natürlich nicht! Wer's trotzdem so lösen konnte, und das Labyrinth wurde fix geleert, kein Feld doppelt betreten oder so, Glückwunsch, vermutlich haben Sie gerade das Traveling Salesman Problem in polynomialer Zeit gelöst! (ist Quatsch, das wird nicht gelingen)

Insofern ist auch der Satz

Denn wenn es zwei verschiedene Wege gibt vom Start zu einem Punkt X gibt, reicht es nicht von Punkt X aus gemeinsam weiterzusuchen, sondern man muss für jeden Weg, der zu X führt separat weitersuchen (zumindest wenn die Menge der auf beiden Wegen gefressenen Futterstücke sich unterscheidet).

irreführend. Darum geht's hier doch gar nicht (stand auch übrigens mit keinem Wort auf dem Blatt)

Schrittweise ist's aber überhaupt kein Problem: solange noch mind. ein Item im Labyrinth liegt, findet die Breitensuche das Item. Sie findet zudem immer das nächste Item zum Player (was natürlich je nach Situation mehrere sein könnten, dann wird aber einfach das erste in der Queue genommen, bzw. die Suche bricht ja schon ab, sobald auch nur E I N Item gefunden wurde).

Ansonsten, die Aufgabe mit einer Queue, einer Hashtable und einem Stack zu lösen war ein Vorschlag, wie es einigermaßen Brainless geht. Kann man auch variieren, z.B. statt der Hashtable Pointer verwenden.

Und noch was: ab jetzt werde ich höllisch aufpassen was hier passiert und wenn ich eine Lösung der Aufgabe bekomme, die aus dem Internet stammt, ist sie ungültig.

• thomas