{"id":35406,"date":"2019-10-31T22:04:08","date_gmt":"2019-10-31T19:04:08","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov\/"},"modified":"2021-01-02T13:01:41","modified_gmt":"2021-01-02T11:01:41","slug":"kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","status":"publish","type":"post","link":"https:\/\/prohoster.info\/pl\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Jak rozwi\u0105zywa\u0107 problemy NP-trudne za pomoc\u0105 algorytm\u00f3w parametryzowanych","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Praca badawcza to chyba najbardziej interesuj\u0105ca cz\u0119\u015b\u0107 naszej edukacji. Idea polega na tym, aby jeszcze na studiach spr\u00f3bowa\u0107 swoich si\u0142 w wybranym kierunku. Na przyk\u0142ad studenci kierunk\u00f3w In\u017cynieria Oprogramowania i Uczenie Maszynowe cz\u0119sto realizuj\u0105 projekty badawcze w firmach (g\u0142\u00f3wnie JetBrains lub Yandex, ale nie tylko).<\/p>\n

W tym po\u015bcie opowiem o swoim projekcie z dziedziny Informatyki. W ramach pracy zbada\u0142em i wdro\u017cy\u0142em w praktyce podej\u015bcia do rozwi\u0105zania jednego z najbardziej znanych problem\u00f3w NP-trudnych: problemu pokrycia wierzcho\u0142k\u00f3w<\/b>.<\/p>\n

Obecnie szybko rozwija si\u0119 ciekawy spos\u00f3b podej\u015bcia do problem\u00f3w NP-trudnych \u2014 algorytmy parametryzowane. Postaram si\u0119 wprowadzi\u0107 was w temat, opowiedzie\u0107 o kilku prostych algorytmach parametryzowanych i opisa\u0107 jeden skuteczny metod, kt\u00f3ry bardzo mi pom\u00f3g\u0142. O swoje wyniki zaprezentowa\u0142em na zawodach PACE Challenge: po zako\u0144czeniu test\u00f3w otwartych moje rozwi\u0105zanie zajmuje trzecie miejsce, a ostateczne wyniki b\u0119d\u0105 znane 1 lipca.<\/p>\n

\"Jak
\n<\/a><\/noindex><\/p>\n

O mnie<\/h3>\n

Nazywam si\u0119 Wasilij Alfiorow, obecnie ko\u0144cz\u0119 trzeci rok na Naukowej Szkole Ekonomicznej \u2014 w Petersburgu. Algorytmami interesuj\u0119 si\u0119 ju\u017c od czas\u00f3w szkolnych, kiedy ucz\u0119szcza\u0142em do moskiewskiej szko\u0142y 179 i skutecznie bra\u0142em udzia\u0142 w olimpiadach informatycznych.<\/p>\n

Ostateczna liczba specjalist\u00f3w od parametr\u00f3w algorytm\u00f3w wchodzi do baru\u2026<\/h3>\n

Przyk\u0142ad pochodzi z ksi\u0105\u017cki \u00abAlgorytmy parametryzowane\u00bb<\/a><\/noindex><\/i><\/p>\n

Wyobra\u017a sobie, \u017ce jeste\u015b ochroniarzem w barze w ma\u0142ym mie\u015bcie. Ka\u017cdego pi\u0105tku po\u0142owa miasta przychodzi do twojego baru, aby si\u0119 zrelaksowa\u0107, co sprawia ci sporo k\u0142opot\u00f3w: musisz wyrzuca\u0107 ha\u0142a\u015bliwych go\u015bci, aby unikn\u0105\u0107 b\u00f3jek. W ko\u0144cu to ci\u0119 nu\u017cy i postanawiasz podj\u0105\u0107 \u015brodki zapobiegawcze.<\/p>\n

Poniewa\u017c miasto jest ma\u0142e, dok\u0142adnie wiesz, kt\u00f3re pary go\u015bci najprawdopodobniej si\u0119 pok\u0142\u00f3c\u0105, je\u015bli znajd\u0105 si\u0119 w barze razem. Masz list\u0119 n<\/i> ludzi, kt\u00f3rzy przyjd\u0105 dzisiaj wieczorem do baru. Postanawiasz nie wpu\u015bci\u0107 niekt\u00f3rych miejskich mieszka\u0144c\u00f3w w taki spos\u00f3b, aby nikt si\u0119 nie pobi\u0142. Jednocze\u015bnie twoje kierownictwo nie chce traci\u0107 zysk\u00f3w i b\u0119dzie niezadowolone, je\u015bli nie wpuszczisz do baru wi\u0119cej ni\u017c k<\/i> ludzi.<\/p>\n

Niestety, problem, przed kt\u00f3rym stoisz, jest klasycznym problemem NP-trudnym. Mog\u0142e\u015b zna\u0107 go jako Pokrycie wierzcho\u0142k\u00f3w<\/a><\/noindex>, or like the vertex cover problem. For such problems, no algorithms are known that work in a reasonable time in general. To be precise, the unproven and quite strong ETH (Exponential Time Hypothesis) suggests that this problem cannot be solved in time \"Jak, meaning that there is nothing significantly better than brute force. For example, let\u2019s say that approximately n = 1000<\/i> people are heading to your bar. Then brute force would involve \"Jak combinations, which is about \"Jak \u2014 an insane number. Fortunately, your management has imposed a restriction of k = 10<\/i>, so the number of combinations you need to consider is much smaller: the number of subsets of ten elements is equal to \"Jak. This is already better, but still cannot be calculated in a day even on a powerful cluster.
\n\"Jak
\nTo eliminate the likelihood of fights with such a configuration of strained relationships among the bar visitors, you need to prohibit Bob, Daniel, and Fyodor from entering. There is no solution where only two remain outside.<\/p>\n

Does this mean it's time to give up and let everyone in? Let's consider other options. For instance, you might not let only those who are likely to fight with a large number of people. If someone can start a fight with at least k + 1<\/i> other individuals, then they definitely should not be let in \u2014 otherwise, you will have to keep out all k + 1<\/i> the locals they can fight with, which would certainly upset management.<\/p>\n

Assuming you've ejected everyone you can based on this principle. Then all remaining people can only fight with at most k<\/i> others. By removing k<\/i> people from them, you can prevent no more than \"Jak conflicts. Therefore, if more than \"Jak people are involved in at least one conflict, you certainly won't be able to prevent them all. Since, obviously, you will definitely let in the completely conflict-free people, you need to consider all subsets of ten from two hundred people. There are approximately \"Jak, and such a number of operations can already be managed on a cluster.<\/p>\n

Je\u015bli mo\u017cna bezpiecznie wpu\u015bci\u0107 osoby, kt\u00f3re nie maj\u0105 konflikt\u00f3w, co powiedzie\u0107 o tych, kt\u00f3rzy bior\u0105 udzia\u0142 w jednym konflikcie? W rzeczywisto\u015bci mo\u017cna ich r\u00f3wnie\u017c wpu\u015bci\u0107, zamykaj\u0105c drzwi przed ich przeciwnikiem. Rzeczywi\u015bcie, je\u015bli Alicja k\u0142\u00f3ci si\u0119 tylko z Bobem, to wpuszczaj\u0105c Alicj\u0119, nie przegramy: Bob mo\u017ce mie\u0107 inne konflikty, a Alicja na pewno ich nie ma. Po co w takim razie nie wpuszcza\u0107 obu? Po takich operacjach zostaje nie wi\u0119cej ni\u017c \"Jak go\u015bci z nierozwi\u0105zanym losem: w sumie mamy \"Jak konflikty, w ka\u017cdym bior\u0105 udzia\u0142 po dwie osoby, a ka\u017cda uczestniczy przynajmniej w dw\u00f3ch. Oznacza to, \u017ce musimy przeanalizowa\u0107 tylko \"Jak warianty, co mo\u017ce zaj\u0105\u0107 p\u00f3\u0142 dnia na laptopie.<\/p>\n

W rzeczywisto\u015bci prostymi rozwa\u017caniami mo\u017cna osi\u0105gn\u0105\u0107 jeszcze bardziej korzystne warunki. Zauwa\u017cmy, \u017ce konieczne jest rozwi\u0105zanie wszystkich spor\u00f3w, czyli z ka\u017cdej k\u0142\u00f3c\u0105cej si\u0119 pary wybra\u0107 przynajmniej jedn\u0105 osob\u0119, kt\u00f3r\u0105 nie wpuszczimy. Rozwa\u017cmy taki algorytm: we\u017amiemy dowolny konflikt, usuniemy jednego uczestnika i uruchomimy rekurencyjnie z reszt\u0105, nast\u0119pnie usuniemy drugiego i r\u00f3wnie\u017c uruchomimy rekurencyjnie. Poniewa\u017c w ka\u017cdym kroku kogo\u015b wykluczamy, drzewo rekurencji tego algorytmu to drzewo binarne o g\u0142\u0119boko\u015bci k<\/i>, dlatego algorytm dzia\u0142a w czasie \"Jak, gdzie n<\/i> -- liczba wierzcho\u0142k\u00f3w, a m<\/i> -- liczba kraw\u0119dzi. W naszym przyk\u0142adzie to oko\u0142o dziesi\u0119ciu milion\u00f3w, co w ci\u0105gu u\u0142amka sekundy mo\u017cna obliczy\u0107 nie tylko na laptopie, ale nawet na telefonie kom\u00f3rkowym.<\/p>\n

Podany powy\u017cej przyk\u0142ad to przyk\u0142ad algorytmu parametryzowanego<\/b>. Algorytmy parametryzowane to algorytmy, kt\u00f3re dzia\u0142aj\u0105 w czasie f(k) poly(n)<\/i>, gdzie p<\/i> -- wielomian, f<\/i> -- dowolna funkcja obliczalna, a k<\/i> -- jaki\u015b parametr, kt\u00f3ry mo\u017ce by\u0107 znacznie mniejszy od rozmiaru zadania.<\/p>\n

Wszystkie rozwa\u017cania do tego algorytmu prowadz\u0105 do przyk\u0142adu kernelizacji<\/b> jedn\u0105 z powszechnych technik tworzenia algorytm\u00f3w parametryzowanych. Kernelizacja polega na redukcji rozmiaru zadania do warto\u015bci ograniczonej funkcj\u0105 od parametru. Otrzymane zadanie cz\u0119sto nazywa si\u0119 rdzeniem. Tak, prostymi rozwa\u017caniami na temat stopni wierzcho\u0142k\u00f3w uzyskali\u015bmy kwadratowy rdze\u0144 dla zadania Vertex Cover, parametryzowanego wed\u0142ug wielko\u015bci odpowiedzi. Istniej\u0105 r\u00f3wnie\u017c inne parametry, kt\u00f3re mo\u017cna wybra\u0107 dla tego zadania (na przyk\u0142ad Vertex Cover Above LP), ale b\u0119dziemy omawia\u0107 w\u0142a\u015bnie ten parametr.<\/p>\n

Pace Challenge<\/h3>\n

Zawody PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) powsta\u0142o w 2015 roku, aby stworzy\u0107 po\u0142\u0105czenie mi\u0119dzy algorytmami parametryzowanymi a podej\u015bciami wykorzystywanymi w praktyce do rozwi\u0105zywania zada\u0144 obliczeniowych. Pierwsze trzy zawody dotyczy\u0142y znalezienia szeroko\u015bci drzewa grafu (Treewidth<\/a><\/noindex>), znalezienia drzewa Steinera (Steiner Tree<\/a><\/noindex>), oraz znalezienia zbioru wierzcho\u0142k\u00f3w, kt\u00f3ry przecina cykle (Feedback Vertex Set<\/a><\/noindex>). W tym roku jednym z zada\u0144, w kt\u00f3rym mo\u017cna by\u0142o spr\u00f3bowa\u0107 swoich si\u0142, by\u0142o opisane powy\u017cej zadanie o pokryciu wierzcho\u0142k\u00f3w.<\/p>\n

Zawody z ka\u017cdym rokiem zyskuj\u0105 na popularno\u015bci. Je\u015bli wierzy\u0107 wst\u0119pnym danym, w tym roku w zawodach dotycz\u0105cych rozwi\u0105zania zadania pokrycia wierzcho\u0142k\u00f3w uczestniczy\u0142o 24 zespo\u0142y. Warto zauwa\u017cy\u0107, \u017ce zawody trwaj\u0105 nie kilka godzin, a nawet nie tydzie\u0144, lecz kilka miesi\u0119cy. Zespo\u0142y maj\u0105 mo\u017cliwo\u015b\u0107 przestudiowania literatury, pomy\u015blenia o w\u0142asnym oryginalnym pomy\u015ble i pr\u00f3by jego realizacji. W zasadzie te zawody stanowi\u0105 prac\u0119 badawcz\u0105. Pomys\u0142y najefektywniejszych rozwi\u0105za\u0144 oraz nagrodzenie zwyci\u0119zc\u00f3w odb\u0119dzie si\u0119 wsp\u00f3lnie z konferencj\u0105 IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) w ramach najwi\u0119kszego corocznego spotkania algorytmicznego w Europie ALGO<\/a><\/noindex>. Bardziej szczeg\u00f3\u0142owe informacje na temat samych zawod\u00f3w mo\u017cna znale\u017a\u0107 na stronie<\/a><\/noindex>, a wyniki z lat ubieg\u0142ych mo\u017cna znale\u017a\u0107 tutaj<\/a><\/noindex>.<\/p>\n

Schemat rozwi\u0105zania<\/h3>\n

Aby poradzi\u0107 sobie z zadaniem pokrycia wierzcho\u0142k\u00f3w, spr\u00f3bowa\u0142em zastosowa\u0107 algorytmy parametryzowane. Z regu\u0142y sk\u0142adaj\u0105 si\u0119 one z dw\u00f3ch cz\u0119\u015bci: regu\u0142 uproszczenia (kt\u00f3re w idealnym przypadku prowadz\u0105 do kernelizacji) oraz regu\u0142 rozga\u0142\u0119ziania. Regu\u0142y uproszczenia to wst\u0119pne przetwarzanie wej\u015bcia w czasie wielomianowym. Celem zastosowania takich regu\u0142 jest sprowadzenie zadania do r\u00f3wnowa\u017cnego zadania mniejszego rozmiaru. Regu\u0142y uproszczenia to najbardziej kosztowna cz\u0119\u015b\u0107 algorytmu, a zastosowanie tej cz\u0119\u015bci prowadzi do og\u00f3lnego czasu pracy. \"Jak Zamiast prostego czasu wielomianowego. W naszym przypadku regu\u0142y rozga\u0142\u0119ziania opieraj\u0105 si\u0119 na tym, \u017ce dla ka\u017cdego wierzcho\u0142ka musimy wzi\u0105\u0107 w odpowiedzi albo jego, albo jego s\u0105siada.<\/p>\n

Og\u00f3lny schemat jest taki: stosujemy regu\u0142y uproszczenia, nast\u0119pnie wybieramy jaki\u015b wierzcho\u0142ek i wykonujemy dwa rekurencyjne wywo\u0142ania: w pierwszym bierzemy go w odpowiedzi, a w drugim bierzemy wszystkich jego s\u0105siad\u00f3w. Nazywamy to rozga\u0142\u0119zieniem (bran\u017cowaniem) wzd\u0142u\u017c tego wierzcho\u0142ka.<\/p>\n

Do tego schematu wprowadzimy dok\u0142adnie jedno uzupe\u0142nienie w nast\u0119pnym akapicie.<\/p>\n

Pomys\u0142y na regu\u0142y rozga\u0142\u0119zania (bran\u017cowania)<\/h3>\n

Porozmawiajmy o tym, jak wybra\u0107 wierzcho\u0142ek, przy kt\u00f3rym b\u0119dzie si\u0119 odbywa\u0107 rozga\u0142\u0119zienie.
\nPodstawowa idea jest bardzo chciwa w sensie algorytmicznym: we\u017amy wierzcho\u0142ek o maksymalnym stopniu i rozga\u0142\u0119\u017amy si\u0119 w\u0142a\u015bnie przy nim. Dlaczego wydaje si\u0119, \u017ce to lepsze? Poniewa\u017c w drugim ga\u0142\u0119zi wywo\u0142ania rekurencyjnego w ten spos\u00f3b usuniemy bardzo wiele wierzcho\u0142k\u00f3w. Mo\u017cna si\u0119 spodziewa\u0107, \u017ce zostanie ma\u0142y graf, a na nim szybko zrealizujemy dzia\u0142anie.<\/p>\n

To podej\u015bcie z wcze\u015bniej om\u00f3wionymi prostymi technikami kernelizacji sprawdza si\u0119 ca\u0142kiem nie\u017ale, rozwi\u0105zuj\u0105c pewne testy o rozmiarze kilku tysi\u0119cy wierzcho\u0142k\u00f3w. Jednak na przyk\u0142ad s\u0142abo dzia\u0142a dla graf\u00f3w kubicznych (to znaczy graf\u00f3w, w kt\u00f3rych stopie\u0144 ka\u017cdego wierzcho\u0142ka wynosi trzy).
\nJest jeszcze jeden pomys\u0142 oparty na do\u015b\u0107 prostym my\u015bleniu: je\u015bli graf jest niesp\u00f3jny, zadanie na jego komponentach sp\u00f3jno\u015bci mo\u017cna rozwi\u0105zywa\u0107 niezale\u017cnie, \u0142\u0105cz\u0105c odpowiedzi na ko\u0144cu. To zreszt\u0105 jest niewielka obiecana modyfikacja w schemacie, kt\u00f3ra znacznie przyspieszy rozwi\u0105zanie: wcze\u015bniej w takim przypadku pracowali\u015bmy za iloczyn czas\u00f3w liczenia odpowiedzi komponent\u00f3w, a teraz pracujemy za sum\u0119. A dla przyspieszenia rozga\u0142\u0119ziania trzeba przekszta\u0142ci\u0107 graf sp\u00f3jny w niesp\u00f3jny.<\/p>\n

Jak to zrobi\u0107? Je\u015bli w grafie jest w\u0119ze\u0142 krytyczny, nale\u017cy podzieli\u0107 wed\u0142ug niego. W\u0119ze\u0142 krytyczny to taki w\u0119ze\u0142, kt\u00f3rego usuni\u0119cie powoduje utrat\u0119 sp\u00f3jno\u015bci grafu. Wszystkie w\u0119z\u0142y krytyczne w grafie mo\u017cna znale\u017a\u0107 klasycznym algorytmem w czasie liniowym. Takie podej\u015bcie znacz\u0105co przyspiesza proces dzielenia.
\n\"Jak
\nPrzy usuni\u0119ciu dowolnego z wyr\u00f3\u017cnionych w\u0119z\u0142\u00f3w graf rozpadnie si\u0119 na komponenty sp\u00f3jne.<\/p>\n

Zrobimy to, ale oczekujemy wi\u0119cej. Na przyk\u0142ad, mo\u017cemy szuka\u0107 w grafie ma\u0142ych ci\u0119\u0107 wierzcho\u0142kowych i przeprowadza\u0107 podzia\u0142 przez wierzcho\u0142ki z nich. Najbardziej efektywny znany mi spos\u00f3b na znalezienie minimalnego globalnego ci\u0119cia wierzcho\u0142kowego to wykorzystanie drzewa Gomoriego-Hu, kt\u00f3re buduje si\u0119 w czasie kubicznym. W PACE Challenge typowy rozmiar grafu to kilka tysi\u0119cy w\u0119z\u0142\u00f3w. W takim przypadku w ka\u017cdym w\u0119\u017ale rekurencji trzeba wykona\u0107 miliardy operacji. Tak wi\u0119c rozwi\u0105zanie zadania w ramach zadanego czasu jest po prostu niemo\u017cliwe.<\/p>\n

Spr\u00f3bujmy zoptymalizowa\u0107 rozwi\u0105zanie. Minimalne ci\u0119cie wierzcho\u0142kowe mi\u0119dzy par\u0105 w\u0119z\u0142\u00f3w mo\u017cna znale\u017a\u0107 dowolnym algorytmem, kt\u00f3ry buduje maksymalny przep\u0142yw. Mo\u017cna zastosowa\u0107 do tego algorytm Dinica<\/a><\/noindex>, w praktyce dzia\u0142a on bardzo szybko. Mam podejrzenie, \u017ce teoretycznie mo\u017cna udowodni\u0107 ocen\u0119 na czas dzia\u0142ania \"Jak, co jest ju\u017c ca\u0142kiem akceptowalne.<\/p>\n

Pr\u00f3bowa\u0142em kilka razy szuka\u0107 ci\u0119\u0107 mi\u0119dzy parami losowych w\u0119z\u0142\u00f3w i wybiera\u0107 z nich najbardziej zr\u00f3wnowa\u017cone. Niestety, na otwartych testach PACE Challenge da\u0142o to s\u0142abe wyniki. Por\u00f3wnywa\u0142em z algorytmem, kt\u00f3ry dzieli\u0142 si\u0119 przez wierzcho\u0142ki o maksymalnym stopniu, uruchamiaj\u0105c go z ograniczeniem na g\u0142\u0119boko\u015b\u0107 spadku. Po algorytmie pr\u00f3buj\u0105cym znale\u017a\u0107 ci\u0119cie w ten spos\u00f3b pozostawa\u0142y grafy wi\u0119kszego rozmiaru. Dzieje si\u0119 tak, poniewa\u017c ci\u0119cia by\u0142y bardzo niezbalansowane: usuwaj\u0105c 5-10 w\u0119z\u0142\u00f3w, udawa\u0142o si\u0119 od\u0142\u0105czy\u0107 zaledwie 15-20.<\/p>\n

Warto zauwa\u017cy\u0107, \u017ce w artyku\u0142ach na temat teoretycznie najszybszych algorytm\u00f3w stosowane s\u0105 znacznie bardziej zaawansowane techniki wyboru w\u0119z\u0142\u00f3w do podzia\u0142u. Takie techniki maj\u0105 bardzo skomplikowan\u0105 implementacj\u0119 i cz\u0119sto z\u0142e wyniki pod wzgl\u0119dem czasu i pami\u0119ci. Nie uda\u0142o mi si\u0119 wydzieli\u0107 z nich w pe\u0142ni akceptowalnych dla praktyki.<\/p>\n

Jak stosowa\u0107 zasady uproszczenia<\/h3>\n

Mamy ju\u017c pomys\u0142y na kernelizacj\u0119. Przypomn\u0119:<\/p>\n

    \n
  1. Je\u015bli istnieje izolowany w\u0119ze\u0142, usu\u0144 go.<\/li>\n
  2. Je\u015bli istnieje wierzcho\u0142ek o stopniu 1, usu\u0144 go i we\u017a jego s\u0105siada w odpowiedzi.<\/li>\n
  3. Je\u015bli istnieje wierzcho\u0142ek o stopniu przynajmniej k + 1<\/i>, we\u017a go w odpowiedzi.<\/li>\n<\/ol>\n

    Z pierwszymi dwoma wszystko jasne, z trzecim jest jeden trik. Je\u015bli w \u017cartobliwej zagadce o barze mieli\u015bmy ograniczenie g\u00f3rne na k<\/i>, to w wyzwaniu PACE musimy po prostu znale\u017a\u0107 wierzcho\u0142kowe pokrycie minimalnego rozmiaru. To typowa transformacja zada\u0144 wyszukiwania (Search Problem) w zadania rozwi\u0105zania (Decision Problem), cz\u0119sto mi\u0119dzy tymi dwoma rodzajami zada\u0144 nie robi si\u0119 r\u00f3\u017cnicy. W praktyce, gdy piszemy rozwi\u0105zanie dla zadania o wierzcho\u0142kowym pokryciu, r\u00f3\u017cnica mo\u017ce by\u0107. Na przyk\u0142ad, jak w trzecim punkcie.<\/p>\n

    Z punktu widzenia realizacji mo\u017cna post\u0105pi\u0107 na dwa sposoby. Pierwsze podej\u015bcie nazywa si\u0119 Iterative Deepening. Polega ono na tym, \u017ce zaczynamy od jakiego\u015b rozs\u0105dnego ograniczenia dolnego na odpowied\u017a i nast\u0119pnie uruchamiamy nasz algorytm, u\u017cywaj\u0105c tego ograniczenia jako g\u00f3rnego ograniczenia na odpowied\u017a, nie schodz\u0105c w rekurencji g\u0142\u0119biej ni\u017c to ograniczenie. Je\u015bli znajdziemy jak\u0105\u015b odpowied\u017a, jest ona gwarantowanie optymalna, w przeciwnym razie mo\u017cemy zwi\u0119kszy\u0107 to ograniczenie o jeden i ponownie uruchomi\u0107 algorytm.<\/p>\n

    Inne podej\u015bcie polega na przechowywaniu jakiej\u015b aktualnej optymalnej odpowiedzi i poszukiwaniu odpowiedzi mniejszego rozmiaru, przy jej znalezieniu zmieniaj\u0105c ten parametr k<\/i> aby lepiej odci\u0105\u0107 zb\u0119dne ga\u0142\u0119zie w wyszukiwaniu.<\/p>\n

    Po przeprowadzeniu kilku nocnych eksperyment\u00f3w, zdecydowa\u0142em si\u0119 na kombinacj\u0119 tych dw\u00f3ch sposob\u00f3w: najpierw uruchamiam sw\u00f3j algorytm z jakim\u015b ograniczeniem na g\u0142\u0119boko\u015b\u0107 wyszukiwania (dobieraj\u0105c je tak, aby zajmowa\u0142o to znikomy czas w por\u00f3wnaniu z g\u0142\u00f3wnym rozwi\u0105zaniem) i u\u017cywam najlepiej znalezionej odpowiedzi jako g\u00f3rnego ograniczenia na odpowied\u017a \u2014 to znaczy na to same k<\/i>.<\/p>\n

    Wierzcho\u0142y o stopniu 2<\/h3>\n

    Z wierzcho\u0142kami o stopniu 0 i 1 si\u0119 uporali\u015bmy. Okazuje si\u0119, \u017ce mo\u017cna to zrobi\u0107 tak\u017ce z wierzcho\u0142kami o stopniu 2, ale do tego od grafu s\u0105 potrzebne bardziej skomplikowane operacje.<\/p>\n

    Aby to wyja\u015bni\u0107, musimy jako\u015b oznaczy\u0107 wierzcho\u0142ki. Nazwijmy wierzcho\u0142ek o stopniu 2 wierzcho\u0142kiem v<\/i>, a jego s\u0105siad\u00f3w \u2014 wierzcho\u0142kami x<\/i> i y<\/i>. Nast\u0119pnie b\u0119dziemy mieli dwa przypadki.<\/p>\n

      \n
    1. Kiedy x<\/i> i y<\/i> \u2014 s\u0105siedzi. Wtedy mo\u017cna wzi\u0105\u0107 w odpowiedzi x<\/i> i y<\/i>, a v<\/i> usun\u0105\u0107. I naprawd\u0119, z tego tr\u00f3jk\u0105ta przynajmniej dwa wierzcho\u0142ki musimy wzi\u0105\u0107 w odpowiedzi, i na pewno nie przegramy, je\u015bli we\u017amiemy x<\/i> i y<\/i>: prawdopodobnie maj\u0105 jeszcze s\u0105siad\u00f3w, a v<\/i> oni nie maj\u0105.<\/li>\n
    2. Kiedy x<\/i> i y<\/i> \u2014 nie s\u0105siedzi. W takim razie twierdzi si\u0119, \u017ce wszystkie trzy wierzcho\u0142ki mo\u017cna po\u0142\u0105czy\u0107 w jeden. Idea polega na tym, \u017ce w takim przypadku istnieje optymalne rozwi\u0105zanie, kt\u00f3re obejmie albo v<\/i>, albo oba wierzcho\u0142ki x<\/i> i y<\/i>. Przy czym w pierwszym przypadku b\u0119dziemy musieli wzi\u0105\u0107 w odpowiedzi wszystkich s\u0105siad\u00f3w x<\/i> i y<\/i>, a w drugim nie jest to konieczne. To dok\u0142adnie odpowiada przypadkom, gdy nie bierzemy po\u0142\u0105czonego wierzcho\u0142ka w odpowiedzi i gdy go bierzemy. pozosta\u0142o jedynie zauwa\u017cy\u0107, \u017ce w obu przypadkach odpowied\u017a z tej operacji zmniejsza si\u0119 o jeden.<\/li>\n<\/ol>\n

      \"Jak<\/p>\n

      Warto zauwa\u017cy\u0107, \u017ce takie podej\u015bcie w uczciwy spos\u00f3b w czasie liniowym jest do\u015b\u0107 trudne do realizacji. \u0141\u0105czenie wierzcho\u0142k\u00f3w to z\u0142o\u017cona operacja, trzeba skopiowa\u0107 listy s\u0105siad\u00f3w. Je\u015bli zrobimy to nieostro\u017cnie, mo\u017cemy otrzyma\u0107 asymptotycznie nieoptymalny czas dzia\u0142ania (na przyk\u0142ad, je\u015bli po ka\u017cdym po\u0142\u0105czeniu skopiujemy wiele kraw\u0119dzi). Skupi\u0142em si\u0119 na poszukiwaniu ca\u0142kowitych \u015bcie\u017cek z wierzcho\u0142k\u00f3w stopnia 2 i rozwa\u017caniu mn\u00f3stwa szczeg\u00f3lnych przypadk\u00f3w, takich jak cykle z takich wierzcho\u0142k\u00f3w lub z wszystkimi takimi wierzcho\u0142kami z wyj\u0105tkiem jednego.<\/p>\n

      Ponadto, ta operacja musi by\u0107 odwracalna, aby podczas powrotu z rekursji przywr\u00f3ci\u0107 graf do pierwotnego stanu. Aby to zapewni\u0107, nie czy\u015bci\u0142em list kraw\u0119dzi po\u0142\u0105czonych wierzcho\u0142k\u00f3w, po czym po prostu wiedzia\u0142em, kt\u00f3re kraw\u0119dzie dok\u0105d skierowa\u0107. Taka realizacja graf\u00f3w r\u00f3wnie\u017c wymaga ostro\u017cno\u015bci, ale zapewnia uczciwy czas liniowy. A dla graf\u00f3w z kilkudziesi\u0119cioma tysi\u0105cami kraw\u0119dzi mie\u015bci si\u0119 to w pami\u0119ci podr\u0119cznej procesora, co daje du\u017ce przewagi w pr\u0119dko\u015bci.<\/p>\n

      Liniowe j\u0105dro<\/h3>\n

      Na koniec, najbardziej interesuj\u0105ca cz\u0119\u015b\u0107 j\u0105dra.<\/p>\n

      Na pocz\u0105tku przypomnijmy, \u017ce w grafach dwudzielnych minimalne pokrycie wierzcho\u0142kowe mo\u017cna znale\u017a\u0107 w \"Jak. W tym celu nale\u017cy skorzysta\u0107 z algorytmu Hopcrofta-Karpa<\/a><\/noindex> aby znale\u017a\u0107 tam maksymalne skojarzenie, a nast\u0119pnie skorzysta\u0107 z twierdzenia K\u00f6ning-Egervari<\/a><\/noindex>.<\/p>\n

      Idea liniowego j\u0105dra jest taka: najpierw rozdzielamy graf, to znaczy zamiast ka\u017cdego wierzcho\u0142ka v<\/i> wprowadzamy dwa wierzcho\u0142ki \"Jak i \"Jak, a zamiast ka\u017cdej kraw\u0119dzi u \u2014 v<\/i> wprowadzamy dwie kraw\u0119dzie \"Jak i \"JakOtrzymany graf b\u0119dzie dwudzielny. Znajdziemy w nim minimalne pokrycie wierzcho\u0142k\u00f3w. Niekt\u00f3re wierzcho\u0142ki oryginalnego grafu znajd\u0105 si\u0119 tam dwa razy, niekt\u00f3re tylko raz, a inne - ani razu. Twierdzenie Nemhausera-Trottera stwierdza, \u017ce w takim przypadku mo\u017cna usun\u0105\u0107 wierzcho\u0142ki, kt\u00f3re nie znalaz\u0142y si\u0119 ani razu, a w odpowiedzi wzi\u0105\u0107 te, kt\u00f3re znalaz\u0142y si\u0119 dwa razy. Co wi\u0119cej, m\u00f3wi, \u017ce z pozosta\u0142ych wierzcho\u0142k\u00f3w (tych, kt\u00f3re znalaz\u0142y si\u0119 raz) nale\u017cy wzi\u0105\u0107 w odpowiedzi przynajmniej po\u0142ow\u0119.<\/p>\n

      W\u0142a\u015bnie nauczyli\u015bmy si\u0119 pozostawia\u0107 w grafie nie wi\u0119cej ni\u017c 2k<\/i> wierzcho\u0142k\u00f3w. I rzeczywi\u015bcie, je\u015bli w odpowiedzi zostaje przynajmniej po\u0142owa wszystkich wierzcho\u0142k\u00f3w, to w sumie jest ich nie wi\u0119cej ni\u017c 2k<\/i>.<\/p>\n

      Tutaj uda\u0142o mi si\u0119 zrobi\u0107 ma\u0142y krok naprz\u00f3d. Oczywiste jest, \u017ce zbudowane w ten spos\u00f3b j\u0105dro zale\u017cy od tego, jakie dok\u0142adnie minimalne pokrycie wierzcho\u0142k\u00f3w w grafie dwudzielnym przyj\u0119li\u015bmy. Chcia\u0142bym wzi\u0105\u0107 takie, aby liczba pozosta\u0142ych wierzcho\u0142k\u00f3w by\u0142a minimalna. Wcze\u015bniej robi\u0107 to mo\u017cna by\u0142o tylko w czasie \"Jak. Ja jednak wymy\u015bli\u0142em realizacj\u0119 tego algorytmu w czasie \"Jak, dzi\u0119ki czemu to j\u0105dro mo\u017cna szuka\u0107 w grafach licz\u0105cych setki tysi\u0119cy wierzcho\u0142k\u00f3w na ka\u017cdym etapie bran\u017cingu.<\/p>\n

      Wynik<\/h3>\n

      Praktyka pokazuje, \u017ce moje rozwi\u0105zanie dobrze dzia\u0142a na testach licz\u0105cych kilka setek wierzcho\u0142k\u00f3w i kilka tysi\u0119cy kraw\u0119dzi. Na takich testach mo\u017cna spodziewa\u0107 si\u0119, \u017ce rozwi\u0105zanie znajdzie si\u0119 w p\u00f3\u0142 godziny. Prawdopodobie\u0144stwo znalezienia odpowiedzi w rozs\u0105dnym czasie og\u00f3lnie wzrasta, je\u015bli w grafie jest wystarczaj\u0105co du\u017co wierzcho\u0142k\u00f3w o du\u017cym stopniu, na przyk\u0142ad stopnia 10 i wy\u017cej.<\/p>\n

      Aby wzi\u0105\u0107 udzia\u0142 w zawodach, rozwi\u0105zania nale\u017ca\u0142o wys\u0142a\u0107 na optil.io<\/a><\/noindex>. Z danych przedstawionych tam tabeli<\/a><\/noindex>, moje rozwi\u0105zanie na otwartych testach zajmuje trzecie miejsce spo\u015br\u00f3d dwudziestu, z du\u017c\u0105 przewag\u0105 nad drugim. Je\u015bli by\u0107 ca\u0142kowicie szczerym, to nie do ko\u0144ca wiadomo, jak b\u0119d\u0105 oceniane rozwi\u0105zania w samych zawodach: na przyk\u0142ad moje rozwi\u0105zanie przechodzi mniej test\u00f3w ni\u017c rozwi\u0105zanie na czwartym miejscu, ale te, kt\u00f3re przechodzi, dzia\u0142a szybciej.<\/p>\n

      Wyniki z zamkni\u0119tych test\u00f3w b\u0119d\u0105 znane pierwszego lipca.<\/p>\n

      \u0179r\u00f3d\u0142o: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

      \u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u044b \u0441 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 Software Engineering \u0438 Machine Learning \u0447\u0430\u0441\u0442\u043e \u0438\u0434\u0443\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u041d\u0418\u0420\u044b \u0432 \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0438 (\u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c, JetBrains \u0438\u043b\u0438 \u042f\u043d\u0434\u0435\u043a\u0441, \u043d\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e). \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u0441\u0432\u043e\u0451\u043c \u043f\u0440\u043e\u0435\u043a\u0442\u0435 \u043f\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044e Computer Science. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":26562,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-35406","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Jak rozwi\u0105zywa\u0107 problemy NP-trudne za pomoc\u0105 algorytm\u00f3w parametryzowanych | ProHoster","description":"Praca naukowo-badawcza, chyba najciekawsza cz\u0119\u015b\u0107 naszego kszta\u0142cenia. Idea polega na tym, aby jeszcze na uniwersytecie spr\u00f3bowa\u0107 swoich si\u0142 w wybranym kierunku.","canonical_url":"https:\/\/prohoster.info\/pl\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pl_PL","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041a\u0430\u043a \u0440\u0435\u0448\u0430\u0442\u044c NP-\u0442\u0440\u0443\u0434\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 | ProHoster","og:description":"\u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438.","og:url":"https:\/\/prohoster.info\/pl\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:04:08+00:00","article:modified_time":"2021-01-02T11:01:41+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"35406","title":null,"description":"","keywords":"","keyphrases":null,"primary_term":null,"canonical_url":"","og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 23:06:35","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:03:22","updated":"2026-01-21 23:06:35","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pl\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}