Zahlen eines Rechtecks aus Zahlen auswählen
Ich habe ein ziemlich großes Problem mit der Erfindung des Algorithmus.
Ich habe zwei Gruppen von Knoten. Sagen wir, wir haben 4 Knoten in der ersten Gruppe und weitere 4 Knoten in der zweiten. Die folgende Abbildung veranschaulicht dies:
Ich möchte Knoten aus der ersten Gruppe mit den Knoten aus der zweiten Gruppe verbinden. Sie müssen mit den besten Wegen verbunden sein. - Die Länge aller Routen muss so nah wie möglich sein und jeder Knoten darf nur mit einer Route verbunden sein. Etwas wie das:
Ich möchte es nicht wie im nächsten Bild machen, weil die Routen in Bezug auf die Länge sehr unterschiedlich sind.
Die folgende Tabelle zeigt die Längen zwischen allen Knoten. Und von dieser Tabelle möchte ich die beste Lösung wählen. Die beste Lösung ist eingekreist.
Und wie kann ich die beste Lösung finden, wenn ich Gruppen mit einhundert Knoten habe? Wenn ich jede Kombination versuche, wird es 100 geben! von Kombinationen, und das ist eine Menge. Ich kann dafür keinen Algorithmus erfinden.
3 Antworten
Wie Thomas @ in den Kommentaren gefragt hat, hängt die Lösung des Problems von Ihrer Definition von "so nah wie möglich" ab. Definieren wir die Kantenmenge in der Lösung als S . Unter der Annahme, dass die Definition so gewählt wurde, dass max(S) - min(S) minimiert wird (was in der Praxis eine vernünftige Annahme ist), kann dieses Problem definitiv in polynomieller Zeit gelöst werden.
Hier ist ein Beispiel für die Lösung. Für 100 Knoten dauert es nur Sekunden.
1
Zunächst müssen Sie das Problem der maximalen Übereinstimmung für zweiseitige Graphen kennen und dass es in polynomieller Zeit gelöst werden kann. Der einfachste Ungarische Algorithmus nimmt O(nm) , wobei n die Anzahl der Knoten und m ist die Anzahl der Kanten. Und für planare Graphen, die Ihr Fall ist, gibt es etwas mehr Algorithmen, die die Leistung weiter verbessern können .
Definieren wir dies als eine Funktion Max_Match(X) , die die maximale Anzahl an Übereinstimmungen in der Kantengruppe X zurückgibt.
Dieser Max_Match kann in weniger als O(n^1.5) berechnet werden, wobei n die Anzahl der Knoten ist. Für n=100 haben wir nur n^1.5 = 1000 .
2
Dann wandeln wir Ihr Problem in das Problem der maximalen Übereinstimmung um.
Definieren wir die Menge der Kanten E für alle Kanten, aus denen wir wählen können. In Ihrem Fall gibt es n*n Kanten in E , wobei n die Anzahl der Knoten auf einer Seite ist.
Definieren wir die Funktion
%Code%
Dies bedeutet die Teilmengenränder von F(E, low, high) = {e | e in E and |e| >= low and |e| <= high } , deren Längen zwischen E
Dann hat Ihr Problem für ein gegebenes Zahlenpaar [low, high] und low genau dann eine Lösung, wenn
high
3
Wie aber ermitteln wir den Wert von Max_Match( F (E, low, high)) == n und low ?
Die möglichen Werte von high und low sind alle möglichen Zahlen in high , die {|e|, e in E} Zahlen haben. Wenn Sie also alle möglichen Kombinationen von n^2 und low ausprobieren, kostet high . Das ist eine Menge.
Wenn wir n^4 bereits kennen, können wir low ohne Aufzählung herausfinden? Die Antwort ist positiv. Beachten Sie Folgendes:
Lemma 1
Wenn wir für eine Zahl high haben
h
Dann haben wir auch für jede Zahl Max_Match( F (E, low, h)) == n
h' >= h
Was das bedeutet ist, dass wir die binäre Suche verwenden können, um Max_Match( F (E, low, h')) == n herauszufinden, sobald wir high behoben haben.
4
Also der Rahmen der endgültigen Lösung:
%Vor% Und low ist der minimale Unterschied zwischen den Kanten in der Lösung. Dieser Algorithmus kostet ans , wobei O(n^3.5 * log(n)) die Anzahl der Knoten ist.
Edit: Eine einfache und hässliche Implementierung des obigen Algorithmus in C ++ finden Sie unter:
ideone.com/33n2Tg . Weil mir die Zeit fehlt, habe ich in dieser Lösung einen einfachen ungarischen Algorithmus erstellt, der langsam ist, wenn n groß ist. Um eine bessere Leistung zu erzielen, benötigen Sie den Algorithmus aus Teil 1 für planare Graphen.
Ich denke nicht, dass Sie das mit A * leicht berechnen können. Auch eine rohe Gewalt wäre O (n!). Ich denke, wir sollten Heuristiken wie den genetischen Algorithmus verwenden.
Sie können das Gen mit einem Array implementieren (Punkt A ist mit dem Wertpunkt B verbunden)
Dann müssen Sie einen Genpool mit zufälligen Genen erzeugen. Die Anzahl der Gene ist nicht fest ... also musst du ein bisschen herumprobieren.
Sie benötigen eine Berechnungsmethode:
%Vor%Dann brauchst du auch eine Fitness-Funktion:
%Vor%Sie müssen sie auch paaren:
%Vor%Der Crossbreed gibt uns ein paar Kinder zurück;) das muss den Fitnesstest bestehen. Außerdem sollten Sie eine Mutate-Methode implementieren, die uns ein mutiertes Gen gibt. Dies ist wichtig, um lokal maximal zu lassen.
Am Ende muss man nur noch eine Weile in einer Schleife laufen und man bekommt ein sehr gutes Ergebnis.
Angenommen, diese Tabelle enthält n Zeilen und m Spalten. Dieses Problem ist gleichbedeutend mit der Auswahl von n Zahlen, die sich in verschiedenen Zeilen und unterschiedlichen Spalten befinden, aus dieser Tabelle, so dass die Summe dieser Zahlen minimal ist. Wir können dfs verwenden, um alle Kombinationen in n zu finden! .aber für dieses Problem können wir einen A * Suchalgorithmus haben.
Für dieses Problem ist die heuristische Funktion h (x)
Die Komplexität dieses A * -Algorithmus ist schwer zu berechnen, aber es funktioniert häufig gut.
Tags und Links algorithm