Lord Tombery
25.03.2004, 02:29
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 http://www.multimediaxis.de/images/smilies/old/sm_12.gif http://www.multimediaxis.de/images/smilies/old/sm_12.gif
(Diese Aufgabe ist von SOI)
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
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 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)
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 [b]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:
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
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
09.04.2004, 20:53
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:
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.....:rolleyes:
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 ;)
Powered by vBulletin® Version 4.2.3 Copyright ©2024 Adduco Digital e.K. und vBulletin Solutions, Inc. Alle Rechte vorbehalten.