Problem mit der Wegfindung..

[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.