[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. |
|