| Autor |
Beitrag |
Dim89K
Hält's aus hier
Beiträge: 3
|
Verfasst: So 09.03.08 13:00
Hi! vllt kennt einer oder der andere von euch das elefantenproblem, wenn sich zwei elefanten-familien auf einem schmalen pfad treffen, und es gibt bestimmte regeln, wie die an einander vorbeigehen gehen können. das problem hab ich mit hilfe von Backtracking gelöst, aber ich will die einzelnen schritte in ein Lösungsarray einlesen. das klappt nur bis zur hälfte. er zeichnet mir den weg auf bis zu einer sackgasse, dann springt er auf die richtige lösung und dann ist alles ok. ich weiß nich, wie ich das lösen soll, dass er mir nur den richtigen weg aufzeichnet. hier ist mein algorithmus, vllt hat jemand ne idee, an welcher stelle, und wie ich den weg aufzeichnen soll. Danke im voraus!
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
| procedure suche(pos: integer);
var i,j,speicher2: integer;
speicher: TPfad;
begin
if not(f_ziel(pfad_ar)) then begin
pos:=suche_leer(pfad_ar);
if (pos > 0)and(pfad_ar[pos-1]='>') then begin
for i:=0 to 6 do begin
speicher[i]:=pfad_ar[i];
end;
speicher2:=schritt;
pfad_ar[pos-1]:='_';
pfad_ar[pos]:='>'; loesung[schritt]:=pfad_ar; inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad_ar[i]:=speicher[i];
end;
dec(schritt);
end;
pos:=suche_leer(pfad_ar);
if (pos < 6)and(pfad_ar[pos+1]='<') then begin
for i:=0 to 6 do begin
speicher[i]:=pfad_ar[i];
end;
speicher2:=schritt;
pfad_ar[pos+1]:='_';
pfad_ar[pos]:='<';
loesung[schritt]:=pfad_ar;
inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad_ar[i]:=speicher[i];
end;
dec(schritt);
end;
pos:=suche_leer(pfad_ar);
if (pos > 1)and(pfad_ar[pos-1]='<')and(pfad_ar[pos-2]='>') then begin
for i:=0 to 6 do begin
speicher[i]:=pfad_ar[i];
end;
speicher2:=schritt;
pfad_ar[pos-2]:='_';
pfad_ar[pos]:='>';
loesung[schritt]:=pfad_ar;
inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad_ar[i]:=speicher[i];
end;
dec(schritt);
end;
pos:=suche_leer(pfad_ar);
if (pos < 5)and(pfad_ar[pos+1]='>')and(pfad_ar[pos+2]='<') then begin
for i:=0 to 6 do begin
speicher[i]:=pfad_ar[i];
end;
speicher2:=schritt;
pfad_ar[pos+2]:='_';
pfad_ar[pos]:='<';
loesung[schritt]:=pfad_ar;
inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad_ar[i]:=speicher[i];
end;
dec(schritt);
end;
end else for i:=0 to 6 do Form1.pfad.cells[i,0]:=pfad_ar[i];
end; |
|
|
BenBE
  
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 09.03.08 13:18
1. Wozu übergibst Du pos, wenn Du die dann nicht nutzt? (Oder hab ich da was übersehen)? IMHO wird das nämlich gleich am Anfang überschrieben ...
2. Pos für eine Variable ist ein SEHR ungünstiger Name, da es eine gleichnamige Funktion gibt.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Dim89K 
Hält's aus hier
Beiträge: 3
|
Verfasst: So 09.03.08 13:30
ja, stimmt, ist ein bissl sinnlos, aber ich hatte das ma bei der abbruchbedingung gebrauch... als ich die dann geändert hab, hat ich das dann nicht weiter verändert... hat glaub ich aber keine auswirkungen...
soll ich vllt den Quelltext des ganzen progs einfügen, damit es verständlicher ist???
|
|
BenBE
Beiträge: 8721
Erhaltene Danke: 191
Win95, Win98SE, Win2K, WinXP
D1S, D3S, D4S, D5E, D6E, D7E, D9PE, D10E, D12P, DXEP, L0.9\FPC2.0
|
Verfasst: So 09.03.08 13:47
Die direkt verwendeten Routinen wie suche_leer fehlen noch.
Und ggf. die Regeln, nach denen das geht.
_________________ Anyone who is capable of being elected president should on no account be allowed to do the job.
Ich code EdgeMonkey - In dubio pro Setting.
|
|
Dim89K
Hält's aus hier
Beiträge: 3
|
Verfasst: So 09.03.08 14:11
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
| type
Tpfad = array[0..6] of string;
TForm1 = class(TForm)
pfad: TStringGrid;
Button1: TButton;
pfad2: TStringGrid;
btn_vor: TButton;
btn_back: TButton;
Label1: TLabel;
procedure btn_backClick(Sender: TObject);
procedure btn_vorClick(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure FormCreate(Sender: TObject);
private
public
end;
var
Form1: TForm1;
pfad_ar, ziel: TPfad;
loesung: array[0..15] of Tpfad;
schritt,schritt2: integer;
implementation
function suche_leer(Pfad: TPfad):integer;
var i: integer;
begin
for i:=0 to 6 do begin
if pfad[i]='_' then begin suche_leer:=i; break end;
end;
end;
function sackgasse(Pfad: TPfad):boolean;
var pos: integer;
begin
sackgasse:=true;
pos:=suche_leer(pfad_ar);
if ((pos > 1)and(pfad_ar[pos-1]='<')and(pfad_ar[pos-2]='>')) or
((pos < 5)and(pfad_ar[pos+1]='>')and(pfad_ar[pos+2]='<')) or
((pos > 0)and(pfad_ar[pos-1]='>')) or
((pos < 6)and(pfad_ar[pos+1]='<')) then begin
sackgasse:=false;
end;
end;
function f_ziel(pruef_pfad:TPfad):boolean;
var i:integer;
begin
f_ziel:=true;
for i:=0 to 6 do begin
if pruef_pfad[i]<>ziel[i] then begin f_ziel:=false; break end;
end;
end;
procedure suche(pos: integer);
var i,j,speicher2: integer;
speicher: TPfad;
begin
if not(f_ziel(pfad_ar)) then begin
pos:=suche_leer(pfad_ar);
if (pos > 0)and(pfad_ar[pos-1]='>') then begin
for i:=0 to 6 do begin
speicher[i]:=pfad_ar[i];
end;
speicher2:=schritt;
pfad_ar[pos-1]:='_';
pfad_ar[pos]:='>';
loesung[schritt]:=pfad_ar;
inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad_ar[i]:=speicher[i];
end;
dec(schritt);
end;
pos:=suche_leer(pfad_ar);
if (pos < 6)and(pfad_ar[pos+1]='<') then begin
for i:=0 to 6 do begin
speicher[i]:=pfad_ar[i];
end;
speicher2:=schritt;
pfad_ar[pos+1]:='_';
pfad_ar[pos]:='<';
loesung[schritt]:=pfad_ar;
inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad_ar[i]:=speicher[i];
end;
dec(schritt);
end;
pos:=suche_leer(pfad_ar);
if (pos > 1)and(pfad_ar[pos-1]='<')and(pfad_ar[pos-2]='>') then begin
for i:=0 to 6 do begin
speicher[i]:=pfad_ar[i];
end;
speicher2:=schritt;
pfad_ar[pos-2]:='_';
pfad_ar[pos]:='>';
loesung[schritt]:=pfad_ar;
inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad_ar[i]:=speicher[i];
end;
dec(schritt);
end;
pos:=suche_leer(pfad_ar);
if (pos < 5)and(pfad_ar[pos+1]='>')and(pfad_ar[pos+2]='<') then begin
for i:=0 to 6 do begin
speicher[i]:=pfad_ar[i];
end;
speicher2:=schritt;
pfad_ar[pos+2]:='_';
pfad_ar[pos]:='<';
loesung[schritt]:=pfad_ar;
inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad_ar[i]:=speicher[i];
end;
dec(schritt);
end;
end else for i:=0 to 6 do Form1.pfad.cells[i,0]:=pfad_ar[i];
end;
{$R *.nfm}
procedure TForm1.FormCreate(Sender: TObject);
var i: integer;
begin
pfad.Cells[0,0]:='>';
pfad.Cells[1,0]:='>';
pfad.Cells[2,0]:='>';
pfad.Cells[3,0]:='_';
pfad.Cells[4,0]:='<';
pfad.Cells[5,0]:='<';
pfad.Cells[6,0]:='<';
for i:=0 to 6 do begin
ziel[i]:= pfad.cells[6-i,0];
end;
schritt2:=0;
end;
procedure TForm1.Button1Click(Sender: TObject);
var i: integer;
begin
for i:=0 to 6 do begin
pfad_ar[i]:=pfad.cells[i,0];
end;
schritt2:=0;
loesung[schritt]:=pfad_ar;
inc(schritt);
suche(suche_leer(pfad_ar));
for i:=0 to 6 do begin
pfad2.cells[i,0]:=loesung[0,i];
end;
end;
procedure TForm1.btn_vorClick(Sender: TObject);
var i:integer;
begin
if schritt2<15 then begin
inc(schritt2);
for i:=0 to 6 do begin
pfad2.cells[i,0]:=loesung[schritt2,i];
end;
Label1.Caption:=IntToStr(schritt2);
end;
end;
procedure TForm1.btn_backClick(Sender: TObject);
var i:integer;
begin
if schritt2>0 then begin
dec(schritt2);
for i:=0 to 6 do begin
pfad2.cells[i,0]:=loesung[schritt2,i];
end;
Label1.Caption:=IntToStr(schritt2);
end;
end;
end. |
so, das ist erstma der code... die regeln:
-ausgangsituation: >>>_<<<
-ziel: <<<_>>> ('_' ist der leere platz, und da kann natürlich nur ein elefant ('<' oder '>' sind die verschiedene familien) drauf gehen)
-kein elefant darf sich rückwärts bewegen
-ein elefant darf über einen anderen drübersteigen, wenn er nicht aus seiner familie und hinter dem überstigenen elefanten ein freier platz ist
so, ich glaub das waren die regeln.... aber wie ich das schon gesagt hab, ich komme schon zum ziel, aber die aufzeichnung der einzelnen schritte funktioniert nicht ganz...
|
|
|
