Szukam sposobu generowania wykresów, aby znana była optymalna osłona wierzchołków. Nie ma ograniczeń co do liczby węzłów lub krawędzi, tylko to, że wykres jest całkowicie połączony.
chodzi o wygenerowanie wykresu, który nie jest łatwy do znalezienia optymalnej osłony wierzchołków, aby móc przetestować na niej różne heurystyki
Znalazłem artykuł Arthur, J. i Frendeway, J. Generowanie problemów podróżujących sprzedawców ze znanymi optymalnymi trasami, The Journal of the Operational Research Society, t. 39, nr 2 (luty, 1988), str. 153-159 do generowania TSP ze znanym optymalnym, niestety nie mogę uzyskać do niego dostępu.
Czy istnieje znany algorytm?
Odpowiedzi:
Rozwinięcie komentarza vzn w odpowiedź: Standardowa redukcja z CNF-SAT do pokrycia wierzchołków jest dość łatwa: utwórz wierzchołek dla każdego terminu (zmienna lub jego negacja), połącz każdą zmienną z negacją krawędzią, utwórz klikę dla każdej klauzuli i połącz każdy wierzchołek kliki z wierzchołkiem dla jednego z warunków w klauzuli. Jeśli zaczniesz od problemu satysfakcji ze znanym zadawalającym zadaniem, da ci to problem z pokrywą wierzchołków ze znanym optymalnym rozwiązaniem (wybierz termin wierzchołki podany w zadaniu, a w każdej klauzuli kliki wybierz wszystkie oprócz jednego wierzchołka, tak aby klauzula wierzchołek, który nie jest wybrany, sąsiaduje z wybranym wierzchołkiem).
Więc teraz musisz znaleźć problemy z zadowalaniem, które mają znane zadowalające zadanie, ale gdzie rozwiązanie jest trudne do znalezienia. Istnieje wiele znanych sposobów generowania trudnych problemów satysfakcji (np. Generowanie losowych instancji k-SAT zbliżonych do progu satysfakcji), ale dodatkowy wymóg znajomości satysfakcjonującego przypisania ogranicza możliwości. Jedną z rzeczy, które możesz tutaj zrobić, jest przejście przez inny poziom redukcji, od trudnego kryptograficznie problemu, takiego jak faktoryzacja. To znaczy wybierz dwie duże liczby pierwsze p i q, ustaw obwód boolowski do mnożenia p i q jako liczby binarne i przetłumacz go na formułę CNF, w której dla każdego wejścia (p i q) i dla każdej wartości pośredniej jest zmienna drut w obwodzie, klauzula dla każdego wyjścia, zmuszająca go do uzyskania właściwej wartości, oraz klauzula dla każdej bramki wymuszająca spójność między wejściami i wyjściami bramki. Następnie przetłumacz tę formułę CNF na osłonę wierzchołków.
Aby uzyskać prostszą strategię, najpierw wybierz satysfakcjonujące przypisanie do formuły 3CNF, a następnie generuj losowo klauzule, zachowując tylko te klauzule, które są zgodne z przypisaniem, a następnie przekonwertuj na pokrycie wierzchołków. Jeśli klauzule mają jednolite prawdopodobieństwo, będzie to podatne na heurystykę opartą na stopniach (termin wierzchołki pasujące do wybranego przypisania będzie miał niższy stopień niż termin wierzchołki, które nie spełniają), ale tej wady można uniknąć poprzez dostosowanie prawdopodobieństwa klauzul zgodnie z tym, ile warunków klauzuli zgadza się z wybranym zleceniem. Prawdopodobnie jest to podatne na atak wielomianowy w czasie, ale może nie być to naturalne dla pokrycia wierzchołków, więc może stanowić dobry zestaw instancji testowych, mimo że nie ma dużej gwarancji twardości.
źródło
najbliższym refem, który znalazłem było ... W trudnych przypadkach przybliżonego pokrycia wierzchołków przez Sundara Vishwanathana. nie widziałem referencji za sprawdzanie trudnych przypadków konkretnego problemu.
jak w moim komentarzu, istnieje wiele badań nad tym odpowiednim podejściem do SAT, które można zredukować do pokrycia wierzchołków.
Jeśli chodzi o komentarz DE, pomysł generowania przypadkowych instancji i wybierania takich instancji, które są trudne dla standardowego algorytmu, wydaje mi się całkowicie rozsądny, szczególnie przy empirycznym / eksperymentalnym podejściu badawczym [1], jest to standardowa procedura operacyjna dla podobnych badań nad SAT punkt przejścia. [2]
który, nawiasem mówiąc, ma coś do powiedzenia, gdzie „twardy” region jest dla dowolnego innego problemu NP pełnego [3,4,5], który odnosi się mniej więcej do punktu krytycznego w „gęstości” 1s w przypadkowych przypadkach określonych w systemie binarnym. dla pokrycia wierzchołków prawdopodobnie odpowiada to gęstości krawędzi.
zauważ, że udowodnienie, że można zbudować zestaw twardych instancji i tylko twardych instancji, jest w zasadzie równoważne problemowi P vs NP. bardziej formalna analiza tej równoważności znajduje się w pracy Razborov / Rudich Natural Proofs.
[1] algorytmy eksperymentalne
[2] Badania przejścia fazowego SAT
[3] Przejścia fazowe w trudnych problemach NP
[4] Przejścia fazowe w problemach NP-zupełnych: wyzwanie dla prawdopodobieństwa, kombinatoryki i informatyki autorstwa Moore'a
[5] Zachowanie przemiany fazowej przez Walsha
źródło