Vertex-Coloring/Assignment um die Anzahl der "Farbkreuzungen" zu minimieren

Question

Ich bin mir nicht sicher, ob dies wirklich ein "Farbgebungsproblem" ist, genauso wie es ein Aufgaben-/Linearprogrammierungsproblem ist. Ich habe keine Expertise in beiden, also verzeihen Sie keine Noob-Ness, die folgen könnte. Aber ich habe das Gefühl, dass dieses Problem fast definitiv gelöst/untersucht worden sein muss, ich konnte einfach nichts finden, nachdem ich viele der Graphalgorithmen auf http://en.wikipedia.org/wiki/Category:Graph_algorithms durchgesehen habe. Ich hatte gehofft, ein paar Hinweise in die richtige Richtung zu bekommen.

Die „Problem-Anweisung“ kocht effektiv nach unten zu:

1. Es gibt zwei Arten von Eckpunkten in der Grafik: Router und Kern.

2. Kerne sind NUR mit Routern verbunden. Jeder Kern ist nur mit einem einzelnen Router verbunden. Und jede hat eine vom Benutzer eingegebene/definierte "Farbe". (Bei meinem speziellen Problem ist die Farbe auf eine von etwa 4/5 möglichen Farben beschränkt). Ihre Farbe kann nicht geändert werden, es ist ein Eingabeparameter. (Kerne sind die Quadrate in der Abbildung unten)

3. Router sind mit Kernen sowie anderen Routern verbunden. Sie haben keine "Farbe" zugewiesen. Das Zuweisen einer Farbe ist Teil des Ziels des Programms/Algorithmus. (Router sind die kreisförmigen Scheitelpunkte im Bild unten.)

4. Ziel des Programms ist es, jedem Router im Graphen Farben zuzuweisen, so dass die Anzahl der "Übergänge"/Kanten zwischen den Scheitelpunkten einer anderen Farbe minimiert wird .

(Eine alternative Sicht. Im Wesentlichen Sie ein Diagramm gegeben, wo einige Eckpunkte sind gefärbt, andere sind nicht Ziel ist es, diejenigen zu färben, die nicht so sind, dass die Anzahl der Kanten zwischen den Scheitelpunkten unterschiedlicher Farbe ist minimiert.)

Ich konnte dies (ich bin mir ziemlich schlecht) als ein Integer-Linear-Programm formulieren und habe eine Lösung/Ansatz mit LP-Solve erstellt. Ich habe auch eine eigene Heuristik. Ich würde gerne die "richtigen"/bekannten/anderen Lösungsansätze kennenlernen ?!

Vielen Dank!

Answer 1

Wenn die Anzahl der Farben < = 5 und Router < = 10, dann können Sie rohe Gewalt verwenden.

Es gibt viel weniger als 5^10 Optionen, besonders wenn Sie standardmäßig jeden Router mit der gebräuchlichsten Farbe versehen und dann nur die Farbe einiger von ihnen ändern, Backtracking wo nötig.

Edit: Es gibt auch einen schönen Hamilton-Pfad-Algorithmus, den Sie vielleicht an Ihre Bedürfnisse anpassen können, vorausgesetzt, es gibt weniger als 15 Router. What is the dynamic programming algorithm for finding a Hamiltonian cycle in a graph?

Answer 2

Beginnen wir mit dem Fall mit zwei Farben. Wir können dies in eine Instanz von s-tmin cut umwandeln. Die Idee ist, dass wir einen s Knoten und einen t Knoten in einem Graphen bezeichnet haben, und dass wir die verbleibenden Knoten in entweder die s Gruppe oder der t Gruppe, so dass die Summe der geteilt werden soll die Kantengewichte zwischen den zwei Gruppen sind minimiert.Für Ihre Version haben wir einen gelben Masterknoten s und roten Masterknoten t, und wir platzieren eine hoch gewichtete Kante, die die Anzahl aller Kanten in Ihrem ursprünglichen Graphen zwischen jedem der Kerne und dem entsprechenden Hauptfarbknoten überschreitet. mit allen ursprünglichen Kanten intakt mit jeweils 1 Gewicht. Die hohen Kosten-Kanten stellen sicher, dass wir niemals irgendeinen der Kerne illegal neu einfärben werden, da es billiger ist, alle Router zu bewegen. Dieses Problem kann in polynomieller Zeit unter Verwendung standard max flow algorithms über die Max flow-Min cut theorem gelöst werden. Die beste Wahl hängt von Ihrer Kanten- und Eckenzahl ab.

Im Fall von mehreren Farben versuchen Sie, das "Multiterminal-Schnitt" -Problem zu lösen. Dies steht in Zusammenhang mit dem minimum k-cut Problem, aber die Standardreferenz für dieses Problem ist das Papier The Complexity of Multiterminal Cuts (welches der k -cut Artikel indirekt verbindet). Bei mehr als 2 Farben ist das Problem, wenn der Graph planar ist, scheinbar immer noch in polynomieller Zeit lösbar; Ansonsten ist es NP-hard, also können Sie auch Ihren Integer-Programmierungslöser verwenden, da dies ein weiteres NP-schweres Problem ist.