Związanie problemów NP-Complete z problemami świata rzeczywistego

Mam przyzwoitą znajomość NP Pełne problemy; to nie jest problem. To, czego nie mam, to dobre wyczucie miejsca, w którym pojawiają się w "prawdziwym" programowaniu. Niektórzy (np. Plecak i podróżujący sprzedawca) są oczywiste, ale inni nie wydają się oczywiście związani z "prawdziwymi" problemami.Związanie problemów NP-Complete z problemami świata rzeczywistego

Kilka razy miałem doświadczenie z trudnym problemem, tylko po to, aby zdać sobie sprawę, że jest to dobrze znany NP. Całkowicie zbadany problem. Gdybym szybciej rozpoznał połączenie, mógłbym zaoszczędzić sporo czasu na badaniu istniejących rozwiązań mojego konkretnego problemu.

Czy są jakieś zasoby (online lub drukowane), które w konkretny sposób łączą NP Complete z rzeczywistymi instancjami?

Edycja: Edytowanie: Na przykład pracowałem nad programem, który próbował podzielić uczniów na grupy na podstawie wieku, klasy i szkoły pochodzenia, co jest zasadniczo problem z partycjonowaniem wykresu. Zajęło mi trochę czasu, aby zrealizować połączenie.

Źródło

2010-03-08 terru

http://pl.wikipedia.org/wiki/List_of_np_complete_problems – kennytm

Ostatni raz wyglądałem, wikipedia było biednym źródłem praktycznych zastosowań. Wygląda na to, że nieco się poprawiła. Dziękuję za wskazanie. – terru

Zgadzam się, że zobaczenie niektórych rzeczywistych przypadków NP-zupełnych/trudnych problemów i zobaczenie połączenia z wersją abstrakcyjną, z czasem zwiększy twoją intuicję do nawiązywania połączenia. –

Znalazłem, że Computers and Intractability jest ostatecznym odnośnikiem na ten temat.

Źródło

2010-03-08 19:44:06

Jakieś uwagi na temat zakresu, w jakim omawiają związki z rzeczywistymi problemami? Wydaje się, że koncentruje się mocno na teorii (co jest w porządku, ale nie to, czego teraz szukam). – terru

Nie omawiają one tak naprawdę problemów w świecie rzeczywistym, ale mają imponujący wachlarz problemów NP-zupełnych, a także dyskusję, jak udowodnić problem NP-zupełny. Kiedy myślisz, że masz do czynienia z problemem NP-zupełnym lub NP-trudnym, to jest to dobra książka do przejrzenia i zobaczenia, czy coś wygląda znajomo. –

Skupia się na teorii. Jednak jest dość krótki i jeśli go przeczytasz, pomoże ci to rozwinąć intuicję na to, co prawdopodobnie jest NP-complete. –

Zazwyczaj połączenie mówisz muszą być wyodrębnione z tzw redukcji, na przykład zmniejszyć 3-SAT z problemem, na którym pracujemy, a następnie można stwierdzić, że problem ma takie same złożoność tego.

Ten fragment nie jest trywialna, ponieważ trzeba udowodnić, że można włączyć każde wystąpienie problemu l znanego NP-trudny problemu L do instancji c Twojego problemu C korzystania deterministyczne algorytmy polinomialne.

więc, oprócz nauki basical korelacje wspólnych problemów NP-trudny korzystania z pamięci, nie ma sposobu, aby się upewnić, czy problem jest podobny do innego NP-trudny bez pierwszej próby zgadywania, a następnie udowodnienie go , musisz być mądry.

Źródło

2010-03-08 19:49:22 Jack

Wszystko, co mówisz, jest poprawne, ale to nie jest to, o czym mówię. Na przykład pracowałem nad programem, który próbował podzielić uczniów na grupy na podstawie wieku, stopnia i szkoły pochodzenia, co jest zasadniczo problemem z partycjonowaniem wykresów. Uświadomienie sobie tego zajęło mi sporo czasu. – terru

tu jest link wiki: http://wapedia.mobi/en/List_of_NP-complete_problems Wskazówka mówi

Ta lista nie jest w żaden sposób kompleksowy (istnieje ponad 3000 znanych NP-zupełny problemów)

prawdopodobnie byłoby byłoby wspaniałym zadaniem, gdyby ktokolwiek mógł skompilować taką listę.

Teoretyk powinien spróbować zrozumieć/udowodnić problem NP-Complete/Hard. Ale programista nie ma czasu. On potrzebuje listy.

Czy mam rację?

Myślę, że powinien on być google to. I przeczytaj wszystkie linki. Dodaj każdy nowy problem znaleziony w linku do Twojej listy.

Nadzieja pomaga

PS: Nie zapomnij, aby opublikować listę kiedy skończysz: P

Źródło

2010-06-23 12:55:41

Za opracowanie lepszego intuicji książka „Podręcznik Algorytm Projektowanie, Second Edition” przez Skiena (fragmenty książek Google) jest po prostu świetny.

Lista z tyłu z problemami (łącznie z trudnymi problemami), że zawierać ilustrację i dyskusji (często) z świata rzeczywistego przykład.
Obejmuje zarówno teoretyczną i praktyczną stronę rzeczy, często mówiąc o aktualnym kodzie.

lektura EXCEPTS Online tu (patrz przykłady w rozdziałach 14): http://books.google.dk/books?id=7XUSn0IKQEgC&printsec=frontcover#v=onepage&q&f=false

Rozdział 16 (nie online) omawia pewne trudne problemy, w tym partycji wykresie.

Źródło

2010-11-12 23:41:46

Ponadto, w przypadku trudnych problemów, daje sugestie, w jaki sposób można je rozwiązać za pomocą np. algorytm aproksymacyjny. –

Podręcznik projektowania algorytmu wspomina również książkę Garey and Johnson, która ma listę 400 problemów NP-zupełnych z komentarzami. Komentarze są dobre, jak sądzę. Nie mam tej książki, ale myślę o jej kupieniu. Tak jak ty, chciałbym mieć lepszą intuicję w rozpoznawaniu trudnych problemów w świecie rzeczywistym :) Powiedział: Przejrzyj katalog, gdy tylko kwestionujesz istnienie wydajnego algorytmu dla twojego problemu. Rzeczywiście, to jest ta jedyna książka w mojej bibliotece, do której sięgam najczęściej. –

Związanie problemów NP-Complete z problemami świata rzeczywistego

Odpowiedz

Powiązane problemy