Beispiele zu Algorithmen in .NET

• Knapsack
• Bi

Knapsack

Dieses Beispiel enthält eine Implementierung eines exakten Enumerationsalgorithmus zur Lösung des 0/1-Rucksackproblems. Beim 0/1-Rucksackproblem geht es darum, aus einer Menge von Gegenständen mit jeweils bestimmtem Gewicht und Wert eine Auswahl zu treffen, die einen maximalen Gesamtwert aufweist, bei der aber die Summe der Einzelgewichte der gewählten Gegenstände ein vorgegebenes Maximalgewicht nicht übersteigt. Gegenstände werden entweder eingepackt oder nicht (daher kommt auch der Name).

Der Algorithmus im Beispiel löst das Problem durch Enumeration. Dabei werden Lösungen schrittweise (iterativ) aufgebaut und jene Konfigurationen, die nicht mehr in den Rucksack passen, ausgeschlossen. Über jeden Gegenstand wird iterativ entschieden, ob er eingepackt wird oder nicht in den Rucksack kommt. Zu jedem Zeitpunkt des Ablaufs wird die beste bisher gefundene Lösung (d. h., jene Konfiguration maximalen Gewichts, die in den Rucksack paßt, und die in der Menge der generierten Konfigurationen enthalten ist) festgehalten. Trifft der Algorithmus auf eine bessere Auswahl, dann wird diese als bisher beste Lösung gespeichert. Nach Durchlauf des Algorithmus erhält man auf diese Weise die optimale Lösung.

Algorithmen, die auf (vollständiger) Enumeration beruhen, also bei denen die Lösung durch Aufzählen und Analysieren aller oder sehr vieler möglicher Lösungen gefunden wird, sind in der Praxis meist nicht einsetzbar. Der hier implementierte Algorithmus hätte bei etwa 30 Gegenständen bereits eine so große Laufzeit, daß er in echten Anwendungen nicht mehr sinnvoll eingesetzt werden kann. Stattdessen kann man auf wesentlich „intelligentere“ Verfahren, die auf beschränkter Enumeration oder dynamischer Programmierung beruhen, zurückgreifen.

Bi

In diesem Beispiel geht es um Algorithmen und die mit der Wahl des richtigen Algorithmus verbundenen Geschwindigkeitssteigerung bei Programmen. Es soll der Binomialkoeffizient, auch bekannt als „$n$ über $k$“ berechnet werden. Der Binomialkoeffizient gibt die Anzahl der $k$-elementigen Teilmengen einer $n$-elementigen Menge an. Zur Berechnung kann man die folgenden Formeln verwenden:

$\left(\begin{array}{c}n\\ k\end{array}\right)=\frac{n!}{k!(n-k)!}=\left(\begin{array}{c}n-1\\ k-1\end{array}\right)+\left(\begin{array}{c}n-1\\ k\end{array}\right)$

Eines der Verfahren benutzt die Lösung mit der Berechnung der Fakultäten. Der Nachteil dieses Verfahrens ist, daß die Werte über und unter dem Bruchstrich sehr groß werden können. So groß, daß sie nicht mehr in einer Variable des entsprechenden ganzzahligen Datentyps (z. B. Integer) Platz finden können. In diesem Fall ist die zweite Methode über das rekursive Berechnen wesentlich besser geeignet, da das Ergebnis durch Summation der Ergebnisse zweier rekursiver Aufrufe berechnet wird. Jedoch hat dieses Verfahren eine sehr hohe Laufzeit, sodaß es in der Praxis für größere Werte für die beiden Parameter nicht mehr benutzt werden kann.

Aus diesem Grund haben wir nach weiteren Möglichkeiten gesucht, den Lösungswert zu berechnen. Ein Verfahren dazu beruht auf dem Verfahren der dynamischen Programmierung. Auch bei diesem Verfahren wird die Lösung durch Summation zusammengebaut, jedoch werden keine sinnlosen Berechnungen durchgeführt. Mit dieser Maßnahme kann erreicht werden, daß die Laufzeit auch für größere $n$ und $k$ in einem akzeptablen Rahmen bleibt.