Pozytywne uporządkowanie topologiczne

45

Załóżmy, że mam ukierunkowany wykres acykliczny z wagami liczb rzeczywistych na jego wierzchołkach. Chcę znaleźć uporządkowanie topologiczne DAG, w którym dla każdego prefiksu uporządkowania topologicznego suma wag jest nieujemna. Lub jeśli wolisz terminologię teoretyczną, mam ważoną częściową kolejność i chcę liniowego rozszerzenia, aby każdy prefiks miał nieujemną wagę. Co wiadomo na temat tego problemu? Czy jest to NP-kompletne czy możliwe do rozwiązania w czasie wielomianowym?

ds.algorithms directed-acyclic-graph partial-order David Eppstein
źródło

4

Wypróbuj algorytm zachłanny na tym wykresie: 1 -> 2 -> 3, 1 -> 4 -> 5, wagi wierzchołków wynoszą 1: +2, 2: -2, 3: +3, 4: -1 , 5: -2. Chciwy algorytm zaczynałby się od v1, następnie wybrał v4, a następnie utknął. Prawidłowa kolejność to v1, v2, v3, v4, v5.

Robin Kothari,

2

„niektóre z problemów z odległością Frecheta, na które patrzyli JeffE i inni” - Ładna abstrakcja! Dla innych korzyści, oto jedna wersja: Załóżmy, że otrzymałeś ważony na krawędzi wykres płaszczyzny G oraz dwa wierzchołki si powierzchni zewnętrznej. Chcesz przekształcić jedną ścieżkę graniczną od s do t w drugą za pomocą sekwencji elementarnych ruchów. Każdy ruch zastępuje bieżącą ścieżkę różnicą symetryczną z pewną granicą twarzy. Jak szybko możemy znaleźć sekwencję mve, która minimalizuje maksymalną długość ewoluującej ścieżki?

Jeffε

3

Tsuyoshi, przepraszam za to, próbowałem dodać nowy wiersz podczas komentowania, co spowodowało odcięcie mojego komentarza. Chodzi o to, że masz sznur ściśle związany z nadgarstkiem i chcesz wiedzieć, czy możesz go zwinąć. Twój nadgarstek jest reprezentowany jako wieloboczna siatka, której komórki są elementami częściowego rzędu (bliżej sznurka wcześniej, bliżej do później w kolejności). Ciężar komórki to różnica długości między jej wewnętrznymi i zewnętrznymi granicami.

David Eppstein,

1

@David: Dzięki za wyjaśnienie. Tym razem rozumiem, w jaki sposób ma to związek z bieżącym pytaniem i jest interesujące!

Tsuyoshi Ito,

3

Niezbyt przydatne, ale zabawne spostrzeżenie: ten problem jest równoważny problemowi sekwencjonowania na jednej maszynie z terminami i ograniczeniami pierwszeństwa, w których czas przetwarzania każdego zadania może być ujemny . Przy nieujemnym czasie przetwarzania problem występuje w P (Lawler and Mooer 1969 jstor.org/stable/2628367 ), a jeśli istnieje rozwiązanie, wówczas istnieje rozwiązanie niezależne od czasu przetwarzania. To wyraźnie psuje się, jeśli niektóre zadania mają negatywny czas przetwarzania.

Tsuyoshi Ito,

18

Ten problem wydaje się bardzo podobny do SEKWENCJONOWANIA W CELU ZMINIMALIZOWANIA MAKSYMALNEGO KOSZTU SKUMULOWANEGO, problem [SS7] w Garey & Johnson . To znaczy:

$T$ $\prec$ $T$ $c(t) \in Z$ $t \in T$ $c(t) < 0$ $K \in Z$

$\sigma$ $T$ $t \in T$ $t'$ $\sigma(t') \leq \sigma(t)$ $K$

$K$ $c(t) \in \{-1,0,1\}$ $t \in T$

mum
źródło

7

K = 0

$K=0$

c

$c$

- K

$-K$

K

$K$

c

$c$

- 1

$-1$

@mhum: Pracuję nad raportem technicznym na temat powiązanych wyników i chciałbym cię zacytować. Czy dałbyś mi swoje prawdziwe imię? Jeśli chcesz, możesz wysłać mi wiadomość e-mail lub pozostać anon ...

domotorp

9

Cóż, moją odpowiedzią jest moje pytanie, z którego okazuje się, że jeśli możesz rozwiązać ten problem w P, możesz również rozwiązać inny otwarty problem: Pozytywne uporządkowanie topologiczne, weź 3

Edycja: Ten problem również okazał się NP-zupełny, więc twój problem jest już NP-zupełny, jeśli twój DAG ma tylko dwa poziomy, tj. Jeśli nie ma ukierunkowanych ścieżek z dwiema krawędziami.

domotorp
źródło

3

Jeśli dobrze rozumiem problem, myślę, że problem związany z pierwszeństwem ograniczenia planowania pojedynczej maszyny w celu zminimalizowania ważonej sumy czasów ukończenia (1 | prec | \ sum wc) może zostać zredukowany do problemu, który Cię interesuje. W problemie 1 | prec | \ sum wc mamy n zadań, każde o nieujemnej wadze i czasie przetwarzania, poset na zadaniach i chcemy liniowego rozszerzenia zadań tak, aby suma ważonych czasów wykonania zadań wynosiła zminimalizowane. Problemy są zakończone NP, mimo że zakładamy, że czas przetwarzania każdego zadania jest równy 1. Czy ma to jakiś sens?

monaldo
źródło

To zdecydowanie interesująca możliwość. Ale w jaki sposób dokonuje się redukcji w taki sposób, że kryterium optymalizacji (minimalizacja sumy czasów ukończenia) przekształca się w ograniczenia (przedrostki nieujemne)?

David Eppstein,

Nie znam tego wyniku NP wynikającego z problemu szeregowania, ale myślę, że odnosi się on do problemu decyzyjnego dotyczącego decyzji, czy istnieje liniowe rozszerzenie, że ważona suma czasów ukończenia zadania wynosi co najwyżej K, dlatego nie sądzę ważne jest tutaj rozróżnienie między kryterium optymalizacji a ograniczeniem. Jednak nie zrozumiałem, jak przedstawić ograniczenie ważonej sumy czasów ukończenia w bieżącym problemie.

Tsuyoshi Ito,

Myślę, że redukcja nie jest tak łatwa, jak myślałem na początku. Nie jestem już pewien mojej odpowiedzi.

monaldo,

Właśnie zauważyłem błąd w poprzednim komentarzu. Kiedy go opublikowałem, pomyślałem, że reprezentacja ograniczenia sumy nieważonej jest łatwa (stąd nacisk na ważenie ), ale to całkowicie błędne.

Tsuyoshi Ito,

2

Co jeśli zawsze bierzemy maksymalny element (w częściowej kolejności) o najmniejszej wadze. Po wyczerpaniu elementów zwracamy je w odwrotnej kolejności jako dane wyjściowe.

Daniel Martin
źródło

Problem jest niezmienny w transformacji polegającej na odwróceniu częściowego uporządkowania i zanegowaniu wszystkich wag. Więc nie rozumiem, jak to może się różnić od chciwego algorytmu Robina K, podanego w komentarzach w kontrprzykładzie.

David Eppstein,

Ale ta metoda działa na jego przykład: najpierw wybierany byłby wierzchołek 5, następnie wierzchołek 4, następnie 3, 2, a na końcu 1. Zatem ostateczna kolejność to 1, 2, 3, 4, 5. W rzeczywistości nie Myślę, że trudno jest udowodnić, że ta metoda działa. Załóżmy, że masz rozwiązanie, które nie ma maksymalnego elementu (zlewu) o minimalnej masie w ostatniej pozycji. Następnie możesz znaleźć inne rozwiązanie, które ma tę właściwość, po prostu zmieniając pozycję takiego elementu na ostatni i zachowując resztę taką, jaka jest. Postępuj indukcyjnie na tym, co zostało, a otrzymasz formalny dowód.

Daniel Martin

Tak ... to nie działa ... 1 -> 2 -> 3, 1 -> 4 z wagami odpowiednio 4, -7, 6, 3.

Daniel Martin

1

Ten problem przypomina mi wiele drzew decyzyjnych. Rozważałbym tego rodzaju rozwiązanie, które stara się zawsze wybierać najbardziej obiecującą ścieżkę, ale patrząc na cały podrozdział:

Zaczynając od węzłów sink, kieruj się w stronę źródeł, jeden poziom na raz. Robiąc to, nadaj każdej krawędzi wagę. Ta waga powinna reprezentować minimalną kwotę, którą musisz „zapłacić”, inaczej „zyskasz”, przechodząc przez słupek, zaczynając od węzła, na który wskazuje krawędź. Załóżmy, że jesteśmy na poziomie i + 1 i przechodzimy na poziom i. Oto, co zrobiłbym, aby przypisać wagę krawędzi wskazującej na węzeł poziomu i:

edge_weight = wskazując_węzeł_węzła.
Znajdź krawędź zaczynając od „węzła wskazującego” o maksymalnej masie. Niech ta waga będzie następna_edge_weight.
edge_weight + = next_edge_weight

Następnie zbuduj kolejność w następujący sposób:

Niech S będzie granicą wyszukiwania, tj. Zestawem węzłów do wyboru od następnego.
Wybierz węzeł, aby (waga_węzła + maksymalna_waga) była zmaksymalizowana.
Usuń węzeł z wykresu i S. Dodaj „dzieci” węzła do S.
Jeśli wykres nie jest pusty, przejdź do kroku 1.
Postój.

Pomysł polega na przejściu przez te podgrupy, które zapewnią jak największy zysk w pierwszej kolejności, aby później móc ponieść koszty podgrafów ujemnej wagi.

chazisop
źródło

Pozytywne uporządkowanie topologiczne

Odpowiedzi: