vorige nächste

Verbesserung von brute force


Unsere einfachen Lösungen zeigen alle ein unbefriedigendes Verhalten, wenn man die Zahl der Möglichkeiten vergrößert. Nun kann man vieles an ihnen noch verbessern und manchmal schafft man es mit HGT ein konkretes Problem zu lösen, das man sonst nicht gelöst hätte.

Leider ändern wir nichts am grundsätzlichen Problem der kombinatorischen Explosion. Ohne eine völlig neue Strategie müssen wir für die Berechenbarkeit größerer Probleme feststellen: Geht nicht! Die Suchräume sind bei größeren Problemen so schnell so groß, dass man an der Rechenzeit scheitert. Dabei haben wir uns mit den z.B. in allgemeinen Graphen auftretenden Problemen wie Zyklen und Endlichkeit noch nicht einmal beschäftigt.


Aufgabe zur Berechenbarkeit

  1. Berechnen Sie mit Hilfe einer Tabellenkalkulation die Zahl der Möglichkeiten für ein Problem mit je 4 Möglichkeiten je Stufe für 5 10 15 20 .. Stufen und stellen Sie diese in einem Diagramm dar!
  2. Weshalb gibt es Schwierigkeiten?
  3. Was ändert sich daran, wenn man 2 oder 10 Verzweigungen hat?