Kapacitní minimální kostra - Capacitated minimum spanning tree

Kapacitní minimální kostra je minimální cena kostra a graf který má určený kořenový uzel ${displaystyle r}$ a splňuje kapacitní omezení ${displaystyle c}$. Omezení kapacity zajišťuje, že všechny podstromy (maximální podgrafy spojené s kořenem jednou hranou) dopadající na kořenový uzel ${displaystyle r}$ mít ne více než ${displaystyle c}$ uzly. Pokud mají uzly stromu váhy, pak lze omezení kapacity interpretovat takto: součet váh v jakémkoli podstromu by neměl být větší než ${displaystyle c}$. Hrany spojující podgrafy s kořenovým uzlem se nazývají brány. Nalezení optima řešení je NP-tvrdý.^[1]

Algoritmy

Předpokládejme, že máme graf ${displaystyle G = (V, E)}$, ${displaystyle n = | G |}$ s kořenem ${displaystyle rin G}$. Nechat ${displaystyle a_ {i}}$ být všechny ostatní uzly v ${displaystyle G}$. Nechat ${displaystyle c_ {ij}}$ být hraniční náklady mezi vrcholy ${displaystyle a_ {i}}$ a ${displaystyle a_ {j}}$ které tvoří nákladovou matici ${displaystyle C = {c_ {ij}}}$.

Ezau-Williamsova heuristika^[2]

Heuristika Esau-Williams najde suboptimální CMST, které jsou velmi blízké přesným řešením, ale v průměru EW produkuje lepší výsledky než mnoho jiných heuristik.

Zpočátku jsou všechny uzly připojeny k vykořenit ${displaystyle r}$ (hvězdný graf) a cena sítě je ${displaystyle displaystyle suma _ {i = 0} ^ {n} c_ {ri}}$; každá z těchto hran je brána. Při každé iteraci hledáme nejbližšího souseda ${displaystyle a_ {j}}$ pro každý uzel v ${displaystyle G- {r}}$ a vyhodnotit funkci kompromisu: ${displaystyle t (a_ {i}) = g_ {i} -c_ {ij}}$. Hledáme největší ${displaystyle t (a_ {i})}$ mezi pozitivními kompromisy a pokud výsledný podstrom neporuší omezení kapacity, odeberte bránu ${displaystyle g_ {i}}$ připojení ${displaystyle i}$-tý podstrom ${displaystyle a_ {j}}$ hranou ${displaystyle c_ {ij}}$. Opakujeme iterace, dokud nebudeme moci provést další vylepšení stromu.

Heuristika společnosti Esau-Williams pro výpočet neoptimálního CMST:

funkce CMST (C,C,r):    T = {${displaystyle c_ {1r}}$, ${displaystyle c_ {2r}}$, ..., ${displaystyle c_ {nr}}$}    zatímco mít změny: pro každého uzel ${displaystyle a_ {i}}$            ${displaystyle a_ {j}}$ = nejbližší uzel v jiném podstromu ${displaystyle t (a_ {i})}$ = ${displaystyle g_ {i}}$ - ${displaystyle c_ {ij}}$        t_max = max(${displaystyle t (a_ {i})}$)        k = i takhle ${displaystyle t (a_ {i})}$ = t_max -li ( náklady(i) + náklady(j) <= C)            T = T - ${displaystyle g_ {k}}$            T = T unie ${displaystyle c_ {kj}}$    vrátit se T

Je snadné vidět, že EW najde řešení v polynomiálním čase.

Sharma je heuristická

Sharma je heuristická.^[3]

Aplikace

Problém CMST je důležitý v designu sítě: když mnoho terminálu počítače musí být připojeny k centrálnímu rozbočovači, konfigurace hvězdy obvykle není návrhem minimálních nákladů. Hledání CMST, který organizuje terminály do podsítí, může snížit náklady na implementaci sítě.

Reference