Vitajte na [www.pocitac.win] Pripojiť k domovskej stránke Obľúbené stránky
Pochopenie zložitosti NP
* p (polynomický čas): Problémy v P môžu byť vyriešené algoritmom, ktorého runtime je ohraničený polynómnou funkciou veľkosti vstupu (napr. O (n), o (n^2), o (n^3)). Všeobecne sa považujú za „sledovateľné“, pretože runtime rastie primerane s rastom vstupov. Pomyslite na triedenie zoznamu čísel pomocou efektívnych algoritmov, ako je zlúčenie zoradenia alebo QuickSort.
* np (nedeterministický polynomický čas): Problémy v NP majú vlastnosť, že * riešenie * je možné * overiť * v polynomiálnom čase. To * neznamená, že problém možno * vyriešiť * v polynomiálnom čase. Znamená to len, že ak vám niekto * dá riešenie, môžete rýchlo skontrolovať, či je to správne. Príklady zahŕňajú:
* sudoku: Dostanete vyplnenú mriežku. Môžete rýchlo skontrolovať, či ide o platné riešenie Sudoku.
* Problém s cestovným predajcom (TSP): Vzhľadom na prehliadku môžete ľahko vypočítať svoju celkovú vzdialenosť a potvrdiť, že navštívi všetky mestá presne raz.
* booleovská uspokojivosť (sat): Vzhľadom na priradenie hodnôt pravdy k premenným v booleovskom vzorci môžete ľahko vyhodnotiť vzorec a zistiť, či je to pravda.
* np-tvrdé: Problém je tvrdý NP, ak sa každý problém v NP môže zredukovať v polynomiálnom čase. To znamená, že ak by ste mohli vyriešiť problém NP tvrdý v polynomiálnom čase, môžete vyriešiť * každý * problém v NP v polynomiálnom čase. Problémy s tvrdými NP sú aspoň také ťažké ako najťažšie problémy v NP.
* np-complete: Problém je komplex NP, ak je v NP aj NP-HARD. Problémy s úplným doplnkom NP sú „najťažšie“ problémy v NP. Ak by ste našli algoritmus polynomiálneho času pre akýkoľvek problém s dokončením NP, dokázali by ste, že p =np.
Vplyv na efektívnosť algoritmu a výpočtové zdroje:
1. Intraktabilita:
* Problém P vs. NP: Jedným z najväčších nevyriešených problémov v oblasti informatiky je, či P =NP. Väčšina počítačových vedcov verí, že p ≠ np. Ak je to pravda (a takmer každý verí, že je), potom problémy s NP-Complete a NP-HARD * nemožno * vyriešiť algoritmami polynomiálneho času. To znamená, že s rastúcou veľkosťou vstupu bude beh akéhokoľvek algoritmu riešenia týchto problémov exponenciálne alebo rýchlejšie rastie.
* Exponenciálny rast: Pretože mnoho problémov v reálnom svete je NP-tvrdá alebo NP-komplexná (napr. Optimalizácia trasy, plánovanie, prideľovanie zdrojov, kryptografia), často čelíme algoritmom s exponenciálnou časovou zložitosťou (napr. O (2^n), o (n!)).
* Praktické dôsledky: To má vážne praktické dôsledky. Pre dokonca aj mierne veľké vstupy sa presné riešenia nemožno vypočítať v primeranom časovom rámci. Predstavte si, že sa snažíte nájsť optimálnu trasu pre cestujúceho predajcu, ktorý navštevuje iba 20 miest. Brute-force prístup by trval astronomicky dlho.
2. Spotreba zdrojov:
* čas: Ako už bolo spomenuté, primárny vplyv je na runtime. Algoritmy pre problémy s tvrdými NP môžu trvať hodiny, dni, roky alebo dokonca dlhšie, kým sa dokončia realistické veľkosti vstupov.
* pamäť: Exponenciálne časové algoritmy často vyžadujú exponenciálne množstvo pamäte. Napríklad niektoré algoritmy vyhľadávania musia uložiť celý vyhľadávací priestor v pamäti.
* Výpočtová sila: Riešenie problémov s tvrdými NP si často vyžaduje významnú výpočtovú silu, ktorá si vyžaduje vysoko výkonné počítače, zhluky alebo dokonca superpočítače.
3.
Pretože pre tieto problémy nemôžeme (pravdepodobne) nájsť algoritmy polynomiálneho času, uchýlime sa k niekoľkým stratégiám:
* Aproximačné algoritmy: Cieľom týchto algoritmov je nájsť riešenia, ktoré sú v polynomiálnom čase „dosť dobré“. Zaručujú riešenie v rámci určitého faktora optimálneho riešenia. Napríklad by ste mohli nájsť prehliadku TSP, ktorá je najviac o 50% dlhšia ako optimálna prehliadka.
* heuristika: Heuristika sú techniky riešenia problémov, ktoré používajú pravidlá a skúsenosti na rýchle nájdenie „dobrých“ riešení, ale bez akejkoľvek záruky optimality alebo dokonca zaručeného viazania výkonu. Príklady zahŕňajú:
* chamtivé algoritmy: V každom kroku urobte lokálne optimálnu voľbu v nádeji, že globálne nájdete dobré riešenie.
* Lokálne vyhľadávanie: Začnite s náhodným riešením a iteratívne ho vylepšite tým, že urobíte malé zmeny, kým sa nedosiahne lokálny optim.
* simulované žíhanie: Typ miestneho vyhľadávania, ktorý umožňuje príležitostné „zlé“ kroky, aby unikol miestnej optime.
* Genetické algoritmy: Tieto algoritmy inšpirované prirodzeným výberom a časom vyvíjajú populáciu kandidátnych riešení.
* parametrizovaná zložitosť: Identifikujte parameter problému (napr. Veľkosť vrcholového krytu, šírka stromov grafu) a konštrukčné algoritmy, ktorých runtime je polynóm vo veľkosti vstupu, ale v parametri exponenciálny. To môže byť užitočné, ak je parameter v praxi malý.
* Špeciálne prípady: Niekedy nájdeme algoritmy polynomiálneho času pre konkrétne inštancie problémov tvrdých NP. Napríklad TSP sa dá efektívne vyriešiť, ak sú mestá umiestnené v rovine a metrika vzdialenosti je euklidovská.
* kvantové výpočty (potenciálny budúci vplyv): Kvantové počítače sú stále do značnej miery teoretické, majú potenciál na vyriešenie niektorých problémov s NP efektívnejšie ako klasické počítače. Je to však stále aktívna oblasť výskumu a nie je zaručené riešenie. Groverov algoritmus poskytuje kvadratické zrýchlenie problémov s vyhľadávaním a Algoritmus SHOR môže efektívne ovplyvniť veľké množstvo (prelomenie mnohých moderných kryptografických algoritmov).
v súhrne: Zložitosť NP má obrovský vplyv na návrh algoritmov a využitie zdrojov. Pravdepodobnosť P ≠ NP znamená, že veľa dôležitých problémov je vo svojej podstate ťažké vyriešiť presne v primeranom čase. To nás núti používať aproximačné algoritmy, heuristiku alebo iné techniky na nájdenie riešení, ktoré sú v praxi „dosť dobré“. Taktiež vedie k výskumu nových výpočtových paradigiem, ako je Quantum Computing. Pochopenie zložitosti NP je rozhodujúce pre každého, kto navrhuje algoritmy pre výpočtovo náročné úlohy.