Kombination aus gegebenen Elementvektoren

[Bashar]

Wenn ich nicht irgendwas übersehe ist das das Maximum Bipartite Matching Problem. Es sei denn dein Beispiel ist blöd gewählt und die Vi können auch Elemente mehrfach enthalten.

[Nexus]

Danke vielmals für die Antworten.

rapso schrieb:

du willst also anhand der einzelnen vektoren die menge rausfinden aus der sie bestehen?

Nein, ich will aus jedem Vektor ein Element nehmen, sodass schliesslich jedes Element genau einmal in X vorkommt. Die Menge Q ist auch gegeben. Sorry für die etwas unklare Beschreibung

Bashar schrieb:

Wenn ich nicht irgendwas übersehe ist das das Maximum Bipartite Matching Problem. Es sei denn dein Beispiel ist blöd gewählt und die Vi können auch Elemente mehrfach enthalten.

Danke für den Begriff, werde ich mir genauer anschauen. Nein, die Vi können Elemente nicht mehrfach enthalten.

Momentan hätte ich eigentlich auch von Mengen Vi sprechen können, aber möglicherweise wird später die Reihenfolge der Elemente relevant, deshalb Vektoren (oder n-Tupel). Falls jemandem zum Spezialfall mit Beachtung der Reihenfolge gerade etwas einfällt, kann er es gerne sagen.

[Michael E.]

Nexus schrieb:

Nein, ich will aus jedem Vektor ein Element nehmen, sodass schliesslich jedes Element genau einmal in X vorkommt. Die Menge Q ist auch gegeben. Sorry für die etwas unklare Beschreibung

Sprich: Du willst eine Permutation von Q, sodass das i-te Element im i-ten Vektor vorkommt.

Falls jemandem zum Spezialfall mit Beachtung der Reihenfolge gerade etwas einfällt, kann er es gerne sagen.

Welche Rolle spielt denn die Reihenfolge? Willst du Lösungen bevorzugen, bei denen die Elemente "weiter vorne" in den Vektoren stehen? Wenn ja, wie sieht deine Metrik genau aus?

[Nexus]

Michael E. schrieb:

Sprich: Du willst eine Permutation von Q, sodass das i-te Element im i-ten Vektor vorkommt.

Permutation ist richtig, aber welches Element wo vorkommt, ist zunächst (ohne Beachtung der Reihenfolge) egal.

Michael E. schrieb:

Welche Rolle spielt denn die Reihenfolge? Willst du Lösungen bevorzugen, bei denen die Elemente "weiter vorne" in den Vektoren stehen? Wenn ja, wie sieht deine Metrik genau aus?

Die Vektorkomponenten sind Indizes für andere Punkte in einem 2D-Raum. Je weiter hinten in einem Vektor, desto grösser die Distanz zum entsprechenden Punkt. Darum möchte ich tendenziell Punkte am Anfang (mit kürzerer Distanz) bevorzugen.

[Michael E.]

Nexus schrieb:

Michael E. schrieb:

Sprich: Du willst eine Permutation von Q, sodass das i-te Element im i-ten Vektor vorkommt.

Permutation ist richtig, aber welches Element wo vorkommt, ist zunächst (ohne Beachtung der Reihenfolge) egal.

Du hast doch selbst geschrieben, dass das i-te Element im i-ten Vektor vorkommen soll

Die Vektorkomponenten sind Indizes für andere Punkte in einem 2D-Raum. Je weiter hinten in einem Vektor, desto grösser die Distanz zum entsprechenden Punkt. Darum möchte ich tendenziell Punkte am Anfang (mit kürzerer Distanz) bevorzugen.

Willst du also sowas wie Abstandssumme minimieren? Dann kannst du dein Problem als Minimum-Cost-Flow-Instanz modellieren: Nimm für jedes Element aus Q und für jeden Vektor Vi einen Knoten. Für erstere setzt du b(x) = 1, für letztere b(x) = -1 (aus jedem Q-Knoten soll Fluss rausfließen, in jeden Vi-Knoten soll Fluss hineinfließen). Füge Knoten von x nach Vi ein für alle x, die in Vi vorkommen. Setze alle Kantenkapazitäten auf 1. Setze die Kosten einer Kante (x, Vi) auf den Abstand, den x hat. Ein Min-Cost-Flow-Algorithmus wird dir nun eine zulässige Lösung (d.h. ein maximales Matching) liefern, dessen Kosten minimal sind (d.h. die Abstandssumme ist minimal). In der Praxis zu empfehlen sind z.B. der Netzwerksimplex und der Sukzessive-kürzeste-Wege-Algorithmus.

Edit: Wahrscheinlich gibt es sogar noch einfachere Algorithmen für das Maximum Weighted Matching Problem. Die kenn ich aber nicht. Hier würdest du den Graphen genauso modellieren, nur die b-Werte und Kantenkapazitäten fallen weg.

[Nexus]

Michael E. schrieb:

Du hast doch selbst geschrieben, dass das i-te Element im i-ten Vektor vorkommen soll

Ah, du meinst i-tes Element von X, nicht von Q. Ja, das stimmt so.

Michael E. schrieb:

Willst du also sowas wie Abstandssumme minimieren?

Vor allem das Abstandsmaximum. Vielen Dank für den Hinweis auf die Graphen (auch Bashar), spontan hätte ich das Problem nicht so modelliert.

[rapso]

jetzt hab ich es endlich auch gepeilt
schaut wie ein TSP aus, wobei du nicht den kuerzesten, sondern ueberhaupt einen pfad finden moechtest. (oder man nimmt es als assymetrisches TSP mit verbindungen die unendlich gewichtet sind oder 0).

wenn wenigstens anfang und end element bekannt waere, waere es extrem einfach, aber so hab ich keine gute idee.

[Michael E.]

rapso schrieb:

schaut wie ein TSP aus

Wie passt das TSP hierzu? (Abgesehen davon, dass man beim TSP auch Permutationen berechnet. Du machst das Problem aber viel schwerer.)

wobei du nicht den kuerzesten, sondern ueberhaupt einen pfad finden moechtest.

Das wäre das Hamiltonkreisproblem und nicht das TSP. Abgesehen davon wurden schon polynomielle Ansätze genannt.

wenn wenigstens anfang und end element bekannt waere, waere es extrem einfach

Wie das?

[Nexus]

Inzwischen habe ich mich ein wenig in Boost.Graph eingelesen. Scheint noch mächtig zu sein, aber aufgrund der extremen Generizität und der Dokumentation (z.B. Property-Maps) ist der Einstieg nicht ganz einfach...

Jedenfalls habe ich das Problem als bipartiten Graphen mit Knoten {a, b, c, d, e, V1, V2, V3, V4, V5} modelliert. Zwischen a und V1 besteht eine Kante, wenn a in V1 vorkommt.

Dafür habe ich nun den Algorithmus boost::edmonds_maximum_cardinality_matching() verwendet, was soweit gut funktioniert. Nun möchte ich aber nicht irgendein Matching, sondern wenn möglich eines mit der kleinsten Abstandssumme (wenn Kanten mit Distanzen gewichtet werden). Wisst ihr, ob der Algorithmus sowas bereits vorsieht?

Ansonsten sähe ich noch die Möglichkeit, das Matchingproblem als Flussnetzwerk mit zusätzlichen Knoten für Quelle und Senke zu modellieren und sowas wie boost::edmonds_karp_max_flow() einzusetzen... Habt ihr Ideen oder Tipps?

[Nexus]

Ideen? Hättet ihr überhaupt Boost.Graph verwendet, oder selbst etwas programmiert? Oder vielleicht eine andere Bibliothek?

[otze]

Du möchtest du Ungarischen Algorithmus, bzw eine weiterentwicklung davon. Der macht bipartit minimum cost matching.

[Jester]

Da ist boost leider nicht besonders gut bestückt. Ich würde Dir empfehlen eine andere Library zu benutzen. Wir haben mit LEMON ganz gute Erfahrungen gemacht: http://lemon.cs.elte.hu/trac/lemon

Da sind insbesondere diverse allgemeine Matching-Algorithmen implementiert: http://lemon.cs.elte.hu/pub/doc/latest/a00555.html
Entsprechende MinCostFlow-Algorithmen, falls Du direkt mit bipartitem Matching arbeiten möchtest sind auch vorhanden.

[Nexus]

Vielen Dank für die Stichworte!

LEMON scheint auch eine vernünftige Dokumentation zu haben und nicht wie Boost.Graph total über-abstrahiert zu sein. Denn gerade die Kombination aus eher minimalistischer Dokumentation und lauter impliziter Template-Konzepte macht einen Einstieg relativ schwierig...

Schade, dass die Bibliothek keinen A*-Algorithmus anbietet. Allerdings habe ich das gefunden...

[Jester]

Das ist halt der Unterschied zwischen einer Library, die von einem Algorithmiker entworfen und implementiert wird und einer, die von Softwaretechnikern entworfen wird. letztere bauen tolle, generische Interfaces und benutzen tolle Programmiertechniken, haben aber leider oft keinen Plan, was man damit wirklich machen will...

[Nexus]

LEMON ist wirklich nett, danke nochmals für den Tipp. Auch das API ist sehr sauber (nur die implizit dereferenzierbaren Iteratoren sind etwas speziell), dagegen ist Boost die reine Hölle. Die LEMON-Bibliothek kann ich nur weiterempfehlen

Bipartite Graphen und entsprechende Matching-Algorithmen sind allerdings noch nicht Teil der offiziellen Bibliothek, darum habe ich einen Fork lemon-bipartite benutzt, so kann ich das Matching-Problem direkt lösen. Mit den Klassen ListBpGraph und MaxWeightedBpMatching funktioniert bisher alles perfekt.