Форум: "Основная";
Текущий архив: 2006.03.26;
Скачать: [xml.tar.bz2];

Вниз

Проблема поиска   Найти похожие ветки 

← →
-matrix- ©   (2006-02-19 13:48) [0]

Имеется массив, квадратный. По сути - лабиринт. Требуется найти минимальное время, за которое шарик перекатывается из данной точки в выход (выход непостоянен, старт - в левом верхнем углу)- НО он движиться с ускорением. То есть не каждый минимальный путь является минимальным по времени,  тк шарик тормозит на поворотах. Какой алгоритм поиска использовать, есть тупая рекурсия с перебором не справляется с временными рамками на последних тестах.
PS Ограничения на запуск рекурсии, если уже пройденное время меньше минимального (на данный момент), не помогают.

---

← →
-matrix- ©   (2006-02-20 18:38) [1]

Ну хоть какие-нибудь идеи есть? Я ведь не прошу описать мне алгоритм детально, но ведь, я знаю, существуют разные алгоритмы поиска! Просто их пару десятков видов, откуда я знаю, какие в моем случае использовать можно, а какие - не надо? Неужели никто не знает?

---

← →
Jeer ©   (2006-02-20 18:48) [2]

Ввести целевую функцию, составляющей которой (возможно основной), является минимизация "путевого" функционала с учетом динамики движения.

---

← →
Virgo_Style ©   (2006-02-20 20:52) [3]

Возможно, я не совсем понял задачу... Что, если использовать классический алгоритм поиска путей, а затем анализировать каждый из найденных путей с учетом динамики?

---

← →
Ученик чародея ©   (2006-02-20 22:02) [4]

Реализация построения матрицы кратчайших путей. Древняя. Может поможет. Виснет при несвязанном дереве.

unit LinkTo;

interface
uses math;

type inttype=integer;

type Tway=record
         port:inttype;//следующая вершина маршрута
         time:inttype;//время достижения маршрута
         end;

type TLinkMatrix=record
                size:inttype;//размерность квадратной матрицы
                links:array of array of inttype;//вес каждой связи квадратной матрицы
                //обычным числом выставляется вес связи
                //если связи нет, то ставится 0
                //пока не работает со значением связи MaxInt
                //пока не работает с "разорванными графами"
                end;

type TWaymatrix=record
              size:inttype;//размерность квадратной матрицы
              Ways:array of array of Tway;//параметры пути
              //строки матрицы обозначают вершину из которой добираемся
              //до нужной нам вершины
              //в стобцах находятся вершины достижимости
              //каждая ячейка матрицы содержит два поля
              //port обозначает следующую верщину пути
              //time время всего пути
              //например на пересечении строка-столбец[2,5]
              //значение port=4 time=6
              //это означает, сдедующая вершина пути 4
              //общее время пути от 2 до 5 вершины 6 тактов
              end;

function PPPAll(var LinkMatrix:TLinkMatrix):TWaymatrix;

implementation

function PPPAll(var LinkMatrix:TLinkMatrix):TWaymatrix;
var
X:array of inttype;
Xpoint:array of inttype;
Xm: array of boolean; { Mask of X}
P,i,j,n: inttype; { N }
Waymatrix:TWaymatrix;
begin
 SetLength(Xm,LinkMatrix.size+1);
 SetLength(X,LinkMatrix.size+1);
 SetLength(Xpoint,LinkMatrix.size+1);
 Waymatrix.Size:=LinkMatrix.Size;
 SetLength(Waymatrix.Ways,Waymatrix.Size+1,Waymatrix.Size+1);

 for j:=1 to LinkMatrix.size do
   begin

   for i:=1 to LinkMatrix.size do
     begin
     Xm[i]:=False;
     X[i]:=MaxInt;
     Xpoint[i]:=0;
     end;

   P:=j;
   Xm[P]:=True; X[P]:=0;                { step 1}

   repeat
     for i:=1 to LinkMatrix.size do if LinkMatrix.links[P, i]<>0 then
       begin
       if (X[i]>(X[P]+LinkMatrix.links[P, i])) then
         Xpoint[i]:=P;
         X[i]:=min(X[i], X[P]+LinkMatrix.links[P, i]);                   {step2 }
       end;
     for i:=1 to LinkMatrix.size do if not Xm[i] then P:=i;
     for i:=1 to LinkMatrix.size do
       if (not Xm[i]) and (X[i]<=X[P]) then P:=i;   { step 4 }
     if Xm[P] then P:=0
     else Xm[P]:=True;          { step 3}
   until P=0;

   for i:=1 to LinkMatrix.size do
     if (X[i]<>MaxInt) and (X[i]<>0) then
       begin
       n:=i;
       repeat
         if (Xpoint[n]=j) and
         (X[n]<>MaxInt)then
         begin
           Waymatrix.Ways[j,i].port:=n;
           Waymatrix.Ways[j,i].time:=X[i];
         end;
         if (Xpoint[n]<>j) then
           n:=Xpoint[n];
         if (Xpoint[n]=j) and (X[n]<>MaxInt)then
         begin
           Waymatrix.Ways[j,i].port:=n;
           Waymatrix.Ways[j,i].time:=X[i];
         end;
       until (Xpoint[n]=j)
       end;

 end;

 SetLength(Xm,0);
 SetLength(X,0);
 SetLength(Xpoint,0);
 Xm:=nil;
 Xpoint:=nil;
 X:=nil;

 PPPAll:=Waymatrix;
end;

end.


---

Страницы: 1 вся ветка

Форум: "Основная";
Текущий архив: 2006.03.26;
Скачать: [xml.tar.bz2];

Наверх

Память: 0.47 MB
Время: 0.041 c