Czy drzewa cięte łączem są kiedykolwiek wykorzystywane w praktyce do obliczeń maksymalnego przepływu lub innych zastosowań?

20

Wiele algorytmów maksymalnego przepływu, które zwykle widzę zaimplementowanych, algorytm Dinica, push push i inne, mogą mieć asymptotyczny koszt czasu ulepszony dzięki zastosowaniu dynamicznych drzew (znanych również jako drzewa cięte łączem).

Wciśnij etykietę w trybie lub lub $O(V^2E)$ $O(V^3)$ normalnie, ale z dynamicznymi drzewami $O(V^2\sqrt{E})$ $O(VE \log(V^2/E))$
Algorytm Dinica działa w , ale z dynamicznymi drzewami $O(V^2E)$ $O(VE\log(V))$

Jednak praktyczne implementacje algorytmów maksymalnego przepływu w większości bibliotek wydają się nie wykorzystywać tej struktury danych. Czy drzewa dynamiczne były kiedykolwiek wykorzystywane w praktyce do obliczania maksymalnego przepływu? Czy też niosą ze sobą zbyt duży koszt, aby były przydatne w rzeczywistych rozmiarach problemów?

Czy istnieją inne domeny problematyczne, w których wykorzystywane są drzewa cięte łączem?

To pytanie jest związane z pytaniem, które zadałem na cstheory: Czy któryś z najnowszych algorytmów maksymalnego przepływu jest praktyczny?

— Rob Lachlan
źródło

przegląd / opis drzewa wyciętych linków, ale tylko stany „jest użyteczny w aplikacjach takich jak Network Flow”

— vzn

z ankiety tarjan cytowanej przez Reza, zasadniczo liniowe algorytmy czasowe działają bardzo dobrze / najlepiej dla umiarkowanej liczby wierzchołków / krawędzi, a następnie istnieje próg progowy większych wierzchołków / krawędzi, w których algorytmy logarytmiczne przewyższają algorytm liniowy. więc logarytmiczne fns dostępu są przydatne i mogą być znacznie lepsze w przypadku bardzo dużych wykresów.

— vzn

7

Istnieje artykuł zatytułowany „ Drzewa dynamiczne w praktyce ”, w którym dokonano przeglądu praktycznego wdrożenia.

Inne kategorie, w których drzewo Link-Cut można efektywnie wykorzystać, to Indeksowanie baz danych . Można to znaleźć w książce „ Techniki indeksu baz danych ”.

— Reza
źródło

myślę, że to wymaga nieco rozwinięcia. drzewa są oczywiście przydatne do indeksów, ale w jakich warunkach drzewo byłoby modyfikowane?

— vzn

@vzn: drzewo B +, drzewo R, drzewo H i drzewo X to tylko niektóre przykłady.

— Reza

oczywiście, ale podejrzewam, że do tej pory nikt nie próbował używać drzew wycinanych linkami w indeksach DB. jest to wiarygodna aplikacja, ale nie wydaje się jasne, że są zoptymalizowane pod kątem tych samych operacji, które występują w indeksach DB.

— vzn

5

ten dokument stwierdza na końcu, że drzewo z wycięciem łącza (LC) przewyższa drzewa rake-kompresji (RC) dla algorytmu maksymalnego przepływu Sleator / Tarjan przy użyciu standardowego generatora grafów losowych Dimacs.

artykuł koncentruje się na propagacji zmian jako jednej aplikacji dynamicznych drzew. np. propagacja zmian jest podobna do sposobu, w jaki komórki arkusza kalkulacyjnego programu Excel muszą być ponownie obliczane na podstawie zmian w niektórych komórkach na podstawie zależności między komórkami / formułami. autorzy opublikowali swój kod jako otwartą bibliotekę.

Eksperymentalna analiza propagacji zmian w dynamicznych drzewach Acar, Blelloch, Vittes

Propagacja zmian to technika automatycznego dostosowywania wyniku algorytmu do zmian na wejściu. Ideą propagacji zmian jest śledzenie zależności między wywołaniami danych i funkcji, aby w przypadku zmiany danych wejściowych funkcje, których dotyczy zmiana, mogły zostać ponownie uruchomione w celu zaktualizowania obliczeń i danych wyjściowych. Propagacja zmian umożliwia kompilatorowi dynamizowanie algorytmów statycznych.

— vzn
źródło

Dziękuję Ci. Miło jest zobaczyć niektóre testy porównawcze algorytmów z udziałem dynamicznych drzew.

— Rob Lachlan