|
|
|
Minimierung der Gesamtdistanz |
|
| panoma |
Forum-Newbie
|
 |
Beiträge: 5
|
|
|
|
Anmeldedatum: 22.08.08
|
|
|
|
Wohnort: Marburg
|
|
|
|
Version: ---
|
|
|
|
 |
|
Verfasst am: 22.08.2008, 19:30
Titel: Minimierung der Gesamtdistanz
|
 |
| |
 |
 |
Hallo Forum,
ich bin ein Anfänger in der Matlab-Programmierung und habe folgendes Problem:
ich betreibe statistisches Matching, d.h. ich suche zu einem bestimmten Datensatz aus der Menge A den am besten geeigneten Datensatz aus der Menge B auf der Grundlage von Distanzen. Mein Ziel ist die Minimierung der Gesamtdistanz beim Zuweisen der sog. statistischen Zwillinge.
Gegeben ist eine nicht-symmetrische Matrix mit Distanzen zwischen jedem Datensatz aus A und jedem Datensatz aus B, die so aussehen könnte:
0,3 0,2 0,6 0,9
0,1 0,4 0,8 0,2
0,5 0,1 0,8 0,8
0,9 0,8 0,7 0,8
0,1 0,3 0,1 0,5
Die erste Spalte enthält also die Distanzen zwischen dem ersten Datensatz aus A und allen Datensätzen aus B usw.
Ich benötige nun einen Algorithmus, der aus jeder Spalte genau ein Element auswählt und die Summe dieser Elemente minimiert. Dabei darf aber jede Zeile nur maximal ein Mal vorkommen. Da es sich um sehr große Matritzen handelt, ist das sture Berechnen aller Möglichkeiten zu aufwändig.
Hat jemand eine Idee für einen Lösungsansatz 
|
|
|
|
|
|
| nschlange |
Ehrenmitglied
|
|
Beiträge: 1.318
|
|
|
|
Anmeldedatum: 06.09.07
|
|
|
|
Wohnort: NRW
|
|
|
|
Version: R2007b
|
|
|
|
|
|
|
Verfasst am: 22.08.2008, 21:59
Titel: Re: Minimierung der Gesamtdistanz
|
|
| panoma hat Folgendes geschrieben: |
Hallo Forum,
...
Ich benötige nun einen Algorithmus, der aus jeder Spalte genau ein Element auswählt und die Summe dieser Elemente minimiert. ... |
Hi,
vielleicht kannst Du diesen Satz mit einem Beispiel nochmal genauer erklären.
Welches Element soll ausgewählt werden, welche werden dann summiert und was wird minimiert?
_________________
Viele Grüße
nschlange
"Chuck Norris ejakuliert fluessigen Stahl!"
|
|
|
|
| panoma |
Themenstarter
Forum-Newbie
|
|
Beiträge: 5
|
|
|
|
Anmeldedatum: 22.08.08
|
|
|
|
Wohnort: Marburg
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 23.08.2008, 10:18
Titel:
|
|
| |
|
|
Hallo nschlange,
gerne versuche ich das:
gesucht ist eine Kombination von Einträgen der Matrix von links nach rechts, d.h. ein Weg durch die Spalten (günstigster Pfad (?)), sodass aus jeder Spalte der Matrix genau ein Eintrag gewählt wird. Nebenbedingung des Ganzen ist, dass aus jeder Zeile aber nur maximal ein Eintrag ausgewählt werden darf. Das bedeutet: wenn bspw. in der ersten Spalte das Element in der 3. Zeile ausgewählt wird, dann darf in keiner anderen Spalte mehr das dritte Element gewählt werden. Diese Spalte ist dann für alle weiteren Schritte gesperrt usw.
Dabei sollen die Elemente aus der Matrix so gewählt werden, dass die Summe dieser bestimmten Elemente minimiert wird.
In meinem kleinen Beispiel aus dem ersten Posting würde der Algorithmus die Elemente (1,1) - (3,2) - (5,3) - (2,4) mit der Gesamtsumme von 0,3+0,1+0,1+0,2=0,7 auswählen (wenn ich keine günstigere Kombination übersehen habe), weil alle anderen Kombinationen von Elementen von links nach rechts eine größere Gesamtsumme ergeben würden. Jede Spalte ist in der Auswahl genau ein Mal vertreten, jede Zeile maximal ein Mal.
|
|
|
|
| nschlange |
Ehrenmitglied
|
|
Beiträge: 1.318
|
|
|
|
Anmeldedatum: 06.09.07
|
|
|
|
Wohnort: NRW
|
|
|
|
Version: R2007b
|
|
|
|
|
|
|
Verfasst am: 23.08.2008, 16:37
Titel:
|
|
Hi,
ja, die Beschreibung ist gut.
Trotzdem hab ich nur eine erste grobe Idee:
Ich würde als erstes mit
die Minima jeder Spalte bestimmen. In I ist dann der zugehörige Zeilenindex.
Im Beispiel wäre:
Aber Zeile zwei darf ja nur einmal ausgewählt werden, hier müsste man dann wohl verzweigen. Ich würde einmal ein NaN in matrix(2,1) schreiben und den Vorgang wiederholen, und dann in matrix(2,4) ein NaN und alles wiederholen. Das müsste man wohl für jede Kombination der Spaltenminima machen.
Dann fällt mir noch Backtracking ein, man muss ja nicht weiterrechnen, wenn schon die Summe über zwei Spalten größer ist, als eine zuvor berechnete.
Und vielleicht ist das sogar ein 'Standardproblem' der Graphen- oder Spieltheorie. Aber da hab ich nicht weiter Ahnung von.
_________________
Viele Grüße
nschlange
"Chuck Norris ejakuliert fluessigen Stahl!"
|
|
|
|
| panoma |
Themenstarter
Forum-Newbie
|
|
Beiträge: 5
|
|
|
|
Anmeldedatum: 22.08.08
|
|
|
|
Wohnort: Marburg
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 23.08.2008, 17:28
Titel:
|
|
Über Graphentheorie habe ich auch schon nachgedacht. Dort gibt es ähnliche Probleme, wie bspw. das Travelling-Salesman-Problem, das mit Standard-Algorithmen wie dem Dijkstra-Algorithmus gelöst werden kann. Der große Unterschied zu meinem Problem ist aber, dass in der Graphentheorie nur eine Menge von Knoten (Datensätzen) betrachtet wird und die Distanzen dieser einen Menge von Knoten untereinander in einer symmetrischen Distanzmatrix abgebildet werden.
Ich habe aber zwei Mengen von Datensätzen und betrachte jeweils die Distanz von einem Datensatz der einen Menge zu jedem Datensatz der anderen Menge. Ich habe also keine klassische symmetrische Distanzmatrix.
Über das Backtracking werde ich mal nachdenken....
|
|
|
|
| nschlange |
Ehrenmitglied
|
|
Beiträge: 1.318
|
|
|
|
Anmeldedatum: 06.09.07
|
|
|
|
Wohnort: NRW
|
|
|
|
Version: R2007b
|
|
|
|
|
|
|
Verfasst am: 23.08.2008, 19:37
Titel:
|
|
Hi,
ich hab mal meine Idee von Hand durchgetestet, siehe Anhang. Vielleicht findest Du für Dich noch interessante Befehle.
Das ich zweimal Hintereinander das Minimum aus der 1. Spalte rauswerfen musste wusste ich ja. Da wird man jede Kombination ausprobieren müssen, dann die Summe bilden und sich die Kombination merken, die die kleinste Summe geliefert hat.
Ich finde die Aufgabe schon interessant...
| Beschreibung: |
|
Download |
| Dateiname: |
panoma.pdf |
| Dateigröße: |
22.18 KB |
| Heruntergeladen: |
776 mal |
_________________
Viele Grüße
nschlange
"Chuck Norris ejakuliert fluessigen Stahl!"
|
|
|
|
| panoma |
Themenstarter
Forum-Newbie
|
|
Beiträge: 5
|
|
|
|
Anmeldedatum: 22.08.08
|
|
|
|
Wohnort: Marburg
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 23.08.2008, 20:21
Titel:
|
|
Hallo nschlange,
danke für die Idee. Ich werde versuchen, das Ganze mal zu implementieren und an meinen "tatsächlichen" Daten zu testen.
Mit der Optimierungs-Toolbox kommt man vermutlich auch nicht weit, weil der Optimierungsalgorithmus (z.B. Simplex) ja nur vorgegebene Werte aus meiner Matrix zum Finden der Lösung verwenden darf. Ich dachte schon mal an "fmincon". Aber da bliebe dann noch das Problem, wie man die Restriktion "jede Zeile darf maximal ein Mal verwendet werden" abbildet?!?
Viele Grüße
Panoma
|
|
|
|
| Bijick |
Ehrenmitglied
|
|
Beiträge: 914
|
|
|
|
Anmeldedatum: 18.06.07
|
|
|
|
Wohnort: Nürnberg
|
|
|
|
Version: R2006b, R2008b
|
|
|
|
|
|
|
Verfasst am: 25.08.2008, 11:10
Titel:
|
|
Hallo Panoma,
ich denke, dass die "Ungarische Methode" für Dein Problem geeignet sein könnte. Das hier zu beschreiben, ist etwas kompliziert, aber bei Wikipedia (hier) findet man eine ganz gute Beschreibung mit Pseudo-Algorithmus. Bei Fragen dazu helfe ich auch gern weiter.
Herzliche Grüße
Bijick
_________________
>> why
|
|
|
|
| panoma |
Themenstarter
Forum-Newbie
|
|
Beiträge: 5
|
|
|
|
Anmeldedatum: 22.08.08
|
|
|
|
Wohnort: Marburg
|
|
|
|
Version: ---
|
|
|
|
|
|
|
Verfasst am: 25.08.2008, 16:38
Titel:
|
|
Hallo Bijick,
ich habe den Wikipedia-Artikel zur ungarischen Methode gerade gelesen und denke, dass er tatsächlich die Lösung zu meinem Problem sein kann. Vielen Dank für den Hinweis und auch für die angebotene Hilfe. Mal sehen, wie die Umsetzung in Matlab-Code klappt.
Viele Grüße
Panoma
|
|
|
|
|
|
|
Einstellungen und Berechtigungen
|
|
Du kannst Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.
Du kannst Dateien in diesem Forum posten
Du kannst Dateien in diesem Forum herunterladen
|
|
Impressum
| Nutzungsbedingungen
| Datenschutz
| FAQ
|  RSS
Hosted by:
Copyright © 2007 - 2024
goMatlab.de | Dies ist keine offizielle Website der Firma The Mathworks
MATLAB, Simulink, Stateflow, Handle Graphics, Real-Time Workshop, SimBiology, SimHydraulics, SimEvents, and xPC TargetBox are registered trademarks and The MathWorks, the L-shaped membrane logo, and Embedded MATLAB are trademarks of The MathWorks, Inc.
|
|
