Dokładny algorytm dla problemu znakowania krawędzi w DAG

Wdrażam część systemu, która wymaga pomocy. Dlatego kadruję go jako problem graficzny, aby uczynić go niezależnym od domeny.

Problem: Otrzymujemy ukierunkowany wykres acykliczny . Bez utraty ogólności załóżmy, że ma dokładnie jeden wierzchołek źródłowy i dokładnie jeden wierzchołek ; pozwolić oznacza zbiór wszystkich skierowanych ścieżek z na , w . Jesteśmy również otrzymuje zestaw wierzchołków . Problem polega na przypisaniu nieujemnych wag liczb całkowitych do krawędzi , więc dowolne dwie ścieżki w mają tę samą wagę wtedy i tylko wtedy, gdy zawierają ten sam podzbiór wierzchołków $G=(V,E)$ $G$ $s$ $t$ $P$ $s$ $t$ $G$ $R \subseteq V$ $G$ $P$ . (Ciężar ścieżki jest sumą wag jej krawędzi.) Zakres wag ścieżek w powinien być jak najmniejszy. $R$ $P$

Obecnie moje podejście nie wydaje się skuteczne; Szukam tylko odniesień do literatury lub dobrych spostrzeżeń. Cokolwiek innego jest również mile widziane.

Edycja: Czy istnieje dowód na twardość tego problemu? Czy kompaktowa numeracja zawsze istnieje?

ds.algorithms reference-request co.combinatorics graph-algorithms directed-acyclic-graph użytkownik5153
źródło

proszę wyjaśnić „Zakres wag ścieżek w P powinien być optymalny”. Czy wagi są tylko liczbami całkowitymi? Czy dozwolone są wagi ujemne? Czy „optimum” oznacza „tak mały zasięg, jak to możliwe”, czy może oznacza coś innego?

Artem Kaznatcheev

zredagowałem pytanie. Dzięki za komentarz. wagi powinny być nieujemnymi liczbami całkowitymi, a zakres powinien być jak najmniejszy.

user5153

Prostą strategią dla znalezienia prawidłowego rozwiązania byłoby przypisanie różnej potęgi dwóch do każdego wierzchołka v w R, użycie tej liczby jako wagi wszystkich przychodzących krawędzi do v i przypisanie wagi zero do wszystkich pozostałych krawędzi. Oczywiście może to nie być optymalne, ale przynajmniej wyznacza górną granicę wymaganego zakresu. Czy kiedykolwiek ulepszenie polega na tym, aby różne krawędzie przechodzące przez ten sam wierzchołek w R miały różne ciężary względem siebie, czy może uprościć problem, dostosowując wagi do wierzchołków zamiast do krawędzi?

David Eppstein,

Odpowiedź BTW @ DavidEppstein pokazuje, że maksymalna masa całkowita ścieżki wynosi

. Jest to ściśle związane ze stałymi. Jako przykład możesz wziąć wykres

O (2^{| R |})

$O(2^{|R|})$

G = (V, E)

$G = (V, E)$

V = [n] \cup {s, t}

$V = [n] \cup \{s, t\}$

. Niech także

. Na

są

różnych ścieżek, a ponieważ każda ścieżka ma nieujemną masę całkowitą, co najmniej jedna musi mieć wagę co najmniej

E = {(i, j) : i < j} \cup {(s, 1), (n, t), (s, t)}

$E = \{(i, j): i<j\} \cup \{(s, 1), (n, t), (s, t)\}$

R = [n]

$R = [n]$

2^{n}

$2^n$

R

$R$

2^{n} - 1

$2^n -1$

Sasho Nikolov,

jasne, w najgorszym przypadku miałem na myśli ciasno (tak naprawdę napisałem to w pierwszej wersji tego komentarza, która zaginęła). pomyślałem, że dobrze byłoby najpierw ustalić pewne absolutne granice, ponieważ nikt jeszcze nie zajął się problemem optymalizacji.

Sasho Nikolov,

nie słyszałem o tym problemie dokładnie w literaturze [może ktoś inny], jednak jako „problem w pobliżu” wydaje mi się, że minimalne drzewo opinające miałoby użyteczne właściwości do rozwiązania twojego problemu. na przykład może wygenerowanie dwóch minimalnych drzew rozpinających, zaczynając od wierzchołka źródłowego i wierzchołka synchronizacji, i propagowanie ich na zewnątrz, aż się dotkną itp., może rozwiązać problem lub dać dokładną odpowiedź. zanim ktokolwiek rzuci mnie na ten temat tutaj, proszę zrozumieć, że rozszerzam pomysł MST, który ma być generowany, zaczynając od danego wierzchołka [zwykle zaczyna się od najkrótszej krawędzi na całym wykresie]. jeśli to nie działa, jestem ciekawy z tego powodu.

vzn
źródło

Przepraszam, ale nie widzę znaczenia tej odpowiedzi na to pytanie.

David Eppstein,

może masz lepszy pomysł o czym on mówi? czy ma to dla ciebie sens, jak stwierdzono?

vzn

Musi przypisać ciężary krawędziom. W jaki sposób pomoc w obliczeniu MST?

Nicholas Mancuso

ok po przeczytaniu i nikt inny nie zaproponował odpowiedzi, wydawało się, że problem można przekształcić na dwie części - (1) przypisać wagi na podstawie kryteriów / ograniczeń, (2) znaleźć najkrótsze ścieżki na podstawie tych wag. wydaje się, że MST może się przydać w (2). albo może nie! (np. może 1/2 jest ściśle ze sobą powiązane)

Nie. Minimalne drzewa rozpinające dotyczą tylko grafów bezkierunkowych; wykres wejściowy jest skierowany. Co więcej, minimalne drzewa rozpinające są jedynie powierzchownie powiązane z najkrótszymi ścieżkami.

Jeffε

Dokładny algorytm dla problemu znakowania krawędzi w DAG

Odpowiedzi: