Текущий архив: 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.018 c