Kombination aus gegebenen Elementvektoren

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.