exponentiell verbessern ...
-
Weiss jemand in welchen Fällen, und wie, man Algorithmen die einen
exponentiellen Zeitaufwand haben, verbessern kann. Bei der Berechnung
des n-ten Fibonacci Gliedes, kann man die ( leicht zu implementierende )
exponentielle Berechnung in eine lineare umwandeln. Auch beim Minmax-
Algorithmus, der bei der Schach-Programmierung vorkommt, wäre eine solche
Verbesserung wünschenswert. Gibt es Literatur bzw Links ?
-
Es gilt als ziemlich gesichert, dass es hierfür kein Patentrezept gibt. Daher sind die üblichen Strategien:
a) Sich kundig machen.
b) Nachdenken.Es kann übrigens auch durchaus herauskommen (bei Strategien a und b), dass besser als exponentiell einfach nicht möglich ist für ein bestimmtes Problem.
P.S.: Und brich deine Zeilen bitte nicht manuell um. Mein (und jeder andere) Browser kann das viel besser als du und kennt auch meine Fenstergröße.
-
GeorgC++ schrieb:
Weiss jemand in welchen Fällen, und wie, man Algorithmen die einen
exponentiellen Zeitaufwand haben, verbessern kann. Bei der Berechnung
des n-ten Fibonacci Gliedes, kann man die ( leicht zu implementierende )
exponentielle Berechnung in eine lineare umwandeln. Auch beim Minmax-
Algorithmus, der bei der Schach-Programmierung vorkommt, wäre eine solche
Verbesserung wünschenswert. Gibt es Literatur bzw Links ?https://www.ads.tuwien.ac.at/w/WS09/186170_Algorithmen_und_Datenstrukturen_2_VO_2.0 die letzten drei Themenblöcke.
MfG SideWinder
-
SeppJ schrieb:
Es gilt als ziemlich gesichert, dass es hierfür kein Patentrezept gibt. Daher sind die üblichen Strategien:
a) Sich kundig machen.
b) Nachdenken.Aber es gibt auch nen ganzen Sack voll Techniken, mit denen man es versuchen kann.
Generell ist das Finden von effizienten, d.h. polynomiellen Algorithmen, Hauptthema des (Forschungs-)Gebiets Algorithmik. Einen Einstieg dazu findet man zum Beispiel in "Introduction to Algorithms" von Cormen et al. Da ist imo nützlich eine Kombination aus möglichst viele grundlegende Algorithmen (Dijkstra, DFS, BFS, Sortieren,...) und möglichste viele grundlegende Algorithmen-Konstruktionstechniken (Dynamische Programmierung, Greedy, Divide&Conquer,...) zu kennen.Man steht jedenfalls nicht völlig allein im Regen.
Bei Problemen, die keine effizienten Algorithmen zulassen (bzw. für die man es nicht hinkriegt) gibt es auch einiges an Techniken, um zumindest exakte exponentielle Algorithmen möglichst schnell zu machen. Der folgende Artikel (Achtung Theorie!) gibt dafür ein paar Ideen: http://www.win.tue.nl/~gwoegi/papers/exact.pdf
