Minimalizacja długości przewodów

Mój problem jest taki:

1. Mam fizyczny układ reprezentowany jako wykres. Węzły reprezentują haki / kanały, w których drut może się zakotwiczyć, a krawędzie są możliwym połączeniem między 2 węzłami, z których może przejść drut.

2. Istnieją specjalne Węzły, zwane rozdzielaczami, z których pojedynczy drut można podzielić na 2 lub więcej do k. Na razie można przyjąć stałą k, ale zmienia się ona w zależności od węzła. Nie wszystkie węzły są rozdzielaczami.

3. Jest jedno źródło energii, z którego wyłoni się drut. To jest źródło. Drut należy zabrać do n zlewów.

4. Krawędź może przenosić przez nią dowolną liczbę drutów w dowolnym kierunku.

5. Całkowita długość drutu musi zostać zminimalizowana.

6. Charakter wykresu, planarny lub euklidesowy nie jest znany.

Przykład : poniżej znajduje się przykładowa sieć. Węzły są nazywane liczbami, a krawędzie mają równe wagi 1. Źródło to Node1, a zlewy to Node5, Node9 i Node13. W przypadku, gdy 1 Node6 jest węzłem rozdzielającym. W przypadku, gdy 2 Node6 i Node4 są węzłami rozdzielającymi. K = 3 węzła splittera, tzn. Może on wziąć jeden drut i podzielić go na 3 druty.

Przypadek 1 . Tylko jeden węzeł rozdzielający. Rozsądne jest podzielenie w Node6.

Przypadek 2 . Węzeł z dwoma rozdzielaczami. Rozsądne jest dzielenie na Node4 zamiast na Node6.

Szukam różnych strategii, aby znaleźć ogólne rozwiązanie tego problemu. Przedstawiony tutaj wykres ma mniejszą skalę w porównaniu do aktualnego problemu. Wykres jest statyczny i nie można go zmienić (to znaczy, że rozwiązanie nie powinno sugerować żadnej nowej krawędzi ani proponować nowej lokalizacji rozdzielacza). Mile widziane są również wszelkie odniesienia do publikacji naukowych na ten temat.

Przypadek 3 . Węzeł z dwoma rozdzielaczami. Rozsądne jest dzielenie na Node4 i Node14. Pamiętaj, że w tym przypadku zmieniono grubości krawędzi dla Edge 8-12, 6-10 i 10-11. Ważną rzeczą w tym przypadku jest odzyskanie drutu po rozszczepieniu z Node14.

Ten problem jest trudny NP.

Załóżmy, że każdy wierzchołek jest rozdzielaczem, który może dzielić się na dowolną liczbę stopni, wtedy twoim problemem jest dokładnie problem drzewa Steinera na wykresie , gdzie zestaw wierzchołków źródłowych i opadających jest wymaganymi wierzchołkami.

$i$$k_i$

Uproszczenie polega na tym, że można wyeliminować wszystkie węzły pośrednie (kwadratowe). Utwórz wykres z samym węzłem źródłowym, węzłami ujścia i węzłami rozdzielającymi.

1. Na oryginalnym wykresie znajdź najkrótszą ścieżkę od węzła źródłowego do każdego węzła rozdzielającego i dodaj krawędź na nowym wykresie od węzła źródłowego do węzła rozdzielającego o tej długości.

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

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

$N$$i$$k_i$

$k_i$

@Chao Xu, znalazłem też, że Steiner jest najbliższym przybliżeniem mojego problemu. Badam systemy oparte na Ant, aby rozwiązać ten problem.