Codzienne problemy z NP-zupełnymi problemami

Odpowiedzi:

24

Mój ulubiony przykład do użycia z przyjaciółmi spoza CS to:

Abraham, A. Blum, Sandholm. Algorytmy rozliczeniowe dla rynków wymiany barterowej: umożliwienie ogólnopolskiej wymiany nerek. EC07.

Rynki wymiany nerki są zasadniczo ograniczoną formą ubezpieczenia rowerowego. Podoba mi się ten przykład, ponieważ a) łatwo jest wyjaśnić istotę (jeśli pominąć niektóre bardziej techniczne szczegóły) ib) jest to jeden z niewielu przypadków, w których wiem, gdzie lepsze algorytmy mogą dosłownie uratować życie!

Moim drugim ulubionym przykładem jest problem szpitali i mieszkańców (zwany także problemem przyjęć na studia). Każdy szpital zalicza wszystkich mieszkańców (kończących studia medyczne), a mieszkańcy szeregują szpitale. Każdy szpital ma określoną liczbę miejsc. Stamtąd jest to stabilny problem dopasowywania i można go rozwiązać w czasie wielomianowym.

Ale w rzeczywistości pary mogą wejść do systemu (tak, istnieje system ) razem, tak że system nie będzie na przykład dzielić małżeństw, które ubiegają się o miejsce zamieszkania. Dodanie par sprawia, że ​​problem NP jest kompletny. Oprócz tego, że jest łatwy do wyjaśnienia, ładnie pokazuje, w jaki sposób wprowadzenie połączeń dalekiego zasięgu może indukować kompletność NP.

Joshua Grochow
źródło
1
Świetny przykład! David Manlove intensywnie pracował nad tego rodzaju problemami (zarówno wymiana, jak i dopasowanie); systemy są używane w Wielkiej Brytanii i na Węgrzech. dcs.gla.ac.uk/~davidm/publications.html O ile mi wiadomo, podejścia te pokonują algorytmy NRMP, a algorytm aproksymacji 3/2 Erica McDermida jest najlepiej znany. dx.doi.org/10.1007/978-3-642-02927-1_57
András Salamon
13

Niektóre problemy „na co dzień”, które są trudne NP, odpowiednio sformułowane:

  • Przypisywanie zajęć uniwersyteckich do przedziałów czasowych w celu zminimalizowania konfliktów planowania.

  • Przypisywanie gości weselnych do miejsc, aby przyjaciele siedzieli przy tym samym stole, a wrogowie nie.

  • Planujesz podróż, aby odwiedzić wszystkie miejsca turystyczne na liście, aby zminimalizować jazdę.

Aaron Roth
źródło
12

Problem podróżującego sprzedawcy jest najwyraźniej dostępny ... przynajmniej tam, gdzie jestem, wydaje się, że jest to najpopularniejszy problem wśród osób spoza CS. Znalazłem również następującą ilustrację Wierzchołka Pokrywy całkiem atrakcyjną, wprowadzoną przez mojego instruktora algorytmów:

Masz sieć dróg i chcesz się upewnić, że jeśli samochód utknie w paliwie, na co najmniej jednym końcu drogi znajduje się stacja benzynowa.

Jako urbanista chcesz zminimalizować koszty, budując możliwie najmniejszą liczbę stacji benzynowych. Zasadniczo jest to problem pokrycia wierzchołków, a ja odniosłem pewien sukces, wskazując, że chociaż nie spodziewasz się znaleźć optymalnej osłony wierzchołków w czasie wielomianowym, w czasie wielomianowym możesz znaleźć coś, co dzieli Cię tylko dwa razy, po prostu wybierając oba punkty końcowe o maksymalnym dopasowaniu (cóż, ten ostatni szczegół może zostać pominięty w zależności od stopnia zainteresowania odbiorców - zwłaszcza, że ​​algorytm MM nie jest dokładnie dwuliniowy).

Jako przykład „skoku złożoności” z niewielką zmianą charakteru problemu, uważam, że różnica między sprawdzaniem dwukolorowości i trójkolorowości stanowi dobry przykład. Przy całym rozgłosie wokół twierdzenia o czterech kolorach można również zauważyć, że sprawdzenie, czy mapę można odpowiednio pokolorować tylko trzema kolorami zamiast czterech, jest trudne, chociaż wiemy, że zawsze można ją pokolorować czterema kolorami. Sporo osób uważa to za dość zaskakujące.

Inną dość naturalną sytuacją jest problem odzyskiwania impasu w systemach operacyjnych. Jest to modelowane przez NP-kompletny problem zestawu wierzchołków sprzężenia zwrotnego - najmniejszej liczby wierzchołków, których usunięcie powoduje, że wykres jest acykliczny - i uważam, że jest to również niezwykły przykład (i wyjaśniono to dalej w tym artykule na Wikipedii).

Neeldhara
źródło
3
Maksymalne dopasowanie jest wystarczające dla dwóch zbliżenia, które jest o wiele łatwiej obliczyć i wyjaśnić.
Warren Schudy,
1
@Warren: Dziękujemy za zwrócenie na to uwagi, oczywiście masz całkowitą rację!
Neeldhara,
8

Myślę, że parkowanie równoległe jest trudne NP.

W rzeczywistości bardziej ogólny problem ze znalezieniem najkrótszej ścieżki z ograniczoną krzywizną, która przenosi obiekt wielokątny z jego początkowej pozycji do ostatecznej pozycji w środowisku wielokąta, jest trudny do przeprowadzenia. Dowód można znaleźć tutaj - http://portal.acm.org/citation.cfm?id=298976

Vinayak Pathak
źródło
7

Plecak jest dość łatwy do uchwycenia, szczególnie dla każdego, kto miał do czynienia z małą walizką. Dobry przykład, jeśli zna programowanie dynamiczne.

Kolejną zabawną (praktycznie identyczną) jest suma cząstkowa, ponieważ ma również przyjemną fizyczną interpretację: wyobraź sobie, że liczby są odległościami równych mas punktowych na idealnej (bezmasowej) linijce, z punktem podparcia na początku. Suma częściowa mówi: czy istnieje niepusty podzbiór taki, że linijka pozostanie zrównoważona? (tj. taki, że środek ciężkości jest punktem podparcia dla linijki?)

W obu przypadkach intuicyjne wydaje się, że naiwne strategie mogą wymuszać uciekanie się do sprawdzania wszystkich podzbiorów.

Jeśli mają więcej tła, fajnie jest rozwiązywać problemy, usuwając ograniczenia. Na przykład, zaczynając od problemu maksymalnego przepływu, przekształcając go w program liniowy i czyniąc go programem całkowitym. (Świetny jest oczywiście MAX-CUT, ponieważ dla osób z większym doświadczeniem możesz również przywołać UGC; Dotykam trochę tego w odpowiedzi MO https://mathoverflow.net/questions/33036/is-quadratic-programming -still-np-hard-if-you-have-bounds-and-a-feasible-point / 33048 # 33048. ) Są też fajne rzeczy, takie jak pozornie podobne problemy, które mają znacznie różną złożoność (ścieżka Eulera (krawędzi) jest liniowa czas ścieżka Hamiltonian (wierzchołek) jest NP-kompletna).

matus
źródło
7
Podoba mi się następująca wersja Subset Sum: dostajesz 10 funtów na zakup przekąsek w sklepie. Czy potrafisz znaleźć właściwą kombinację zakupów, aby nie pozostały żadne pieniądze?
András Salamon
6

Konstrukcja krzyżówki jest NP-Complete: Biorąc pod uwagę zestaw odpowiedzi, spróbuj dopasować je do siatki.

Aryabhata
źródło
5

Stworzyłem stronę internetową Tagxedo, http://www.tagxedo.com , generator chmury słów, który dopasowuje słowa do kształtu (wielkości według częstotliwości). Wyniki są bardzo ładne, ale łatwo udowodnić, że problem jest trudny do przeprowadzenia (problem pakowania).

Co ciekawe, wiele problemów trudnych dla NP ma „łatwe” przybliżenie. W wielu przypadkach Tagxedo wykonuje prawie idealną robotę. Prowadzi to do interesującej dyskusji na temat praktycznej implikacji P vs NP i tematu przybliżenia.

Hardy Leung
źródło
4

Jeden z moich przyjaciół spędził sabatyczny rok oglądając mecz baseballowy na każdym dużym stadionie ligowym w Ameryce Północnej. Bez latania. (Nie do końca mu się udało; w tym roku budowano trzy stadiony).

Jeffε
źródło
tak, ale czy próbował zminimalizować zużycie gazu? :)
Suresh Venkat
Nawet znalezienie odpowiedniego harmonogramu było trudne, ponieważ stadiony nie są otwarte codziennie (cykl Hamiltonian z oknami czasowymi).
Jeffε
4

Ze względu na sukces takich firm jak Uber i Lyft wiele osób ma bardzo łatwo dostępne bezpośrednie doświadczenie z problemami NP-zupełnymi.

Biorąc pod uwagę zbiór kierowców i listę osób, które chcą być odbierane o różnych porach, jaki jest najbardziej efektywny przydział pasażerów dla kierowców?

Ten problem (po odpowiednim sformułowaniu) to NPC i wyobrażam sobie, że ludzie w pewnym momencie zastanawiali się, w jaki sposób Uber decyduje się sparować kierowców i pasażerów.

Stella Biderman
źródło
3

Zwykle używam SAT jako przykładu. Mówię coś w stylu: „wszelkiego rodzaju problemy, które pojawiają się cały czas, można przepisać jako szukanie prawdziwego przypisania do wielkiej formuły logicznej. Pytanie P vs NP dotyczy tego, czy istnieje zasadniczo łatwiejszy sposób rozwiązania tej formuły logicznej niż tylko wypróbowanie wszystkich możliwości. Jak dotąd nikt nie był w stanie ani znaleźć sposobu, ani udowodnić, że nie ma łatwego wyjścia ".

Alexandre Passos
źródło
2
Nie jestem pewien, ilu ludzi napotyka to każdego dnia.
Dave Clarke,
3

Np-kompletny problem, taki jak Sudoku (na nxn sqaure), jest jak uniwersalne narzędzie, które pozwala nam skutecznie rozwiązywać wszystkie problemy, które mają skutecznie weryfikowalne rozwiązania. Jedynym wymaganiem jest posiadanie wydajnej metody rozwiązywania Sudoku.

Mohammad Al-Turkistany
źródło
2

N.P.

npjotmNPpjkNP.-kompletne w tej sytuacji. Zauważ, że nie muszą to być bloki, pod warunkiem, że zakładamy, że nie mogą się przewrócić. Mogą to być stosy papierów, skrzyń lub talerzy.

Mam nadzieję że to pomoże!

PageWizard
źródło
2

Kapryśnie dostępnym przykładem jest krótka prezentacja Marka Dominusa (patrz powiązany post na blogu ) zatytułowana „Mój ulubiony problem NP-Complete”, w której zdjęcie poniżej stanowi dokładny zarys dokładnej okładki 3 zestawów .

Tytuły z serii wideo obejmują

  • Taniec, muzyka i książki
  • Dłonie, uszy i stopy
  • Obudź się z Elmo (o spaniu, ubieraniu się i myciu zębów)
  • Ludzie w twoim sąsiedztwie (o strażakach, ratownikach i pielęgniarkach)

Oczywistym celem było, aby każdy film zawierał trzy odcinki o wspólnym temacie, zaczerpnięte z puli tematów interesujących małe dzieci.

Dziwna kaczka w serii była filmem na temat „kwiatów, bananów i… włosów”.

Kwiaty, banany i… włosy.

Greg Bacon
źródło
0

Zwłaszcza, gdy przyjrzymy się później problemowi plecakowemu, ten problem NP-zupełny może być dobrym rozwiązaniem:

Zgadywanie liczb, w którym możesz zgadywać tylko pojedyncze liczby, dopóki nie uzyskasz właściwego wyniku.

Sudix
źródło