Diagonalsumme der Matrix minimieren

Wissenschaft Informatik
#1

Hallo zusammen,

folgendes Problem habe ich gerade auch schon bei den Mathematikern eingestellt, da ich das ganze aber hinterher ohnehin programmieren möchte, frage ich hier auch mal:

Ich habe eine Matrix, wie z. B. die folgende:

5 2 3 4 0 5
0 2 2 6 7 0
5 4 4 1 2 9
8 8 1 1 5 4
1 6 8 9 5 9
5 0 3 2 7 4

Diese Matrix möchte ich durch umsortieren der Spalten oder der Zeilen (also entweder nur die Spalten oder nur die Zeilen vertauschen) so anordnen, dass auf einer der beiden Diagonalen die Summe der Zahlen möglichst gering wird.

Ich habe schon ein paar Stunden herumprobiert, aber ich komme auf keinen vernünftigen Algorithmus, der das für beliebige Matrizen korrekt macht.

Ob der Lösungsweg nur verbal beschrieben wird oder eine Lösung in (egal welcher) Programmiersprache angeboten wird, ich mir gleich. Komme dann schon irgendwie klar damit.

Vielen Dank für eure Hilfe!

#2

Minimum Cost Flow Problem

Diese Matrix möchte ich durch umsortieren der Spalten oder der
Zeilen (also entweder nur die Spalten oder nur die Zeilen
vertauschen) so anordnen, dass auf einer der beiden Diagonalen
die Summe der Zahlen möglichst gering wird.

Hallo,

das Problem läßt sich als Minimum Cost Flow Problem modellieren:

http://en.wikipedia.org/wiki/Minimum_cost_flow_problem

Es wird der folgende bipartite Graph konstruiert:
Knoten s1,…, s6 für die Spalten, z1,…,z6 für die Zeilen.
Aus der Quelle gehen Kanten mit Kapazität 1 zu den Knoten s_1,…,s_6. Von jeden Knoten s_i verläuft eine Kante mit Kapazität 1 zu jedem Knoten z_j, wobei dei Kosten aus der gegebenen Matrix stammen. Von jedem Knoten z_1,…,z_6 verläuft eine Kante mit Kapazität 1 zur Senke.

Wenn wir einen maximalen Fluss durch diesem Graphen haben, so wird jede Spalte genau einer Zeile zugeordnet, so dass wir ablesen können, welches Matrix-Element auf die Diagonale kommt. Da die Kosten minimiert wurden, ist die Summe der Diagonalelemente ebenfalls minimal.

Evt. läßt sich noch ausnutzen, dass der Graph bipartite ist und die Kanten nur Kapazitäten 1 haben.

Hoffe, die Erklärung hilft Dir weiter.

Viele Grüße
Thorsten

#3

Hallo.

Ich habe eine Matrix, wie z. B. die folgende:

5 2 3 4 0 5
0 2 2 6 7 0
5 4 4 1 2 9
8 8 1 1 5 4
1 6 8 9 5 9
5 0 3 2 7 4

Diese Matrix möchte ich durch umsortieren der Spalten oder der
Zeilen (also entweder nur die Spalten oder nur die Zeilen
vertauschen) so anordnen, dass auf einer der beiden Diagonalen
die Summe der Zahlen möglichst gering wird.

Wenn ich über dein Problem nachdenke, kommt mir folgende Idee:

Es ist egal, ob man die Spalten oder Zeilen umsortiert, man kann jede beliebige mögliche Diagonale auf beide Arten erreichen.
Man muss also erstmal nur schauen, dass man aus jeder Zeile und jeder Spalte genau eine Zahl wählt, die hinterher in der Diagonale stehen soll, dann kann man passend umsortieren.

Ich würde dann so vorgehen:

Summe\_min = unendlich
Summe = 0
Zeile = 1
Spaltenliste = {}
Spaltenliste\_min = {}

Wähle aus der aktuellen Zeile aus den Spalten, die nicht in Spaltenliste sind, die kleinste Zahl aus.
Füge die Spalte zur Spaltenliste hinzu
Summe += Matrix(Zeile, Spalte)
Wenn Summe \>= Summe\_min
 [Sprungmarke1]
 Summe -= Matrix(Zeile, Spalte)
 entfenre Spalte aus Spaltenliste
 Wenn noch nicht alle möglichen Spalten der Zeile probiert,
 Wähle nächstgrößere Zahl als Spalte
 Sonst 
 Wenn Zeile = erste Zeile
 Abbruch
 Sonst gehe eine Zeile zurück und mache weiter bei Sprungmarke1
Wenn Zeile = letzte Zeile
 Summe\_min = Summe
 Spaltenliste\_min = Spaltenliste
 Weiter bei Sprungmarke1

Summe_min enthält dann die kleinste erreichbare Summe und Spaltenliste_min die Spalten der jeweiligen Zeilen, die zu dieser Summe führen. Damit enthält Spaltenliste dann auch gleich die Zeilennummer, in die die jeweilige Zeile geschoben werden muss.

Am Beispiel sollte am Ende
Summe_min = 3
Spaltenliste_min = {5, 6, 4, 3, 1, 2}
sein. Damit wird Zeile 1 also in der neuen Matrix zu Zeile 5, Zeile 2 zu Zeile 6 usw.
Sorry, der Algo ist ein wenig holprig beschrieben, ich hoffe, du kommst trotzdem damit zurecht.

Sebastian.

#4

Brauche noch Hilfe - Minimum Cost Flow Problem
Hallo McGee,

dein Vorschlag hört sich interessant an, nur bin ich leider kein Mathematiker und verstehe noch nicht so genau, wie du das meinst.

Die Wiki-Seite war für mich nicht so richtig ergiebig, dazu benötige ich wohl etwas mehr Infos, bis ich es richtig verstanden habe.

Vielleicht bin ich bisher auch auf dem falschen Weg. Also, ich habe mal nach Minimum Cost Flow gegoogelt. Wenn ich es richtig verstanden habe, handelt es sich ein Problem der linearen Optimierung (?). Dort seint der Simplex-Algorithmus (den habe ich verstanden) die Lösung für die meisten Probleme zu sein.

Allerdings verstehe ich deine Antwort trotzdem nicht. Was meinst du mit Quelle, Kanten und Kapazität? Mit den Knoten ist scheinbar die Schnittstellen von Zeile und Spalte gemeint?

Wäre nett, wenn du deinen Lösungsvorschlag noch etwas ausführlicher beschreiben kannst.

Danke!

#5

Neuer Versuch - wie soll der Graph aussehen?
Hallo,

ich habe zwischenzeitlich noch weiter gesucht und festgestellt, dass ich nicht auf dem richtigen Weg war.

Nun weiß ich schon mal, worum es geht und was Kanten, Knoten usw. sind. Allerdings kann ich mir aus deiner Beschreibung noch nicht vorstellen, wie der Graph aussehen soll.

Zusätzlich habe ich noch eine Frage. In meinem Beispiel handelte es sich um eine Matrix, die gleich viele Zeilen und Spalten hat. Funktioniert dein Vorschlag auch, wenn die Matrix nicht gleich viele Spalten und Zeilen hat? In einem solchen Fall, soll die Diagonale des „quadratischen Teils“ mimimiert werden. Hoffentlich kann man verstehen, was ich damit meine.

Soweit schon mal vielen Dank!

#6

Hallo,

Nun weiß ich schon mal, worum es geht und was Kanten, Knoten
usw. sind. Allerdings kann ich mir aus deiner Beschreibung
noch nicht vorstellen, wie der Graph aussehen soll.

In diesem Skript finden sich ab Seite 87 eine Einleitung zu Flüssen:

http://ls2-www.cs.uni-dortmund.de/lehre/sommer2002/e…

Bei den dargestellten Flüssen gibt es jedoch an den Kanten nur eine Kapazität und einen Fluss.

Hier gibt es zusätzlich noch Kosten an den Kanten.

Vom Prinzip her sieht der konstruierte Graph so ähnlich aus wie in diesem Bild:

http://upload.wikimedia.org/wikipedia/commons/0/0e/M…

Links die Quelle Q, rechts die Senke S.
Die roten Knoten links stehen für die Spalten s1, … s_i, … s_n
die grünen Knoten rechts stehen für die Zeilen z_1, …, z_j, … z_n

Q -> s_i Kapazität 1, Kosten 0
s_i -> z_j Kapazität 1, Kosten wie in der Matrix an Position (j,i)
z_j -> S Kapazität 1, Kosten 0

für alle i = 1,…,n und j = 1,…,n

Zunächst jedoch einen Schritt zurück: Wie groß ist das n bei
Deiner n x n Matrix?
Wenn es eher n

#7

Danke
Hallo Sebastian,
Hallo McGee,

vielen Dank für eure Antworten.

Ich habe es erst mal so umgesetzt dass ich bei nicht quadratischen Matrizen zunächst dafür sorge, dass die längere Seite den Spalten entspricht.

Dann ermittele ich mit einem rekursiven Algo alle möglichen Permutationen der Spaltenreihenfolge. Damit ich die Möglichkeiten nicht alle speichern muss, ermittele ich, sobald eine neue Permutation gerechnet wurde, die Diagonalsumme. Ich speichere nur die aktuelle Diagonalsumme und die bisher kleinste Diagonalsumme (mit der zugehörigen Reihenfolge natürlich). Wenn ich alle Möglichkeiten getestet habe, erhalte ich die gesuchte Reihenfolge.

@McGee
Deinen Vorschlag finde ich sehr interessant. Aber momentan fehlen mir noch die notwendigen Kenntnisse um ihn zu implementieren. Sobald ich mir genug angelesen habe, werde ich es aber trotzdem in Angriff nehmen. Ich bin einfach mal neugierig, ob das einen Zeitgewinn bringt - und dummer werde ich dadurch ja auch nicht…

Noch zu deinen Fragen, die Matrizen, mit denen ich es Momentan zu tun habe sind alle n

#8

Hallo Fragewurm,

Dann ermittele ich mit einem rekursiven Algo alle möglichen
Permutationen der Spaltenreihenfolge. Damit ich die
Möglichkeiten nicht alle speichern muss, ermittele ich, sobald
eine neue Permutation gerechnet wurde, die Diagonalsumme. Ich
speichere nur die aktuelle Diagonalsumme und die bisher
kleinste Diagonalsumme (mit der zugehörigen Reihenfolge
natürlich). Wenn ich alle Möglichkeiten getestet habe, erhalte
ich die gesuchte Reihenfolge.

Eigentlich genügt es die Ziffern aufsteigend zu sortieren und dann die Anzahl, entsprechend der Diagonalen, der kleinsten Wertezu nehmen.

MfG Peter(TOO)

#9

Hallo Peter,

wie man merkt bin ich weder Mathematiker noch Informatiker, man fragt sich halt so durch. Hätte vielleicht doch was anderes als BWL studieren sollen…

Danke für die Anregung, werde ich auch mal testen.

powerblue

#10

Hallo powerblue,

wie man merkt bin ich weder Mathematiker noch Informatiker,
man fragt sich halt so durch. Hätte vielleicht doch was
anderes als BWL studieren sollen…

Sorry, aber das hat nichts mit Informatik und auch nichts mit höherer Mathematik zu tun, sondern nur etwas mit gesundem Menschenverstand.

Wenn ich 9 Werte habe und aus beliebigen 3 dieser Werte die kleinste Summe bilden soll, muss ich die 3 kleinsten Werte nehmen.

Diese Aufgabe löst schon jedes kleine Kind. Da gehts dann halt um Kirschen und Tortenstücke und welche Stücke es auslesen muss um am meisten Kirschen zu erhalten …

MfG Peter(TOO)

#11

Hallo Peter,

Wenn ich 9 Werte habe und aus beliebigen 3 dieser Werte die
kleinste Summe bilden soll, muss ich die 3 kleinsten Werte
nehmen.

sorry, aber dann hast du die Problemstellung eventuell nicht genau genug gelesen: Es kann aus jeder Zeile nur eine Zahl gewählt werden; zudem darf jede Spalte nur einmal vorkommen, damit die Zahlen sich auf der Diagonalen anordnen lassen. Es ist also nicht mit einer einfachen Bestimmung des Minimums ohne jegliche Nebenbedingungen getan.

Gruß

Andreas

#12

Hallo Andreas,

Wenn ich 9 Werte habe und aus beliebigen 3 dieser Werte die
kleinste Summe bilden soll, muss ich die 3 kleinsten Werte
nehmen.

sorry, aber dann hast du die Problemstellung eventuell nicht
genau genug gelesen: Es kann aus jeder Zeile nur eine Zahl
gewählt werden; zudem darf jede Spalte nur einmal vorkommen,
damit die Zahlen sich auf der Diagonalen anordnen lassen. Es
ist also nicht mit einer einfachen Bestimmung des Minimums
ohne jegliche Nebenbedingungen getan.

Ist doch kein Problem und eigentlich eine Nebensache.

Er darf ja die Matrix beliebig horizontal und vertikal rotieren.

Im Prinzip dürfen die Werte alle nebeneinander in einer Zeile liegen.
Die Diagonale ergibt sich dann, wenn man man jede Spalte um eine Position mehr als die vorangehende rotiert.

Ist also mathematisch gar nicht relevant, dass es eine Diagonale ist :wink:

MfG Peter(TOO)

#13

Hi und guten Abend,

Im Prinzip dürfen die Werte alle nebeneinander in einer Zeile
liegen.

Die Diagonale ergibt sich dann, wenn man man jede Spalte um
eine Position mehr als die vorangehende rotiert.

nein, das geht nicht; diese Zahlen eignen sich gerade nicht für die Lösung. Als einzige Operation waren Vertauschungen von ganzen Zeilen (oder Spalten) erlaubt, aber nicht das In-sich-Rotieren von einzelnen Zeilen/Spalten.

So eine Struktur an ausgewählten Zahlen lässt sich also in eine Diagonale überführen:

X . . . .
. . . X .
. X . . .
. . . . X
. . X . .

Eine solche aber nicht:

X X X . .
. . X . .
. . X . .
. . . . .
. . . . .

Andreas

#14

Hallo zusammen,

Andreas hat recht, die Problemstellung ist, die Diagonalsumme durch vertauschen nur von Spalten oder nur von Zeilen zu minimieren.

Wenn ich die Matrix beliebig rotieren könnte, hätte hier keine Frage eingestellt - so deppig bin ich dann auch nicht.

powerblue

#15

Hallo Fragewurm,

Sorry, ich habe mich da beim ersten Durchgang verlesen.

Ich bleibe dabei, alle Ziffern zu sortieren
Ich hab mich jetzt dafür entschlossen am Ende die Zeilen zu vertauschen und habe die Zeilen auch noch einzeln sortiert.

5 2 3 4 0 5 = 0 2 3 4 5 5 
0 2 2 6 7 0 = 0 0 2 2 6 7 
5 4 4 1 2 9 = 1 2 4 4 5 9
8 8 1 1 5 4 = 1 1 4 5 8 8 
1 6 8 9 5 9 = 1 5 6 8 9 9
5 0 3 2 7 4 = 0 2 3 4 5 7

Alle Werte: 0 0 0 0 1 1 1 1 2 2 2 2 2 3 3 4 4 4 4 4 5 5 5 5 5 5 6 6 7 7 8 8 8 9 9 9

nun streichen wir die höchsten Werte bis in einer Zeile oder Spalte nur noch 1 Wert stehen bleibt:

 2 3 0 = 0 2 3 
0 2 2 0 = 0 0 2 2 
 1 2 = 1 2 
 1 1 = 1 1 
1 = 1 
 0 3 2 = 0 2 3 

Alle Werte: 0 0 0 0 1 1 1 1 2 2 2 2 2 3 3

In der 5. Zeile und der 6. Spalte steht jetzt nur noch ein Wert. Diese werden jetzt markiert und gegen weiteres Löschen geschützt. In der 2. Zeile können die restlichen Werte entfernt werden. Alle entfernten Werte, werden auch aus „Alle Werte“ entfernt.

 2 3 0 = 0 2 3 
0 2 2 **0** =
 1 2 = 1 2 
 1 1 = 1 1 
**1** =
 0 3 2 = 0 2 3 

Alle Werte: 0 0 0 1 1 1 1 2 2 2 2 2 3 3

und weiter gehts:

**0** = 
**0** =
**1** = 
**1** 1 = 1 
**1** =
**0** = 

Alle Werte: 0 0 0 1 1 1 1

und noch eine Runde:

**0** =
**0** =
**1** = 
**1** =
**1** =
**0** = 

Alle Werte: 0 0 0 1 1 1

Das sortieren der Zeilen sollte jetzt kein Problem mehr sein.
Die Summe auf der Diagonalen, kann man nun auch gleich aus „Alle Werte“ ersehen, diese ist 3.

Dieses Vorgehen wird nicht in jedem Fall das optimale Ergebnis bringen, dazu müsste man immer bei derjenigen Zeile streichen, welche noch dir grösste Restsumme enthält.

MfG Peter(TOO)

#16

Hallo.

Ich bleibe dabei, alle Ziffern zu sortieren
Ich hab mich jetzt dafür entschlossen am Ende die Zeilen zu
vertauschen und habe die Zeilen auch noch einzeln sortiert.

nun streichen wir die höchsten Werte bis in einer Zeile oder
Spalte nur noch 1 Wert stehen bleibt:

Da habe ich ein Gegenbeispiel:

 3 2 1
 0 9 11
 8 10 12

Zahlen sortiert: 0 1 2 3 8 9 10 11 12

  1. Durchlauf:

    3 2 1
    0 9
    8

Daraus ergibt sich dann als Summe 8+9+1=18
Offenbar günstiger wäre aber 1+0+10=11.

Oder siehst du das anders?

Sebastian.

#17

Hallo zusammen,

folgendes Problem habe ich gerade auch schon bei den
Mathematikern eingestellt, da ich das ganze aber hinterher
ohnehin programmieren möchte, frage ich hier auch mal:

Ich habe eine Matrix, wie z. B. die folgende:

5 2 3 4 0 5
0 2 2 6 7 0
5 4 4 1 2 9
8 8 1 1 5 4
1 6 8 9 5 9
5 0 3 2 7 4

Diese Matrix möchte ich durch umsortieren der Spalten oder der
Zeilen (also entweder nur die Spalten oder nur die Zeilen
vertauschen) so anordnen, dass auf einer der beiden Diagonalen
die Summe der Zahlen möglichst gering wird.

Ich habe schon ein paar Stunden herumprobiert, aber ich komme
auf keinen vernünftigen Algorithmus, der das für beliebige
Matrizen korrekt macht.

Ob der Lösungsweg nur verbal beschrieben wird oder eine Lösung
in (egal welcher) Programmiersprache angeboten wird, ich mir
gleich. Komme dann schon irgendwie klar damit.

Hi powerblue !

Wenn ich mich nicht irre, ist das das sogenannte stable marriage problem
http://en.wikipedia.org/wiki/Stable_marriage_problem
Dabei geht es darum, dass n Frauen mit n Männern verheiratet werden sollen. Jede Frau hat eine eigene sogenannte Präferenzliste der Männer, d.h. eine Reihenfolge nach der sie die Männer anordnet. Der Mann mit dem sie am liebsten verheiratet wäre steht ganz oben auf der Liste, der zweitliebste Kandidat als zweites usw. Genauso hat jeder Mann eine eigene Präferenzliste der Frauen.
Nun geht es darum n Ehepaare zu bilden, sodass es keine Frau gibt, die ihrem Ehemann einen anderen Mann vorziehen würde der gleichzeitig diese Frau seiner Ehefrau vorziehen würde. Es soll also kein Paar geben bei dem beide Partner den jeweils anderen dem Ehepartner vorziehen würden. Ist das der Fall, dann nennt man die Heirat stabil.
Es gibt einen ziemlich cleveren Algorithmus um dieses Problem zu lösen, den Gale-Shapley-Algorithmus.
Man kann zeigen, dass die Heirat die dieser Algorithmus berechnet unter allen stabilen Heiraten die schlechteste für die Frauen und die beste für die Männer ist.
Was hat das jetzt mit deinem Problem zu tun ?
Stell dir vor die Spalten deiner Matrix sind Frauen und die Zeilen Männer. Die Spalten wollen mit den Zeilen verheiratet werden, d.h. du suchst ein gemeinsames Element, was später dein Diagonalelement wird.
Was ist mit den Präferenzlisten ?
Jede Zeile will natürlich die Spalte heiraten mit der sie das kleinste gemeinsame Element hat und umgekehrt.

Ich hoffe das hilft dir erst mal weiter, ansonsten frag am besten nochmal nach.

Grüße

hendrik