Ich habe ein zweiteiliges Diagramm, wo jeder Knoten Verbindungen (Kanten) verschiedener Längen zu den Knoten in der anderen Partition hat. Ich möchte Kanten so auswählen, dass die Summe der Längen so klein wie möglich ist, aber abhängig von der Einschränkung, dass jeder Knoten eine und nur eine ausgewählte Kante haben sollte (wenn die Anzahl der Knoten in den zwei Partitionen gleich ist - wenn nicht, ein oder mehrere Knoten haben keine ausgewählte Kante).Bipartite Grafik, kürzeste Verbindung?
Ich möchte dieses Matching so schnell wie möglich finden, aber bis jetzt habe ich nur den Brute-Force-Ansatz gefunden, jede Möglichkeit auszuprobieren, die mir einen O (n!) -Algorithmus gibt - was undurchführbar ist. Hat jemand einen Vorschlag für einen besseren Ansatz?
Mein konkretes Problem ist das Folgende: Ich habe mehr oder weniger zufällig bewegte 3D-Partikel in zwei verschiedenen Zeitpunkten beobachtet. Ich möchte wissen, wo sich jedes Teilchen bewegt hat, d. H. Jedes Teilchen verfolgen, unter der Annahme, dass ihre Gesamtbewegung so kurz wie möglich ist.
Die genaue Antwort wäre derjenige von @tjhighley vorgeschlagen werden. Wenn Sie mit einem "gut genug" -Algorithmus leben können, könnten Sie mit einem naiven Matching beginnen und ihn dann an [* annealing *] (https://en.wikipedia.org/wiki/Simulated_annealing) weiterleiten. –