Vertragstheorie Eine Einführung mit finanzökonomischen Beispielen und Anwendungen 2005, XVI, 218 S. Basler, Herbert Grundbegriffe der Wahrscheinlichkeitsrechnung und Statistischen Methodenlehre

2.1.3 Heuristiken

Die oben getroffenen Aussagen zur Schwierigkeit der L¨

osung gewisser Prob-

lemstellungen lassen teilweise eine Relativierung des L¨

osungsbegriffes als

zweckm¨

aßig erscheinen. Bei der Definition

”

Probleme, f¨

ur deren L¨

osung ein

polynomialer Algorithmus existiert, werden als effizient l¨

osbar bezeichnet“,

wird in der Regel implizit zu Grunde gelegt, dass mit L¨

osung die exakte Be-

stimmung einer optimalen L¨

osung gemeint ist. Aus den obigen Darlegungen

ergab sich, dass es auch unter Nutzung leistungsf¨

ahigster Rechner prinzipiel-

le Grenzen des theoretisch wie auch praktisch Machbaren gibt. Damit bleibt

f¨

ur die praktische L¨

osung gewisser Probleme in der Regel nur die Aufga-

be bzw. die Vernachl¨

assigung des Optimalit¨

atskriteriums. Man begn¨

ugt sich

dann mit approximativen Verfahren, so genannten Heuristiken, die effizient

(d. h. mit polynomialem Rechenaufwand) ¨

uber die Anwendung als sinnvoll

erachteter Vorgehensweisen systematisch m¨

oglichst gute, aber gegebenenfalls

nicht optimale L¨

osungen erzeugen.

Aus praktischer Sichtweise mag f¨

ur ein gewisses Anwendungsbeispiel die

Bestimmung einer zul¨

assigen L¨

osung mit der Garantie, dass diese h¨

ochstens

1% vom optimalen Zielfunktionswert entfernt liegt, vollkommen ausreichend

sein – auch im Hinblick auf eine im Allgemeinen vorhandene Ungenauig-

keit der Eingabedaten wie auch der Problemmodellierung. Demzufolge ist

die komplexit¨

atstheoretische Untersuchung von approximativen Algorithmen

oder heuristischen Verfahren ein wichtiger praxisrelevanter Forschungsbe-

reich. Selbst wenn es auch hier theoretische Aussagen z. B. dahingehend gibt,

dass die Approximationsg¨

ute effizienter Verfahren f¨

ur gewisse Problemstel-

lungen im Worst Case nicht beliebig gesteigert werden kann, sind solche Aus-

sagen f¨

ur praktische Probleme doch nur bedingt gewichtig. So relativieren die

Erfolge von modernen heuristischen Verfahren (so genannten Metaheuristi-

ken) wie u. a. Genetische Algorithmen und Tabu Search bei der Anwendung

auf praktische Problemstellungen die theoretischen Aussagen doch in einem

gewissen Maße; vgl. z. B. Rayward-Smith et al. (1996) oder Voß et al. (1999).

---

2.2 Codierung von Informationen als Daten

23