Minimalne drzewo opinające z podwójnymi parametrami wagi

Rozważmy wykres . Każda krawędź ma dwa obciążniki i . Znajdź drzewo które minimalizuje produkt . Algorytm powinien działać w czasie wielomianowym w odniesieniu do. $G(V,E)$ $e$ $A_e$ $B_e$ $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$ $|V|, |E|$

Trudno mi dostosować dowolny tradycyjny algorytm na drzewach opinających (Kruskal, Prim, Usuwanie krawędzi). Jak to rozwiązać? Jakieś wskazówki?

algorithms graph-theory spanning-trees

— Strin
źródło

Może spróbuj zbudować nowy wykres, w którym waga krawędzi wynosi .

e

$e$

max (A_{e}, B_{e})

$\max(A_e,B_e)$

— utdiscant

Czy to jest zadanie domowe / ćwiczenie? Jeśli tak, to czy pochodzi z podręcznika? Pytam o to, że kontekst może pomóc w „inżynierii wstecznej” problemu. Nie jest od razu oczywiste, że chciwy algorytm jest tutaj odpowiedni, ale jeśli pochodzi on z rozdziału o algorytmach zachłannych ...

— Joe

@utdiscant, to nie zadziała. Przydatne mogą być krawędzie ujemne.

— Nicholas Mancuso

nawet dla dodatnich krawędzi nie jest przydatna, np. para (10,10) nie jest lepsza niż para (11,1) w większości przypadków.

Odpowiedzi:

Zakładam, że nie masz ujemnie ważonych krawędzi, ponieważ może to nie działać, jeśli występują ujemne wagi.

Algorytm

Dla każdej krawędzi oznacz je od do $1$ $n$

Niech waży A numeru krawędzi $a_i$ $i$

Niech waga B numeru krawędzi $b_i$ $i$

Przygotuj ten stół

   |a_1 a_2 a_3 a_4 .. a_n
---+-------------------------
b_1|.........................
b_2|.........................
 . |.........................
 . |.........................
b_n|...................a_n * b_n

Każdy element tabeli jest iloczynem wiersza i kolumny.

Dla każdej krawędzi zsumuj odpowiedni wiersz tabeli i kolumnę (pamiętaj o usunięciu elementu w przecięciu, ponieważ został on zsumowany dwukrotnie).

Znajdź krawędź, która ma największą sumę, usuń ją, jeśli nie rozłączy wykresu. W przeciwnym razie zaznacz krawędź jako niezbędną. Jeśli krawędź została usunięta, wypełnij jej wiersze i kolumny wartością 0.

Poprawność

Rezultatem jest oczywiście drzewo.

Wynik jest oczywiście szeroki, ponieważ żadne wierzchołki nie są odłączone.

Wynik jest minimalny? Jeśli istnieje inna krawędź, której usunięcie spowoduje utworzenie mniejszego drzewa opinającego na końcu algorytmu, wówczas krawędź ta zostałaby najpierw usunięta i unieważniona. (gdyby ktoś pomógł mi uczynić to nieco bardziej rygorystycznym / i / lub kontrprzykładowym, byłoby świetnie)

Środowisko wykonawcze

Oczywiście wielomian w. $|V|$

edytować

$(2,11), (11,2), (4,6)$ jest nie przykładem licznika.

$a_1 = 2, a_2 = 11, a_3 = 4$

$b_1 = 11, b_2 = 2, b_3 = 6$

Następnie

   | 2     11     4
---+--------------------
11 | 22    121    44
 2 | 4     22     8
 6 | 12    66     24

\begin{aligned} (4, 6) & = 44 + 8 + 24 + 66 + 12 = 154 \\ (2, 11) & = 22 + 4 + 12 + 121 + 44 = 203 \\ (11, 2) & = 121 + 22 + 66 + 4 + 8 = 221 \end{aligned}

$\begin{align*} (4,6) &= 44 + 8 + 24 + 66 + 12 = 154 \\ (2,11) &= 22 + 4 + 12 + 121 + 44 = 203 \\ (11,2) &= 121 + 22 + 66 + 4 + 8 = 221 \end{align*}$

$(11,2)$ zostaje usunięty.

Skończ z $(2,11), (4,6) = 6 * 17 = 102$

Inne drzewa rozpinające są

$(11,2), (4,6) = 15 * 12 = 180$

$(2,11), (11,2) = 13 * 13 = 169$

— Herp Derpington
źródło

Wydaje mi się, że jest to raczej chciwe podejście. Nie przekonuje mnie twój „dowód” na minimalizm.

— Nejc

@SaeedAmiri Jak to jest kontrprzykład? Umieściłem pracę w edytowanej sekcji, algorytm daje poprawny wynik.

— Herp Derpington

To, co zrobiłeś, to ustalenie, ile każdy wnosi w , a ty wybierasz te, które mają największy wpływ. To dobrze, ale nie jest to wymagane. To trudne pytanie. Jeśli chcesz poprawić swoją odpowiedź, musisz przedstawić dowód. W przeciwnym razie nie ma sensu.

(a_{i}, b_{i})

$(a _i, b _i)$

\sum_{e \in E} a_{i} . \sum_{e \in E} b_{i}

$\sum _{e \in E} a _i. \sum _{e \in E} b _i$

— AJed

bardzo niesprawiedliwe jest jednak głosowanie w dół za twój wysiłek.

— AJed

@AJed Dowód jest taki sam jak w przypadku prim / kush / reverse delete. Wszystko, co musimy teraz udowodnić, to to, że wycięta nieruchomość nadal obowiązuje.

— Herp Derpington

To jest rozwiązanie z http://www.cnblogs.com/autsky-jadek/p/3959446.html .

Możemy zobaczyć każde drzewo opinające jako punkt na płaszczyźnie , gdzie jest sumą masy , y jest sumą wagi . Celem jest zminimalizowanie . $x-y$ $x$ $\sum_{e\in T}A_{e}$ $\sum_{e\in T}B_{e}$ $xy$

Znajdź minimalne drzewo rozpinające według wagi i waga . Tak więc mamy dwa punkty w płaszczyźnie xy . We wszystkich punktach drzewa rozpinającego w płaszczyźnie ma minimum , ma minimum . $A$ $B$ $A,B$ $A$ $x$ $B$ $y$
Teraz staramy się znaleźć punkt w trójkącie który ma maksymalną odległość do linii , abyśmy mogli zminimalizować wartość dla dla wszystkich punktów w trójkącie . $C$ $OAB$ $AB$ $xy$ $C$ $ABC$

Ponieważ . $2S_{ABC}=|\overrightarrow{AB}\times\overrightarrow{AC}|=(B_{x}-A_{x},B_{y}-A_{y})\times(C_{x}-A_{x},C_{y}-A_{y})=(B_{x}-A_{x})\cdot C_{y}+(A_{y}-B_{y})\cdot C_{x}-A_{y}(B_{x}-A_{x})+A_{x}(B{}_{y}-A_{y})$

Zauważ, że jest stałą, więc teraz dążymy do maksymalizacji . Więc tworzymy nowy wykres , podczas gdy waga . Teraz uruchamiamy maksymalne drzewo rozpinające na do uzyskania punktu . $A_{y}(B_{x}-A_{x})+A_{x}(B{}_{y}-A_{y}$ $(B_{x}-A_{x})\cdot C_{y}+(A_{y}-B_{y})\cdot C_{x}$ $G^{\prime}=(V,E)$ $w(e)=B_{e}(B_{x}-A_{x})+C_{x}(A_{y}-B_{y})$ $G^{\prime}$ $C$
Uruchom powyższy algorytm na rekurencyjnie, aż nie ma więcej drzew obejmujące między i . $OBC, OAC$ $BC,AC$ $O$
Teraz otrzymujemy zestaw możliwych drzew spinających. Oblicz wartość dla każdego drzewa, aby uzyskać minimalne drzewo. $xy$