grösstes Element in einem 2d-Array finden

[lurchlarve]

Hallo und danke für das herzliche Willkommen!

Ich weiss nicht, ob ihr mir da weiterhelfen könnt, aber es geht konkret um folgendes Problem:

Ich habe als Aufgabe, den Saving-Algorithmus einzubinden. Kurze Erklärung: Der Algorithmus dient dazu, in einem ungerichteten Graphen (also zum Beispiel ein Strassennetz), die Touren zu berechnen, wie man am günstigsten jeden Knoten derart anfährt, dass man...

a) die maximale Länge der Tour nicht überschreitet
b) die maximale Ladung nicht überschreitet

..also...sowas wird zum Beispiel in der Fahrzeugeinsatzplanung (Müllabfuhr) benötigt, um zu planen, wie die vorhandenen Fahrzeuge am besten eingesetzt werden, ohne möglichst viel Strecke zu fahren und ohne die maximale Ladekapizität zu überschreiten.

genauere Erklärung wäre hier zu umfangreich...

Jedenfalls erstelle ich eine Entfernungsmatrix, die die Entfernung von jedem Knotenpunkt zu jedem anderen enthält. Dann berechne ich diese sog. Savingwerte, die angeben, wie groß die Optimiereung für eine Tour wäre, wenn man über diese Knoten fährt.

Diese Matrix sieht z.B. so aus:

Code:

    1   2   3   4   5   6

1       45  72  45  76  45

2           41  84  67  84

3               71  112 65

4                   111 122

5                       105

6                       0

Der nächste Schritt im Algorithmus ist, dass man sich den grössten Wert aus dieser Tabelle heraus sucht, da dieser Wert die beste Optimierung hat. Dann macht man diverse Sachen (auf die ich nicht näher eingehe), nimmt dann den zweitgrössten , usw...

D.h. ich gehe alle Werte nacheinander durch, vom grössten zum kleinsten.

Da ich nun ja nicht jedes Mal die komplette Matrix durchsuchen will, dachte ich mir, da müsste es noch eine andere Lösung geben...

Wäre nett, wenn ihr nochmal drüber grübeln würdet, denn...
das:

Delphi-Quellcode:

for i := 1 to n do
begin
  for j:= i+1 to n do
  begin
    if Matrix[i,j] > temp then
    begin
      temp := Matrix[i,j];
      a := i;
      b := j;
    end;
  end;
end;
//temp ist nun grösstes Element mit Koordinaten [a,b]

...ist ja wohl nicht sehr schnell. In diesem Beispiel wahrscheinlich verkraftbar - aber gewöhnliche Strassennetze haben eine Matrix von 1000*1000 Feldern...

Was sagen die Fachleute?

Gruß,

Björn

[edit=Daniel B]Delphi-Tags eingefügt. MfG Daniel B.[/edit]