Minimierung der Verdrahtungslänge

Mein Problem ist wie folgt:

1. Ich habe ein physisches Layout als Grafik dargestellt. Die Knoten stellen Haken / Kanäle dar, an denen ein Draht verankert werden kann, und Kanten sind die mögliche Verbindung zwischen zwei Knoten, von denen aus der Draht verlaufen kann.

2. Es gibt einige spezielle Knoten, sogenannte Splitter, von denen aus ein einzelner Draht auf 2 oder mehr bis zu k geteilt werden kann. Das k kann vorerst konstant genommen werden, variiert jedoch von Knoten zu Knoten. Nicht alle Knoten sind Splitter.

3. Es gibt eine Stromquelle, aus der ein Draht austritt. Es ist die Quelle. Der Draht muss zu n Waschbecken gebracht werden.

4. Eine Kante kann eine beliebige Anzahl von Drähten aufnehmen, die in beide Richtungen durch sie verlaufen.

5. Die Gesamtdrahtlänge muss minimiert werden.

6. Die Art des Graphen, des Planars oder des Euklidischen ist nicht bekannt.

Beispiel : Unten sehen Sie ein Beispielnetzwerk. Knoten werden als Zahlen benannt und Kanten werden mit der gleichen Gewichtung von 1 versehen. Quelle ist Knoten1 und Senken sind Knoten5, Knoten9 und Knoten13. Im Fall 1 ist Knoten6 Splitter-Knoten. In Fall 2 sind Knoten6 und Knoten4 Teilungsknoten. K = 3 des Splitterknotens, dh er kann einen Draht aufnehmen und in 3 Drähte aufteilen.

Fall 1 . Nur ein Splitterknoten. Es ist sinnvoll, sich bei Node6 zu trennen.

Fall 2 . Zwei-Splitter-Knoten. Es ist sinnvoll, bei Node4 anstelle von Node6 zu teilen.

Ich suche nach verschiedenen Strategien, um eine generische Lösung für dieses Problem zu finden. Die hier dargestellte Grafik ist im Vergleich zum vorliegenden Problem kleiner. Das Diagramm ist statisch und kann nicht geändert werden (ich meine, die Lösung sollte keine neue Kante oder neue Splitter-Position vorschlagen). Jeder Verweis auf ein Forschungspapier, das zu dieser Art von Problem veröffentlicht wurde, ist ebenfalls zu begrüßen.

Fall 3 . Zwei-Splitter-Knoten. Es ist sinnvoll, bei Node4 und Node14 zu teilen. Beachten Sie, dass in diesem Fall die Kantengewichte für die Kanten 8-12, 6-10 und 10-11 geändert wurden. In diesem Fall ist es wichtig, einen Draht zurückzuverfolgen, nachdem er von Knoten 14 getrennt wurde.

Dieses Problem ist NP-schwer.

Angenommen, jeder Scheitelpunkt ist ein Splitter, der bis zu einer beliebigen Anzahl von Graden geteilt werden kann. Dann ist Ihr Problem genau das Steiner-Baumproblem in einem Diagramm , bei dem die Menge der Quell- und Senkenscheitelpunkte die erforderlichen Scheitelpunkte sind.

$i$$k_i$

Die Vereinfachung besteht darin, dass Sie alle Zwischenknoten (quadratischen Knoten) entfernen können. Erstellen Sie ein Diagramm nur mit dem Quellknoten, den Senkenknoten und den Splitterknoten.

1. Suchen Sie in Ihrem ursprünglichen Diagramm den kürzesten Pfad vom Quellknoten zu jedem Splitterknoten und fügen Sie im neuen Diagramm eine Kante vom Quellknoten zum Splitterknoten mit dieser Länge hinzu.

2. $i$$j$$i$$j$$i$$j$

3. $i$$j$$i$$j$$i$$j$

$N$$i$$k_i$

$k_i$

@Chao Xu, ich fand auch, dass Steiner meinem Problem am nächsten kommt. Ich erforsche Ant-basierte Systeme, um dieses Problem zu lösen.