Aproximativní algoritmy.
14.4.2005
UIN009 Efektivní algoritmy
1
Jak nakládat s NP-těžkými úlohami? Speciální případy Aproximativní algoritmy Pravděpodobnostní algoritmy Exponenciální algoritmy – pro data malého rozsahu – vylepšení typu „ořezávání neperspektivních možností“ (metoda větví a mezí)
Lokální prohledávání Heuristiky Metody umělé inteligence: neuronové sítě, genetické algoritmy 14.4.2005
UIN009 Efektivní algoritmy
2
Aproximativní řešení optimalizačních problémů Algoritmus A pro optimalizační problém P je aproximativní algoritmus s poměrem ρ(n), pokud pro každé přirozené číslo n a každou instanci I problému P délky n platí max{AP(I)/OPTP(I), OPTP(I)/AP(I)} ≤ ρ(n), přičemž OPTP(I) je optimální řešení a AP(I) řešení nalezené algoritmem A
14.4.2005
UIN009 Efektivní algoritmy
3
Aproximativní algoritmus pro vrcholové pokrytí Vstup: graf G Výstup: Minimální vrcholové pokrytí grafu G AproxVrcholovéPokrytí(V,E) V’:=∅ ; E’:=E; while E’≠∅ do vyber libovolnou hranu {u,v} ∈E’; přidej u,v do V’ odstraň z E’ každou hranu incidentní s u nebo v od return V’. Věta: AproxVrcholovéPokrytí(I)≤ 2OPT(I) pro každou instanci I problému VP. 14.4.2005
UIN009 Efektivní algoritmy
4
Převoditelnost aproximativních řešení NEZ > VP. Lze tímto převodem získat též aproximaci problému NEZ s poměrem 2? Polynomiální transformace, která zachovává optimální řešení, nemusí nutně zachovávat poměr mezi optimálním a aproximativním řešením. Příklad. Graf G, |V(G)|=1000, OPTVP(G)=490, AVP(G) ≤ 980. Pak OPTNEZ(G)/ANEZ(G) ≤ (1000-490)/(1000-980)=25.5
14.4.2005
UIN009 Efektivní algoritmy
5
Problém obchodního cestujícího s ∆ nerovností Problém obchodního cestujícího (optimalizační verze) Vstup: Graf G s nezáporně ohodnocenými hranami Výstup: Hamiltonovská kružnice minimální ceny Dodatečná podmínka: ∆ nerovnost c(x,y)+ c(y,z) ≥ c(x,z) pro každé tři vrcholy x,y,z. AproxPOC∆ (G) sestroj minimální kostru T grafu G průchodem do hloubky očísluj vrcholy kostry T v pořadí, v němž byly navštíveny return (hamiltonovskou) kružnici, která prochází vrcholy grafu v tomto pořadí. 14.4.2005
UIN009 Efektivní algoritmy
6
Problém obchodního cestujícího - pozitivní a negativní výsledek Věta: AproxPOC∆(I) ≤ 2OPT(I) pro každou instanci I problému POC∆. Věta: Jestliže existuje konstanta c≥1 a polynomiální aproximativní algoritmus pro POC bez ∆ nerovnosti takový, že pro každou instanci I platí A(I) ≤ c ⋅ OPT(I), pak P=NP.
14.4.2005
UIN009 Efektivní algoritmy
7
Množinové pokrytí Vstup: Množina M a její pokrytí P Výstup: Minimální podpokrytí Hladový algoritmus N := M; A := ∅; while N ≠∅ do vyber S ∈ P tak, aby |S∩N| bylo maximální N:= N \ S; A := A ∪ {S}; od . Věta: AproxMnožinovéPokrytí(M,P)≤ (ln|M|+1) OPT(M,P).
14.4.2005
UIN009 Efektivní algoritmy
8
Aproximační schéma pro optimalizační problém P je aproximativní algoritmus A, jehož vstupem je instance I problému P a ε > 0 tak, že |A(I)-OPT(I)|/OPT(I) ≤ ε. ε I
A
A(I)
Polynomiální aproximační schéma - jeho časová složitost je omezena polynomem v délce instance. Úplné polynomiální aproximační schéma - jeho časová složitost je omezena polynomem v proměnných n (délka instance) a 1/ε . 14.4.2005
UIN009 Efektivní algoritmy
9
Úplné polynomiální aproximační schéma pro problém batohu Problém batohu (optimalizační verze) Vstup: Množina přirozených čísel S={x1,..., xn}, t ∈ N Výstup: S’⊆ S, ∑ ′ x ≤ t s maximálním ∑ ′ x x∈S
x∈S
Algoritmus dynamického programování (exponenciální) Datové struktury: – L = 〈l1 ,..., lk〉 uspořádaný seznam prvků l1< l2<...
14.4.2005
UIN009 Efektivní algoritmy
10
Problém batohu - exponenciální algoritmus Batoh(S= {x1 ,..., xn}, t ) L0 := 〈0〉 for i:=1 to n do Li := Merge(Li-1 ,Li-1+xi ) odstraň z Li každý prvek > t od return největší prvek v Ln . Časová složitost: O(n⋅t) Příklad: S={1,4,5}, t=7.
14.4.2005
UIN009 Efektivní algoritmy
11
Úplné polynomiální aproximační schéma (Ibarra,Kim,1975) Buď 0< δ <1. Ořezání seznamu L: pro každý odstraněný prvek y musí v L zůstat z tak, aby (1-δ)y ≤ z ≤ y, tj. (y-z)/y ≤ δ. Příklad: δ=0.1, L = 〈10,11,12,15,20,21,22,23,24,29〉.
14.4.2005
UIN009 Efektivní algoritmy
12
Ořezání seznamu Vstup: L=〈y1,...,ym〉, 0<δ<1. Výstup: „ořezaný“ seznam L’ Trim(L,δ) m:= |L|; L’ := 〈y1〉; poslední := y1 for i := 2 to m do if poslední< (1- δ) yi then L’ := 〈L’,yi〉 poslední := yi fi od return L’
14.4.2005
UIN009 Efektivní algoritmy
13
Aproximační schéma AproxBatoh(S,t,ε) n := |S| L0 := 〈0〉 for i:=1 to n do Li := Merge(Li-1,Li-1+xi ) Li := Trim(Li,ε/n) odstraň z Li každý prvek > t od return největší prvek v Ln . Příklad: S={104,102,201,101}, t= 308, ε = 0.2 Věta: AproxBatoh je úplné polynomiální aproximační schéma pro problém batohu. 14.4.2005
UIN009 Efektivní algoritmy
14
