grösstes Element in einem 2d-Array finden

[lurchlarve]

Hallo!

Ich habe eine n*n - Matrix mit n Elementen. Ich versuche nun. eine Funktion zu schreiben, die mir die Koordinaten des grössten Elements in der Matrix zurück liefert. Dabei möchte ich umgehen, die komplette Matrix jedesmal zu durchsuchen.

Nun meine Frage:

Wie finde ich am besten den grössten Wert in einer 2-dimensionalen Matrix?
Gibt es bereits in Delphi eine Funktion, die man aufrufen kann, die dies tut? Habe bis jetzt nur herausgefunden, wie man die Anzahl der Elemente heraus finden kann:

Code:

Anzahl_Elemente := high(Matrix);

Gibt es vielleicht sowas, wie

Code:

Max_Element := max(Matrix);

Ich weiss, dass es sowas in PHP gibt...das ist aber auch alles.

Oder wie würdet ihr eine 2-dimensionale Matrix absteigend nach ihren Werten sortieren?

Für Ideen wäre ich dankbar!

Gruß,

Björn

[Christian Seehase]

Moin Björn,

erst einmal herzlich willkommen hier in der Delphi-PRAXiS.

Die Funktion high liefert Dir nicht die Anzahl, sondern die Anzahl - 1 zurück length würde die Anzahl zurückgeben.

Ich gehe mal davon aus, dass Du mit der Matrix eine zweidimensionale Tabelle meinst.
Den Inhalt zu sortieren wäre wohl keine gute Idee, denn die Position eines Wertes in der Tabelle wird wohl durchaus ihren Sinn haben.

Die Unit Math kennt nur eine Funktion für eine eindimensionale Tabelle mit double Werten (MaxValue).

Ob jetzt Deine Funktion es macht, oder eine von wo auch immer stammende:
Bei einer nicht sortierten Tabelle wird einem (unabhängig von der Anzahl der Dimensionen) nichts anderes übrig bleiben alles alle Elemente durchzugehen.

[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]

[Christian Seehase]

Moin Björn,

dann solltest Du diese zweidimensionale Tabelle auf eine eindimensionale sortierte abbilden.
Eventuell mit TList, so dass die Koordinaten mit als Objekt hinzugefügt werden.

In diesem Falle wäre es wichtig zu wissen, welche Wertebereiche die Koordinaten und die Tabelleneinträge haben können. Am besten dabei nicht zu knapp rechnen, lieber zu üppig. Ich hätte da nämlich eine Idee, wie man zumindest schon mal das abbilden auf eine Dimension gut hinbekommen kann. Hängt aber von den Wertebereichen ab.

[lurchlarve]

Hallo nochmals!

Ich glaub gleich muss ich mal ins Bett - bin bereits seit 13 Stunden am proggen !

Noch mal zu der Matrix:

Code:

- Die Matrix ist immer symmetrisch (n * n)
- n ist zwischen 5 und 3000, d.h. die Matrix hat zwischen 25 und
  9.000.000 Elemente abhängig von der Anzahl der Knoten im Strassennetz
- Die Werte der Elemente variieren zwischen -32.000 und +32.000
- (-32 000  = unendlich negative Optimierung, +32.000 = unendlich gute
  Optimierung)

Mit welchem Algorithmus kann ich die 2-dimensionale Matrix also anständig in einem 1-dimensionalen Array (absteigend sortiert nach Werten) speichern?

Ich hoffe, ich konnte nochmal wertvolle Infos beisteurn...

Gruß,

Björn (tooootmüde! )

[Sharky]

Hai lurchlarve,

eine Frage am Rande:

Wie kommen die Werte denn in die Matrix?

Eventuell wäre es ja sinnvoll den größten Wert beim füllen der Matrix zu ermitteln?