Optimaliseringsproblem

I tilfelle et optimaliseringsproblem , gis et løsningsrom (sett med mulige løsninger) og en evalueringsfunksjon (også mål- eller treningsfunksjon) . Man ønsker å finne en løsning med størst mulig verdi , eller komme med uttalelser om verdiene til løsningene. ${\ displaystyle \ Omega}$${\ displaystyle f \ colon \ Omega \ rightarrow \ mathbb {R}}$${\ displaystyle x \ in \ Omega}$${\ displaystyle f (x)}$

I dette tilfellet ville det være et maksimeringsproblem , med et minimeringsproblem søkes det løsninger med minst mulig , men denne saken kan reduseres til den forrige ved ganske enkelt å negere . ${\ displaystyle x}$${\ displaystyle f (x)}$${\ displaystyle f}$

Det skilles mellom tre problemer:

• Beslutningsproblemer der det også er en grenseverdiog det bør avgjøres om det er enmed.${\ displaystyle g \ in \ mathbb {R}}$${\ displaystyle x \ in \ Omega}$${\ displaystyle f (x) \ geq g}$
• faktiske optimaliseringsproblemer som du vil vite verdien av den beste løsningen, altså .${\ displaystyle \ max \ {f (x) \ mid x \ in \ Omega \}}$
• Søkeproblemer som detsøkesetter en optimal løsning for(), eller en løsning med en gitt minimumskvalitet, dvs. enmed. Eller du vil bare finne en best mulig løsning (tilnærming).${\ displaystyle o \ in \ Omega}$${\ displaystyle f (o) = \ max \ {f (x) \ mid x \ in \ Omega \}}$${\ displaystyle o}$${\ displaystyle f (o) \ geq g}$

I teoretisk informatikk betyr et optimaliseringsproblem vanligvis et faktisk optimaliseringsproblem, der bare den best mulige verdien og ingen løsning i seg selv blir søkt. Spesielt tilfelle av en diskret evalueringsfunksjon blir også vanligvis vurdert, da dette vanligvis ikke utgjør noen vesentlig forskjell og reelle tall er mindre enkle å håndtere, f.eks. B. omtrent som flytende tall . ${\ displaystyle f \ colon \ Omega \ rightarrow \ mathbb {N}}$

For det meste vurderer man imidlertid beslutningsproblemer innen teoretisk informatikk. Et beslutningsproblem kan enkelt genereres for et optimaliseringsproblem ved å legge til grenseverdien eller til problemet . Motsatt, for de fleste praktisk interessante problemer, kan man vise at en løsning for beslutningsproblemet kan modifiseres til en løsning for det tilsvarende søke- eller optimaliseringsproblemet som ikke krever betydelig mer databehandlingstid eller lagringsplass. ${\ displaystyle g \ in \ mathbb {R}}$${\ displaystyle g \ in \ mathbb {N}}$

I praktisk bruk må du vanligvis håndtere søkeproblemer, fordi verdien av en optimal løsning vanligvis ikke nytter for deg uten kjennskap til denne løsningen. En algoritme som løser et optimaliseringsproblem kalles en optimaliseringsalgoritme . På samme måte blir minimerings- og maksimeringsproblemet mer presist referert til som minimerings- eller maksimeringsalgoritmen. En algoritme som omtrent løser et optimaliseringsproblem kalles en tilnærmelsesalgoritme , men ofte også noe upresis som en optimaliseringsalgoritme.

Se også

• Optimalisering (matematikk)
• Evolusjonær algoritme

weblenker

• Litteratur om optimaliseringsproblemet i katalogen til det tyske nasjonalbiblioteket