Problem mit der Wegfindung..

[Lord Tombery]

Hi guys
Ich habe folgendes Problem:

Eingabeformat:
Die erste Zeile der Eingabe gibt die Breite b und Höhe h des des Feldes an. Keine der beiden Dimensionen wird 25 übertreffen.

Die nächsten h Zeilen enthalten je b Zeichen. Der Buchstabe X für undurchdringbar, während der Buchstabe S für den Ort, an dem man sich befindet, und der Buchstabe D das Ziel markiert. Die Wege sind mit einer Zahl von 1 bis 9 gekennzeichnet. Diese Zahl steht dabei für die Anzahl Sekunden, die man, um das "Feld" zu durchqueren.


Ausgabeformat

Das Programm soll die Anzahl Sekunden ausgeben, die auf dem kürzesten Weg benötigt werden, um ans Ziel zu gelangen. Diagonales Fortbewegen ist nicht möglich, man kannst nur nach links, rechts, oben oder unten schreiten. Der Grundriss kann nicht verlassen werden. Das Programm kann davon ausgehen, dass es immer einen Weg gibt, das Ziel zu erreichen.



Beispieleingabe

5 5
S5213
2X2X5
51248
4X4X2
1445D



Beispielausgabe

23


Ziemlich knifflige Aufgabe...
Wäre froh für gute Ideen

(Diese Aufgabe ist von SOI)

[SmokingFish]

moin

das könnte dir weiterhelfen :

http://www.irf.uni-dortmund.de/semin...tte/stdt_1.htm

http://n.ethz.ch/student/stammt/doc/.../Dijkstra.html

mit dem algo, ein wenig modifiziert sollte das ohne probleme zu machen sein. die aufgabe an sich ist sehr interessant , vor kurzem hatte ich mit einem ähnlichen problem zu kämpfen , da hat das geholfen =)

mfg

[Ineluki]

die einfachste, wenn wohl auch langsamste Methode waere wohl das ganze rekursiv zu loesen ...

du machst eine funktion, die auf ihrer lokalen kopie der karte vermerkt, wo du schon gewesen bist und die sich selbst immer wieder aufruft, und zwar mit allen Feldern, die die aktuelle position umgeben, die nicht X sind und an denen man noch nicht war. dabei speicherst du immer den aktuellen pfad.
Geht es nicht mehr weiter, d.h. du steckst in einer Sackgasse, so beendet sich die funktion und gehrt somit automatisch zu ihrem vorgaengeraufruf zurueck. Findet dagegen die Funktion das Ziel, dann wird der genommene Pfad global in einer Liste abgespeichert und die funktion beendet sich ebenfalls.

Dadurch erhaellst du eine Liste aller wege, die zum Ziehl fuehren, ohne dass dabei ein Feld doppelt betreten wird.

Nun brauchst du nur noch alle gefundenen wege durchgehen und darueber jeweils aufsummieren, um den richtigen weg zu finden

wenn du willst, koennte ich dir so eine funktion mal etwas genauer in delphi oder c++ ausformulieren, oder reicht dir das so ?

Gruss Ineluki

[Lord Tombery]

Danke euch beiden für die raschen antworten!!!
Die Idee von Ineluki ist Genial ...
Ich habe es gestern gleich ausprobiert. Das hat aber nicht so ganz geklappt. Ich habe wohl einige fehler geamcht....

Hey Ineluki wäre super wenn du mir kurz ein Beispiel posten könntest.
bin euch aber schon jetzt mehr als dankbar!!

Thanks!!

[Ineluki]

hm ... ich versuchs nochmal etwas genauer theoretisch abzuhandeln ..

Also als erstes brauchst du eine Struktur, die die Map speichert ...

bestehend aus
MAP :
* Breite der Map : Ganzzahl
* Hoehe der Map : Ganzzahl
* einem Array [breite x hoehe] einer Feldstruktur

die Feldstruktur besteht aus
FELDSTRUKTUR :
* Dauer : Ganzzahl
* Betreten : Wahrheitswert

Im Hauptprogramm wird nun die Map mit den anfangsdaten aus der Vorgabe gefuellt. Dafuer wird in der Eigenschaft Zeitdauer die Anzahl in Sekunden die jedes Feld hat eingestellt. Fuer eine Wand koennte man dort den Wert -1 eintragen (das wird dann als Blockiert gewertet), fuer den Start -2 und fuer das Ziel den Wert 0. Zudem wird eine globale Liste mit Strings initialisiert, die unsere Ergebnisse aufnehmen soll. Danach wird eine Funktion aufgerufen, die die Auswertung rekursiv vornimmt (dazu spaeter).

Die Funktion sollte im Prinzip so aussehen (Pseudocode)

Code:

Function Gehe(Karte: MAP, PosX:Ganzzahl, PosY:Ganzzahl, Zeit:Ganzzahl, Weg:String);

Markiere das Feld [PosX,PosY] in Map als Betreten = Wahr

Wenn Karte[PosX,PosY].Dauer>0 // Damit -2 vom Start ignoriert wird
   Addiere zu Zeit den Wert von Karte[PosX,PosY].Dauer

Wenn Karte[PosX,PosY].Dauer = 0 // das heisst Ziel erreicht
   Fuege (Weg + Leerzeichen + Zeit) der globalen Stringliste hinzu
   Beende diese Funktion
Ansonsten 
 Wenn PosX+1, PosY innerhalb der Map
  UND Karte[PosX+1,PosY].Dauer>=0 // also Ziel oder Passierbar
  UND Karte[PosX+1,PosY].Betreten = Falsch // da war ich noch nie
   Gehe(Karte, PosX+1, PosY, Zeit, Weg+"R") // Nach Rechts Gehen

 Wenn PosX, PosY+1 innerhalb der Map
  UND Karte[PosX,PosY+1].Dauer>=0 
  UND Karte[PosX,PosY+1].Betreten = Falsch 
   Gehe(Karte, PosX, PosY+1, Zeit, Weg+"U") // Nach Unten Gehen

 Wenn PosX-1, PosY innerhalb der Map
  UND Karte[PosX-1,PosY].Dauer>=0 
  UND Karte[PosX-1,PosY].Betreten = Falsch 
   Gehe(Karte, PosX-1, PosY, Zeit, Weg+"L") // Nach Links Gehen

 Wenn PosX, PosY-1 innerhalb der Map
  UND Karte[PosX,PosY-1].Dauer>=0 
  UND Karte[PosX,PosY-1].Betreten = Falsch 
   Gehe(Karte, PosX, PosY-1, Zeit, Weg+"O") // Nach Oben Gehen
Ende von Ansonsten

ENDE

Es ist darauf zu achten, das die Funktion die Parameter nicht veraendern darf. (Also nicht als VAR deklarieren. Wenn mit Dynamischen Arrays ueber Pointer gearbeitet hat, muss man vor der uebergabe jeweils eine eigene Kopie erstellen und nach dem Aufruf freigeben.

Im Hauptprogramm wird dann die Gehe Funktion einmal aufgerufen mit den Parametern (Map, StartPosX, StartPosY, 0, Leerstring)

Das vorgehen ist folgendermassen :
Die Funktion setzt die Startposition als Betreten und geht nach rechts, indem es sich selbst wieder aufruft. Dadurch wird nun das Feld Rechts von Startfeld als betreten markiert, aber da es sich um eine Kopie handelt, nur inerhalb der jetzt aufgerufenen Funktionsinstanz und ihrer Unterinstanzen. Diese ruft nun wieder sich selber auf, indem sie nach rechts geht, solange, bis es nicht mehr nach rechts geht, das ziel gefunden ist, oder kein Feld mehr da. Dann wird nach unten gehen geprueft, danach links und danach oben. Trifft so ein Abbruchkriterium ein, dann beendet sich die Funktion und kehrt zur funktion zurueck, die sie aufgerufen hat, und macht dannn mit dem naechsten Befehl weiter und natuerlich ist es so, das alle veraenderungen an der Map nie stattgefunden haben, da jede Funktionsebene ja ihre eigene Kopie hat, also sind auch felder die als Betreten markiert waren jetzt wieder frei, weil man ja wieder auf die alte kopie zurueckgreift.

Der Aufruf aus dem Hauptprogramm endet erst, wenn alle moeglichen Wege durchgegangen sind, was durchaus sehr lange dauern kann.

Danach hat man alle moeglichen Wege in der Stringliste gespeichert und zwar als eine Art Befehlsmuster (der Art "RULLO 23" = Gehe nach Rechts, Unten, Links, Links, Oben, dauert 23 Sekunden) was reproduzierbar ist. Nun muss man nur noch die Stringliste nach dem Wert sortieren, der den kleinsten Zahlenwert nach dem Leerzeichen hat.

Hoffe, das ganze ist jetzt klar, wie es gemeint war. Haette ich ein komplettes Programm geschrieben, waere das wesentliche verlohren gegangen, da z.B. die Speicherverwaltung fuer dynamische Arrays etc den Blickpunkt vom eigentlichen Problem abgelenkt haetten.

Wenn du jedoch Delphi kannst, und ich nochmal Zeit finde, kann ich dir ja mal ein richtiges Beispielprogramm schreiben, hoffe aber, das nicht zu muessen ^^

Gruss Ineluki

EDIT ...

Na ja ... ich war doch so frei, nach obigem Schema ein Programm zu schreiben .... :D

Hier die kompletten Ausgaben zu deinem obigen Problem:

Code:

 Bitte Kartenbreite eingeben : 5
 Bitte Kartenhoehe eingeben : 5

 Bitte jetzt die Karte eingeben.
 Geben Sie ein : Verweilzeit als Ziffer in Sekunden (1..9)
                 S fuer Start
                 # fuer Wand
                 Z fuer Ziel
Beispiel (4x3) :
  S#Z2
  29#6
  #153

 Zeile 1: S5213
 Zeile 2: 2#2#5
 Zeile 3: 51248
 Zeile 4: 4#4#2
 Zeile 5: 1445Z

Starte Berechnung ... 0 Millisekunden
Gefundene Wege : 12
1: RRRRUUUU 26
2: RRRRUULLUURR 43
3: RRRRUULLLLUURRRR 54
4: RRUURRUU 25
5: RRUUUURR 24
6: RRUULLUURRRR 35
7: UURRRRUU 24
8: UURRUURR 23
9: UURROORRUUUU 33
10: UUUURRRR 25
11: UUUURROORRUU 40
12: UUUURROOOORRUUUU 49

Der kuerzesze Weg ist "UURRUURR"  mit einer Dauer von 23 Sekunden.

Zum Beenden bitte ENTER druecken.

und hier der Delphi Quellcode ..
Wichtig: Project unter Neu -> Konsole-Application erstellen
Vielleicht nicht schoen, und auch nicht optimiert, dafuer quick n' dirty

Code:

program Wegfinden;

{$APPTYPE CONSOLE}

uses
  SysUtils, Classes, Windows;

Type PFeld = ^TFeld; //Pointertyp
     TFeld = record  //Felddaten
              dauer:Integer;
              used :Boolean;
             end;

Var breite, hoehe : Integer;
    liste:TStringlist;

Function GetElement(karte:PFeld; x,y:integer):PFeld;     // Zugreifen auf Map wie auf Array
begin
 result:= PFeld(longint(karte)+(x+breite*y)*SizeOf(TFeld)); // aus 1Dim Array mach 2Dim Array
end;

Procedure Gehe(karte:PFeld; PosX, PosY, Zeit: Integer; Weg:String);
var karte2:PFeld;
begin
GetElement(karte,PosX,PosY)^.used:=true;
if GetElement(karte,PosX,PosY)^.dauer > 0 then inc(Zeit, GetElement(karte,PosX,PosY)^.dauer);
if GetElement(karte,PosX,PosY)^.dauer = 0 then liste.Add(Weg+' '+inttostr(Zeit))
else begin
      if (PosX+1>=0) AND (PosX+1<breite) AND
         (GetElement(karte,PosX+1,PosY)^.used = False) AND
         (GetElement(karte,PosX+1,PosY)^.dauer >= 0)
         then begin
               GetMem(karte2,breite*hoehe*SizeOf(TFeld)); // Platz fuer neue Karte machen
               move(karte^,karte2^,breite*hoehe*SizeOf(TFeld)); // Karte kopieren
               Gehe(karte2,PosX+1,PosY,Zeit,Weg+'R');
               FreeMem(Karte2); // Platz wieder freigeben
              end;

      if (PosY+1>=0) AND (PosY+1<hoehe) AND
         (GetElement(karte,PosX,PosY+1)^.used = False) AND
         (GetElement(karte,PosX,PosY+1)^.dauer >= 0)
         then begin
               GetMem(karte2,breite*hoehe*SizeOf(TFeld)); // Platz fuer neue Karte machen
               move(karte^,karte2^,breite*hoehe*SizeOf(TFeld)); // Karte kopieren
               Gehe(karte2,PosX,PosY+1,Zeit,Weg+'U');
               FreeMem(Karte2); // Platz wieder freigeben
              end;

      if (PosX-1>=0) AND (PosX-1<breite) AND
         (GetElement(karte,PosX-1,PosY)^.used = False) AND
         (GetElement(karte,PosX-1,PosY)^.dauer >= 0)
         then begin
               GetMem(karte2,breite*hoehe*SizeOf(TFeld)); // Platz fuer neue Karte machen
               move(karte^,karte2^,breite*hoehe*SizeOf(TFeld)); // Karte kopieren
               Gehe(karte2,PosX-1,PosY,Zeit,Weg+'L');
               FreeMem(Karte2); // Platz wieder freigeben
              end;

      if (PosY-1>=0) AND (PosY-1<hoehe) AND
         (GetElement(karte,PosX,PosY-1)^.used = False) AND
         (GetElement(karte,PosX,PosY-1)^.dauer >= 0)
         then begin
               GetMem(karte2,breite*hoehe*SizeOf(TFeld)); // Platz fuer neue Karte machen
               move(karte^,karte2^,breite*hoehe*SizeOf(TFeld)); // Karte kopieren
               Gehe(karte2,PosX,PosY-1,Zeit,Weg+'O');
               FreeMem(Karte2); // Platz wieder freigeben
              end;
     end;
end;

var x,y,dummy,dauer:integer;
    startX,startY:integer;
    temp:String;
    Map: PFeld;
    noziel:Boolean;
    kurz,kurzno:integer;
    time:DWORD;
begin
liste:=TStringlist.create;
Write(' Bitte Kartenbreite eingeben : '); readln(breite);
Write(' Bitte Kartenhoehe eingeben : '); readln(hoehe);
GetMem(Map, breite*hoehe*SizeOf(TFeld));
repeat
 Writeln;
 Writeln(' Bitte jetzt die Karte eingeben. ');
 Writeln(' Geben Sie ein : Verweilzeit als Ziffer in Sekunden (1..9)');
 Writeln('                 S fuer Start');
 Writeln('                 # fuer Wand');
 Writeln('                 Z fuer Ziel');
 Writeln('Beispiel (4x3) :');
 Writeln('  S#Z2');
 Writeln('  29#6');
 Writeln('  #153');
 Writeln;
 startX:=0; startY:=0; noziel:=true;
 // Einlesen der Karte
 for y:=0 to hoehe-1 do
   repeat
    Write(' Zeile ',y+1,': '); readln(temp);
    if length(temp)<>breite then dummy:=1
    else for x:=0 to breite-1 do
          begin
           dummy:=0;
                if upcase(temp[x+1])='S' then begin dauer:=-2; startX:=x; startY:=y; end
           else if upcase(temp[x+1])='Z' then begin dauer:=0; noziel:=false; end
           else if temp[x+1]='#'         then dauer:=-1
           else val(string(temp[x+1]),dauer,dummy);
           if dummy=0 then begin 
                            GetElement(Map,x,y)^.dauer:=dauer;
                            GetElement(Map,x,y)^.used:=false;
                           end;
          end;
    if dummy<>0 then Writeln('Eingabe ungueltig, bitte nochmal eingeben.');
   until dummy=0;
 if noziel then Writeln('Kein Ziel (Z) gefunden. Bitte nochmal die Eingabe wiederholen.');
until not(noziel);
Writeln;
Write('Starte Berechnung ... ');
time:=GetTickCount; // Ermittle Millisekunden seit Windowsstart
Gehe(Map,startX,startY,0,'');
Writeln(GetTickCount-time,' Millisekunden'); // gib Differenz aus
// Auswerten der Ergebnisliste
Writeln('Gefundene Wege : ',liste.count);
kurz:=-1;
if liste.Count=0 then Writeln(' Keine Wege gefunden.') else
 begin
  for y:=0 to liste.count-1 do
    begin
     Writeln(y+1,liste[y]);
     x:=pos(' ',liste[y]);
     val(copy(liste[y],x+1,length(liste[y])-x),dauer,dummy);
     if dummy<>0 then Writeln('Fehler im Listenformat.'); 
      // Darf eigentlich nie Auftreten, aber sicher ist sicher
     if (dauer<kurz)OR(kurz=-1) then begin kurz:=dauer; kurzno:=y; end;
    end;
  Writeln;
  Writeln('Der kuerzesze Weg ist "',
          copy(liste[kurzno],1,pos(' ',liste[kurzno])),
          '" mit einer Dauer von ', kurz,' Sekunden.');
 end;
FreeMem(Map);
liste.free;
Writeln;
Write('Zum Beenden bitte ENTER druecken.');readln;
end.

Ich habs mal fuer eine 10x10 map mit ca 1/4 der Felder als Wand rechnen lassen ... es wurden ueber 15000 Wege gefunden in weniger als 700 ms. 6x6 Unbeschraenkte Felder dauerten ganze 26 Sekunden und hatten ueber 1,3 Millionen gefundene Wege. 7x7 Felder ohne Beschraenkung dauerte dagegen schon ueber 60 Minuten (und ist damit noch nicht mal fertig) und verbrauchte schon mal zwischenzeitlich ueber ein halbes GIGABYTE(!!!) an Ram weil jetzt ja kein vorzeitiger Rekursionsabbruch mehr stattfinden konnte bzw der Worst Case der Rechenzeit eintrat.

[Lord Tombery]

Danke Ineluki für deine Ausfürliche Antwort!
Ich habe mir das Ganze auch noch einmal durch den Kopf gehen lassen..
Der Code funktioniert zwar, braucht aber ein relativ grossen Rechenaufwand .

Mir eine Idee gekommen die den Rechenaufwand erhablich verkürzt:
Man findet für die nächsten Felder den kürzesten Weg. Ausgehend vom gefundenen kürzesten Weg berechnet man wieder den kürzesten Wegen der folgenden Felder usw bis man am Ziel ist.
Das ganze geschieht mit Hilfe einer Rekursiv aufgerugfenen Funktion.
Ein Beispiel:

Sry, musste das Beispiel rausnehmn, irgendwie hat es mir die Abstände verschoben, was das Ganze unleserlich machte.


Der Vorteil dieser Lösung: Ist viel schneller als die andere,
der Nachteil: Man weiss nicht welchen Weg man genommen hat, nur wie lang der kürzeste ist... (was aber für mein Problem reicht.)

Ich hoffe ich habe das nicht zu kompliziert erklärt...


Auf jeden Fall besten Dank an Ineluki!!!!

[Ineluki]

das klappt nur nicht so ganz, oder ich hab was falsch verstanden

Beispiel

S7511
11171
76281
9977Z

Bei deiner Variante wuerde er URRUURR gehen .. der kurzeste weg ist aber URRORRUUU

Das formatieren machst du mit den [Code][*/Code] Tags .. ohne * natuerlich

Gruss Ineluki

[Lord Tombery]

Meine Erklährung ging wohl etwas in die Hose... (schäm)
Das Programm berechnet für jeden Wegpunkt den kürzesten Weg.

In deinem Beispiel:

Code:

S  7  8  9  10
1  2  3  10 11
8  8  5  13 12
17 17 12 19  Z

(edit: habs immer no net gerafft mit den Abständen.....

Also die Länge des kürzesten Weges ist 12. (Wobei es zwei kürzeste Wege gibt.)
Mein Programm findet aber nur die Länge des kürzesten Weges, nicht aber den Weg selbst.

Im Programm selbst habe ich zwei Arrays gebraucht, eines mit den Anfangswerten(die Werte die du geschrieben hast) und ein Zweites mit den meinen berechneten Werten(die Werte von mir).
Dann eine Rekursive Funktion. Welche folgendes tut: Sie geht einen Weg und schreibt die Wegdauer ständig in das Array mit den berechneten Wegen. Sie tut das solange bis sie in eine Saackgase gerät, d.h bis sie Rund um sich nur a)Rand b)Hindernisse c)das Ziel oder d)einen kürzeren Weg hat. Ist das der Fall springt sie einen Aufruf zurück fährt dort mit einem anderen Weg weiter. Trifft es im Array mit den berechneten Werten auf einen längeren Weg, wird dieser einfach mit dem neuen, kürzeren überschrieben.
Am Ende der Funktion hat man sicher für jedes Feld den kürzesten Weg gefunden.
Nun prüft man noch welches das kleinste Feld neben Z ist und man hat die Lösung.

Das Programm hat ein 15*15 gosses Feld in unter einer Sekunde geschafft. Aber wie gesagt es hat auch seine Mängel, denn um zu wissen welchen Weg man den nun wirklich gegangen ist, braucht man weitere Variablen, welche auch wieder Speicher kosten.

Einfach den [.Code][./code] tag verwenden

[cypher256]

Also imho schaut des nach einen fall für den A* algorithmus aus...
ich werde heute (oder morgen, je nachdem wann ich zeit hab) genau posten, wie der geht

gn8, cypher