| [Medlem (365WT)]svar [Kinesisk ] | Tid :2017-11-24 | Alle kendte NP-hardproblemalgoritmer har eksponentielle runtider. Imidlertid findes polynomalgoritmer nogle gange, hvis vi søger en "god" snarere end optimal løsning.
I betragtning af et minimeringsproblem og en tilnærmelsesalgoritme vurderer vi algoritmen som følger: For det første, giv en lavere grænse for den optimale løsning, og sammenlign derefter algoritmens løbende resultat med den nederste grænse
Til sammenligning. For maksimeringsproblemet skal du først afgive en øvre grænse og sammenligne algoritmens løbende resultat med den øvre grænse.
De omtrentlige algoritmer indbefatter: mindste spidsdækning, rejseforhandlerproblem, sæt dækning og så videre.
Hidtil har alle NP-komplette problemer ingen polynomaltidsalgoritmer.
For sådanne problemer kan der normalt tages følgende strategier.
(1) Løs kun specifikke forekomster af problemet
(2) ved hjælp af dynamisk programmering eller gren og bundet metode til at løse
(3) Løs med sandsynlighedsalgoritmen
(4) Kun omtrentlig løsning
(5) Brug heuristisk metode til at løse
Hvis den optimale værdi af et optimeringsproblem er c *, er den omtrentlige objektive funktionsværdi af den omtrentlige optimale løsning opnået ved en omtrentlig algoritme til løsning af problemet c,
Prestationsforholdet for tilnærmelsesalgoritmen er defineret som max (c / c *, c * / c). Generelt er dette præstationsforhold en funktion af problemindgangsstørrelsen n
ρ (n), det vil sige max (c / c *, c * / c) ＜= ρ (n).
Den relative fejl tilnærmelse algoritme defineres som Abs [(c-c *) / c *]. Hvis input størrelse n af problemet, der er en funktion [epsilon] (n), således at Abs [(c-c *) / c *] ＜= ε (n), kaldet [epsilon] (n) for den relative tilnærmelse fejlgrænse algoritme. Tilnærmelse algoritme ydelsesforhold mellem ρ (n) og relativ fejlgrænse ε (n) har tilsyneladende følgende
Forholdet: ε (n) ≤ρ (n) -1. |
|
