Текущий архив: 2003.01.20;
Скачать: CL | DM;
Вниз
Нужна помощь! Найти похожие ветки
← →
SergeySS (2003-01-08 17:43) [0]Здравствуйте!
Помогите мне пожалуйста все кто может :) ну очень прошу !
За ранее всем бооольшое спасибо!
Есть лабиринт, задана начальная точка А(x,y) и конечная точка B(X1,Y1)
нужно найти самый короткий путь из точки А в точку В
Пример
0000000000000000
00А0111110000000
0000100000000000
0011100111100000
0000100000001100
00001000110000В0
1100000000000000
Где 1 - непроходимый участок(можно двигать и по вертикали)
Мне нужен только алгоритм!!!!!
Спасибо всем!1
← →
Sha © (2003-01-09 17:00) [1]Для начала разберись с вот этим:
procedure TForm1.Button1Click(Sender: TObject);
const
xsize= 3; // Размер-X
ysize= 3; // Размер-Y
zsize= xsize * ysize; // Площадь
d: array[0..3] of integer= (-1, -xsize, xsize, 1); // Смещения: лево/верх/низ/право
var
k: array[0..zsize-1] of cardinal; // Матрица кратчайших расстояний
m: array[0..zsize-1] of char; // Лабиринт-вектор
n: array[0..ysize-1,0..xsize-1] of char absolute m; // Лабиринт-матрица
xa, ya, za, xb, yb, zb, x, z, zz: integer; // Координаты точек
i: integer;
done: boolean;
s: string;
begin
// Инициализация
fillchar(m,zsize,"0"); n[1,1]:="1"; // Лабиринт
xa:=0; ya:=0; za:=ya * xsize + xa; m[za]:="2"; // Точка А
xb:=xsize-1; yb:=ysize-1; zb:=yb * xsize + xb; m[zb]:="2"; // Точка Б
fillchar(k,zsize,$FF); k[zb]:=0; // Матрица кратчайших расстояний
// Рассчитываем расстояния
repeat;
done:=true;
for z:=zsize-1 downto 0 do if (m[z]<>"1") and (k[z]<$FFFFFFFF) then begin;
x:=(z+1) mod xsize; // x=0 - правый край, x=1 - левый край, x>1 - середина
for i:=0+ord(x=1) to 3-ord(x=0) do begin;
zz:=z+d[i];
if (zz<0) or (zz>=zsize) or (m[zz]="1") or (k[zz]<=k[z]+1) then continue;
done:=false;
k[zz]:=k[z]+1;
end;
end;
until done;
// Рисуем путь
z:=za;
if k[z]<$FFFFFFFF then repeat;
for i:=3 downto 0 do begin;
zz:=z+d[i];
if (zz<0) or (zz>=zsize) or (m[zz]="1") or (k[zz]>=k[z]) then continue;
z:=zz; break;
end;
m[z]:="2";
until z=zb;
// Вывод
SetLength(s,xsize);
Memo1.Lines.Clear;
for i:=0 to ysize-1 do begin;
Move(n[i,0],pchar(s)^,xsize); Memo1.Lines.Add(s);
end;
end;
Эффективность алгоритма можно повысить в десятки раз. Основные улучшения:
1. Не хранить все расстояния в матрице, а использовать списки расстояний, полученных на каждом шаге, и при формировании очередного списка перебирать только элементы предыдущего.
2. Запоминать, откуда пришли.
3. Прекрашать вычисления, как только достигнута конечная точка назначения.
4. В самой матрице лабиринта хранить не только стенки/не_стенки, но и возможные направления движения.
← →
Думкин (2003-01-10 07:29) [2]зайди на Алголист - почитай про Волновой алгоритм, или просто поищи по этому ключу - все расписано четко и ясно.
Страницы: 1 вся ветка
Текущий архив: 2003.01.20;
Скачать: CL | DM;
Память: 0.47 MB
Время: 0.028 c
