Taal :
SWEWE Lid :Login |Registratie
Zoeken
Encyclopedie gemeenschap |Encyclopedie Antwoorden |Vraag indienen |Woordenschat Kennis |Uploaden kennis
vragen :Wat is een approximatiealgoritme?
Bezoeker (152.118.*.*)[Engels ]
Categorie :[Wetenschap][Ander]
Ik moet beantwoorden [Bezoeker (3.88.*.*) | Login ]

Afbeelding :
Type :[|jpg|gif|jpeg|png|] Byte :[<2000KB]
Taal :
| Controle code :
Alle antwoorden [ 1 ]
[Lid (365WT)]antwoorden [Chinese ]Tijd :2017-11-24
Alle bekende NP-harde probleemalgoritmen hebben exponentiële looptijden. Er bestaan ​​echter soms polynomiale algoritmen als we op zoek zijn naar een "goede" in plaats van optimale oplossing.

Gegeven een minimalisatieprobleem en een benaderingsalgoritme, evalueren we het algoritme als volgt: Geef eerst een ondergrens van de optimale oplossing en vergelijk het loopresultaat van het algoritme met de ondergrens

Ter vergelijking. Voor het maximalisatieprobleem geeft u eerst een bovengrens op en vergelijkt u vervolgens het resultaat van het algoritme met de bovengrens.

De geschatte algoritmen omvatten: minimale topdekking, probleem met reisverkoper, ingestelde dekking enzovoort.

Tot nu toe hebben alle NP-complete problemen geen algoritmen voor polynomiale tijd.
Voor dergelijke problemen kunnen meestal de volgende strategieën worden gevolgd.

(1) Los alleen specifieke voorbeelden van het probleem op

(2) met behulp van dynamisch programmeren of branch and bound methode om op te lossen

(3) oplossen met kansalgoritme

(4) Alleen bij benadering oplossing

(5) Gebruik de heuristische methode om op te lossen

Als de optimale waarde van een optimalisatieprobleem c * is, is de geschatte objectieve functiewaarde van de geschatte optimale oplossing verkregen door een benaderend algoritme voor het oplossen van het probleem c,

De uitvoeringsverhouding van dit benaderingsalgoritme is gedefinieerd als max (c / c *, c * / c). Over het algemeen is deze prestatieverhouding een functie van de probleeminputgrootte n

ρ (n), dat is max (c / c *, c * / c) <= ρ (n).
De relatieve fout benaderingsalgoritme wordt gedefinieerd als Abs [(c-c *) / c *]. Indien de invoergrootte n van het probleem, is een functie [epsilon] (n) zodanig dat de Abs [(c-c *) / c *] <= ε (n), genaamd [epsilon] (n) de relatieve benaderingsfout gebonden algoritme. Benaderingsalgoritme prestatieverhouding tussen ρ (n) en relatieve fout gebonden ε (n) blijkbaar de volgende

Relatie: ε (n) ≤ρ (n) -1.
Zoeken

版权申明 | 隐私权政策 | Auteursrecht @2018 Wereld encyclopedische kennis