Mamy DAG. Mamy funkcję na węzłach (luźno mówiąc, numerujemy węzły). Chcielibyśmy utworzyć nowy ukierunkowany wykres z tymi zasadami:
- Tylko węzły o tym samym numerze można zawrzeć w tym samym nowym węźle. . (Jednak .)
- Dodajemy wszystkie stare krawędzie między nowymi węzłami: .
- Ten nowy wykres jest nadal DAG.
Jaka jest minimalna? Co to jest algorytm tworzący nowy minimalny wykres?
Odpowiedzi:
Jednym podejściem do rozwiązania tego problemu byłoby zastosowanie programowania liniowego liczb całkowitych (ILP). Zajmijmy się wersją decyzyjną problemu: biorąc pod uwagę , czy istnieje sposób na zawarcie wierzchołków tego samego koloru, aby uzyskać DAG o wielkości ≤ k ?k ≤k
Można to wyrazić jako instancję ILP przy użyciu standardowych technik. Kolor oryginalnego wykresu jest podany dla każdego wierzchołka. Sugeruję, aby oznaczyć każdy wierzchołek etykietą w ; wszystkie wierzchołki z tą samą etykietą i tym samym kolorem zostaną skurczone. Problemem decyzyjnym staje się zatem: czy istnieje oznakowanie, które powoduje, że skurczenie wszystkich wierzchołków tego samego koloru w ten sam sposób daje DAG?{1,2,…,k}
Aby wyrazić to jako całkowity program liniowy, wprowadź zmienną całkowitą dla każdego wierzchołka v , aby przedstawić etykietę na wierzchołku v . Dodaj nierówność 1 ≤ ℓ v ≤ k .ℓv v v 1≤ℓv≤k
Następnym krokiem jest wyrażenie wymogu, że zakontraktowany wykres musi być DAG. Należy zauważyć, że jeśli jest znakowanie postaci wymienionych powyżej, bez utraty ogólności istnieje taki oznakowania, gdzie etykiety indukowania topologiczne sortuje umownej wykresie (czyli jeżeli poprzedza W umownej wykresu, a V „S etykiety jest mniejszy, niż w „s etykiecie). Tak więc, dla każdej krawędzi v → wagowo w oryginalnym wykresie dodamy ograniczenie, że albo v i w mają taką samą etykietę i tego samego koloru, albo v „s etykieta jest mniejsza niż w ” s etykietą. W szczególności dla każdej krawędzi vv w v w v→w v w v w w początkowym wykresu gdzie v , w mają ten sam kolor, dodać nierówność £ -l v ≤ £ -l wag . Dla każdej krawędzi v → w, gdzie v , w mają różne kolory, dodaj nierówność ℓ v < ℓ w .v → w v , w ℓv≤ ℓw v → w v , w ℓv< ℓw
Sprawdź teraz, czy istnieje jakieś realne rozwiązanie tego programu liczb całkowitych. Możliwe będzie rozwiązanie, jeśli i tylko wtedy, gdy etykietowanie będzie miało pożądaną formę (tj. Skurczenie wszystkich wierzchołków tego samego koloru o tym samym kolorze daje DAG). Innymi słowy, możliwe będzie rozwiązanie tylko i wyłącznie wtedy, gdy istnieje sposób na zawężenie oryginalnego wykresu do DAG o wielkości . Możemy użyć dowolnego liczbowego solvera do programowania liniowego; jeśli solver ILP daje nam odpowiedź, mamy odpowiedź na pierwotny problem decyzyjny.≤ k
Oczywiście nie można tego zagwarantować w czasie wielomianowym. Nie ma gwarancji. Jednak solwery ILP są całkiem niezłe. Spodziewałbym się, że dla rozsądnego wykresu masz spore szanse, że solver ILP może rozwiązać ten problem w rozsądnym czasie.
Możliwe jest również zakodowanie tego jako instancji SAT i użycie solvera SAT. Nie wiem, czy to byłoby bardziej skuteczne. Prawdopodobnie łatwiej jest myśleć o wersji ILP.
(Mam nadzieję, że to prawda. Nie sprawdziłem dokładnie każdego szczegółu, więc proszę dokładnie sprawdzić moje rozumowanie! Mam nadzieję, że gdzieś nie poszedłem źle).
Aktualizacja (10/21): Wygląda na to, że ILP tego formularza można rozwiązać w czasie liniowym, przetwarzając DAG w topologicznie posortowanej kolejności i śledząc dolną granicę etykiety dla każdego wierzchołka. To mnie podejrzewa o moje rozwiązanie: czy popełniłem gdzieś błąd?
źródło
UWAGA: AFAICT, DW znalazł dziurę w tej redukcji i jest ona błędna (patrz komentarze). Trzymanie go tutaj ze względów historycznych.
Wprowadzenie : najpierw zredukuję problem Monotone 3SAT do naszego problemu. Chociaż problem Monotone 3SAT jest trywialnie satysfakcjonujący, nasz problem może dodatkowo rozwiązać problem minimalnej prawdziwej Monotone 3SAT , który jest trudny dla NP; dlatego ten problem jest trudny dla NP.
Redukcja z Monotone 3SAT do naszego problemu
Mamy monotoniczną formułę logiczną wyrażoną jako ciąg zmiennych i ciąg klauzul. CNF ma postać taką, że:Φ = ( V, C.)
i
Konwersja
Budujemy wykres, . Każdy wierzchołek w G ′ ma etykietę; wierzchołki z tą samą etykietą kwalifikują się do skurczu.sol′= V.′, E′ sol′
Najpierw konstruujemy wykres w następujący sposób: dla każdego tworzymy dwa węzły, każdy oznaczony x i oraz skierowaną krawędź od jednego do drugiego (kliknij obrazy, aby wyświetlić w wysokiej rozdzielczości).xja∈ V. xja
Te węzły mogą oczywiście zostać zakontraktowane, ponieważ mają tę samą etykietę. Rozważymy zmienne / węzły, które zostały zakontraktowane, jako wycenione jako fałszywe, a te, które nie są traktowane jako wycenione jako prawdziwe :
Oto kolejna wizualizacja, rozwijająca ograniczenie klauzuli:
Zatem każde ograniczenie klauzuli wymaga, aby co najmniej jedna ze zmiennych w nim zawartych pozostała niezakłócona; ponieważ niekontraktowane węzły są wyceniane jako prawda, wymaga to, aby jedna ze zmiennych była prawdziwa; dokładnie to, czego wymaga Monotone SAT dla swoich klauzul.
Redukcja od minimum True Monotone 3SAT
Monotone 3SAT jest banalnie satysfakcjonujący; możesz po prostu ustawić wszystkie zmienne na true.
Ponieważ jednak naszym problemem minimalizacji DAG jest znalezienie największego skurczu, przekłada się to na znalezienie satysfakcjonującego przypisania, które wytwarza najbardziej fałszywe zmienne w naszym CNF; co jest równoznaczne ze znalezieniem minimalnych prawdziwych zmiennych. Ten problem jest czasami nazywany minimalnym True Monotone 3SAT lub tutaj (jako problem optymalizacji lub problem decyzyjny) lub k-True Monotone 2SAT (jako słabszy problem decyzyjny); oba trudne problemy NP. Zatem nasz problem jest trudny NP.
Bibliografia:
Źródła wykresów:
źródło
Przy każdej zamianie (z wyjątkiem bezpośrednich zamian rodzic-dziecko) dodajesz nowe relacje przodek-potomek, które sprawiają, że ustalenie, który z nich jest tego wart w perspektywie długoterminowej, nie jest łatwe. Dlatego prosty chciwy algorytm zawiedzie w ogólnym przypadku. Jeśli jednak zastosujesz podejście z użyciem siły brutalnej, możesz określić najmniejszy wykres:
Python-ish (nie testowany):
Nie jestem pewien, czy to naprawdę trudny problem, ale ręczna gra z niektórymi wykresami wydaje się bardzo kombinatoryczna. Jestem ciekawy, czy coś trudnego można zredukować do tego problemu, czy też istnieje algorytm o lepszym czasie działania.
źródło