4
사각형 행렬 N x N 인 가중 그래프에서 Dijkstra Shortest Path Search의 구현 속도를 높이는 조언을 찾고 있습니다. 수평 꼭지점의 가중치를 H 수평 수직선에 수직선). 이 더 큰 응용 프로그램의 일부입니다, 물론Delphi에서의 Dijkstra 최단 경로 검색 최적화
A picture is worth a thousand words! http://lionelgermain.free.fr/img/graphe.png
,하지만 난 관련 비트 여기에서 추출했습니다 :
은 천개의 단어가 그림의 가치가
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls;
const
N = 200; //Working on a grid of N x N, here for a quick test, in practice, it's more 10000
type
TForm1 = class(TForm)
Button1: TButton;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
end;
TNode = class
public
ID, //Number of the Node
origin, //From which Node did I came?
weight : integer; //The total weight of the path to Node ID
done : boolean; //Is the Node already explored?
constructor Create(myID, myOrigin, myweight: integer);
end;
var
Form1: TForm1;
implementation
var
H, V : array of integer;
{$R *.dfm}
constructor TNode.Create(myID, myOrigin, myweight: integer);
begin
ID:=MyID;
origin:=MyOrigin;
weight:=MyWeight;
end;
{------------------------------------------------------------------------------}
Function GetNodeFromID(ID: integer; NodeList: TList) : TNode; overload;
var
I: Integer;
Node: TNode;
begin
result:=nil;
for I := 0 to NodeList.count-1 do
begin
Node := NodeList[i];
if Node.ID=ID then
begin
result:=Node;
break;
end;
end;
end;
{------------------------------------------------------------------------------}
Function GetNodeOfMiniWeight(NodeList: TList) : TNode; overload;
var
I, min: Integer;
Node: TNode;
begin
result:=nil;
min :=maxint;
for I := 0 to NodeList.count-1 do
begin
Node := NodeList[i];
if Node.done then continue;
if Node.weight < min then
begin
result:=Node;
min := Node.weight;
end;
end;
end;
{------------------------------------------------------------------------------}
procedure SearchShortestPath(origin,arrival: integer);
var
NewWeight: integer;
NodeList : Tlist;
NodeFrom, //The Node currently being examined
NodeTo :TNode; //The Node where it is intented to go
s : string;
begin
NodeList := Tlist.Create;
NodeFrom := TNode.Create(origin,MaxInt,0);
NodeList.Add(NodeFrom);
while not (NodeFrom.ID = arrival) do //Arrived?
begin
//Path toward the top
if (NodeFrom.ID > N-1) //Already at the top of the grid
and not(NodeFrom.origin-NodeFrom.ID = N) then //Coming from the top
begin
NewWeight:=NodeFrom.weight + H[NodeFrom.ID-N];
NodeTo := GetNodeFromID(NodeFrom.ID-N, NodeList);
if NodeTo <> nil then
begin
if NodeTo.weight > NewWeight then
begin
NodeTo.Origin:=NodeFrom.ID;
NodeTo.weight:=NewWeight;
end;
end
else
begin
NodeTo := TNode.Create(NodeFrom.ID-N,NodeFrom.ID,NewWeight);
NodeList.Add(NodeTo);
end;
end;
//Path toward the bottom
if (NodeFrom.ID < N*N-N) //Already at the bottom of the grid
and not(NodeFrom.Origin- NodeFrom.ID = N) then //Coming from the bottom
begin
NewWeight:=NodeFrom.weight + H[NodeFrom.ID];
NodeTo := GetNodeFromID(NodeFrom.ID+N, NodeList);
if NodeTo <> nil then
begin
if NodeTo.weight > NewWeight then
begin
NodeTo.Origin:=NodeFrom.ID;
NodeTo.weight:=NewWeight;
end;
end
else
begin
NodeTo := TNode.Create(NodeFrom.ID+N,NodeFrom.ID,NewWeight);
NodeList.Add(NodeTo);
end;
end;
//Path toward the right
if not(NodeFrom.ID mod N = N-1) //Already at the extrem right of the grid
and not(NodeFrom.Origin - NodeFrom.ID = 1) then //Coming from the right
begin
NewWeight:=NodeFrom.weight + V[NodeFrom.ID];
NodeTo := GetNodeFromID(NodeFrom.ID+1, NodeList);
if NodeTo <> nil then
begin
if NodeTo.weight > NewWeight then
begin
NodeTo.Origin:=NodeFrom.ID;
NodeTo.weight:=NewWeight;
end;
end
else
begin
NodeTo := TNode.Create(NodeFrom.ID+1,NodeFrom.ID,NewWeight);
NodeList.Add(NodeTo);
end;
end;
//Path toward the left
if not (NodeFrom.ID mod N = 0) //Already at the extrem right of the grid
and not(NodeFrom.Origin - NodeFrom.ID = -1) then //Coming from the left
begin
NewWeight:=NodeFrom.weight + V[NodeFrom.ID-1];
NodeTo := GetNodeFromID(NodeFrom.ID-1, NodeList);
if NodeTo <> nil then
begin
if NodeTo.weight > NewWeight then
begin
NodeTo.Origin:=NodeFrom.ID;
NodeTo.weight:=NewWeight;
end;
end
else
begin
NodeTo := TNode.Create(NodeFrom.ID-1,NodeFrom.ID,NewWeight);
NodeList.Add(NodeTo);
end;
end;
NodeFrom.done :=true;
NodeFrom:=GetNodeOfMiniWeight(NodeList);
end;
s:='The shortest path from '
+ inttostr(arrival) + ' to '
+ inttostr(origin) + ' is : ';
//Get the path
while (NodeFrom.ID <> origin) do
begin
s:= s + inttostr(NodeFrom.ID) + ', ';
NodeFrom:=GetNodeFromID(NodeFrom.Origin, NodeList);
end;
s:= s + inttostr(NodeFrom.ID);
ShowMessage(s);
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
SearchShortestPath(Random(N*N),Random(N*N));
end;
procedure TForm1.FormCreate(Sender: TObject);
var
I: Integer;
begin
//Initialisation
randomize;
SetLength(V,N*N);
SetLength(H,N*N);
for I := 0 to N*N-1 do
begin
V[I]:=random(100);
H[I]:=random(100);
end;
end;
end.
코드는 루틴에서 대부분의 시간 : GetNodeFromID 및 GetNodeOfMiniWeight을 사용하며 노드를 만드는 데 많은 시간을 소비합니다.
필자는 이진 검색을 사용할 수 있다고 생각했지만 목록을 정렬해야하므로이 목록을 정렬하는 데 시간이 많이 걸릴 것으로 생각됩니다. 어떤 조언을 환영합니다.
다른 구현에서는 어떤 알고리즘 최적화를 사용합니까? –
웹에서 본 구현은 임의의 그래프에 있으며 특정 컨테이너를 사용합니다. 내 프로그램에서 N, H 및 V는 이미 메모리에 저장되어 있습니다. 다른 컨테이너를 사용하는 경우 그래프를 작성할 시간을 더한 메모리를 잃어 버리고 있습니다. –
Dijkstra 알고리즘은 선택된 하나의 노드에서 다른 모든 노드까지의 최단 경로를 찾습니다. 임의의 쌍의 노드 사이에서 S.P.를 검색하고 있습니다. 모든 노드 사이에 S.P.가 필요합니까 (예 : Floyd 's algo와 같은) 또는 두 개의 선택된 노드 사이에 S.P.가 하나만 필요합니까 (예 : A * (A-Star)와 같은)? – MBo