Idioma :
SWEWE Membre :Login |Registre
Cercar
Comunitat enciclopèdia |Enciclopèdia Respostes |Enviar pregunta |Coneixement de vocabulari |Pujar coneixement
preguntes :Què és l'algoritme d'aproximació?
Visitant (152.118.*.*)[Anglès ]
Categoria :[Ciència][Un altre]
He de respondre [Visitant (54.160.*.*) | Login ]

Imatge :
Tipus :[|jpg|gif|jpeg|png|] Byte :[<2000KB]
Idioma :
| Comproveu el codi :
Tots respostes [ 1 ]
[Membre (365WT)]respostes [Xinès ]Temps :2017-11-24
Tots els algoritmes de problema NP-hard coneguts tenen temps d'execució exponencials. No obstant això, si estem buscant una solució "bona" ​​en comptes de la solució òptima, hi ha de vegades algoritme polinòmic.

Donat un problema de minimització i un algoritme d'aproximació, es va avaluar l'algoritme de la següent manera: En primer lloc, un límit inferior en la solució òptima, llavors el resultat de l'operació d'algorisme a aquest límit inferior

Per a la comparació. Per al problema de maximització, primer donar un límit superior i executi el resultat de l'algorisme es compara amb el límit superior.

Els algoritmes aproximats inclouen: cobertura mínima de vèrtex, problema del venedor de viatges, configuració de cobertura, etc.

Fins ara, tots els problemes NP-complets no tenen algorismes de temps polinòmic.
Per a aquests problemes, en general es poden prendre les següents estratègies.

(1) Resoldre només instàncies específiques del problema

(2) utilitzant la programació dinàmica o la branca i el mètode enllaçat per resoldre

(3) resoldre amb l'algoritme de probabilitat

(4) Només una solució aproximada

(5) Utilitzeu el mètode heurístic per resoldre

Si el valor òptim d'un problema d'optimització és c *, el valor de funció objectiu aproximat de la solució òptima aproximada obtinguda per un algoritme aproximat per resoldre el problema és c,

La relació de rendiment d'aquest algorisme d'aproximació es defineix com a màxim (c / c *, c * / c). En general, aquesta relació de rendiment és una funció de la grandària d'entrada del problema n

ρ (n), és a dir, màx (c / c *, c * / c) <= ρ (n).
L'algorisme d'aproximació d'error relativa es defineix com Abs [(c-c *) / c *]. Si la mida d 'entrada núm del problema, hi ha una funció de [èpsilon] (n) de tal manera que els Abs [(c-c *) / C *] <= ε (n), anomenat [èpsilon] (n) per l'algoritme unit error d'aproximació relativa. relació de rendiment algoritme d'aproximació entre ρ (n) i ε unida error relatiu (n) aparentment té la següent

Relació: ε (n) ≤ρ (n) -1.
Cercar

版权申明 | 隐私权政策 | Drets d'autor @2018 Coneixement enciclopèdic del Món