Symmetric Bipartite Matching der Elemente in Liste

Question

Beginnen Sie mit einer zufälligen Liste von ganzen Zahlen, sagen:

list = [2,5,7,1,3] 

Ziel: maximal jeden Eintrag in der Liste mit einem anderen Eintrag in der Liste paaren. Einträge von Werten (m, n) können angepasst werden, wenn log_base_2 ((m + n)/gcd (m, n)) NICHT eine ganze Zahl ist. I.e. (7,3) ist eine gültige Übereinstimmung, und (1,3) ist es nicht.

Ich bin mir ziemlich sicher, dass ein Weg, dies zu tun wäre, zwei Listen zu generieren, A und B, das entspricht die ursprüngliche Liste:

A=B=list=[2,5,7,1,3] 

Und dann behandelt es als ein zweiteiliges Matching Problem mit der zusätzliche Einschränkung, dass, wenn A [m] mit B [n] übereinstimmt, A [n] auch mit B [m] übereinstimmen muss (wiederum zusätzlich zu der obigen Übereinstimmungseinschränkung). Ich würde mir vorstellen, dass eine Visualisierung des resultierenden Flussnetzwerks horizontal symmetrisch wäre (d. H. Entlang der Source-Sink-Achse, daher der Titel).

Ich weiß, wie man ein bipartite Matching-Problem mit MaxFlow löst, kann aber nicht herausfinden, wie diese letzte, fett gedruckte Constraint implementiert wird. Jede Hilfe wäre sehr, äh, hilfreich.

Answer 1

Die zusätzliche Einschränkung (wenn A[m] Spiele B[n] dann muss A[n] auch B[m] entsprechen) ändert sich radikal die Art des Problems. Diese Einschränkung zerstört die Zweiteilung des Eingabediagramms und macht sie tatsächlich zu einem allgemeinen ungerichteten Graphen. Daher suchen Sie nach einem Algorithmus zum Finden einer maximalen Übereinstimmung in einem allgemeinen Diagramm.

Das Problem kann gelöst werden mit Edmonds Algorithm, die einen anderen Ansatz als die maximale Flusslösung für den zweiteiligen Fall zeigt (obwohl es den Begriff eines Augmentationspfad verwendet). Der Algorithmus nutzt die Tatsache, dass bipartite Matching einfach gelöst werden kann, und versucht in gewisser Weise, den Eingangsgraphen durch das Kollabieren von ungeraden Zyklen in zwei Teile zu verwandeln (ein Graph ist genau dann zweigeteilt, wenn er keine ungeraden Zyklen und somit die Zahl hat von ungeraden Zyklen in der Grafik misst das Ausmaß, zu dem der Eingabegraph weit davon entfernt ist, zweiteilig zu sein). Die Details, wie genau der Algorithmus funktioniert, sind im obigen Link gut erklärt.

Hier ist a Python implementation of the algorithm. Der Algorithmus ist für spärliche Graphen ziemlich effizient, für dichte Graphen jedoch nicht sehr effizient. Die Dichte Ihres Graphen hängt davon ab, wie viele Paare von Einträgen m, n die Bedingung (m + n)/gcd(m, n) erfüllen, die eine Potenz von 2 ist. Wenn die meisten Paare die Bedingung erfüllen, wird die Laufzeit ungefähr O(n^4) sein. Im Allgemeinen ist die Laufzeit O(E•V^2).

Answer 2

Es stellt sich heraus, dass es sich überhaupt nicht um ein bipartites Matching-Problem handelt - es ist vielmehr die allgemeinere Klasse der "Non-Bipartite Maximum Matching". Die Edmonds/'Blossom' algorithm bietet die Lösung (Snakile's answer pointed this out).

Nach einiger Suche um, fand ich eine einfache Implementierung des Edmonds/'Blossom' Algorithmus, die ich mit Liquidation: http://code.activestate.com/recipes/221251-maximum-cardinality-matching-in-general-graphs/

Es nutzt Guido van Rossum ist sehr intuitiv Graph Struktur: https://www.python.org/doc/essays/graphs/

Viel Glück für zukünftige Leser!