uni/algodat/report4567/p6-fragestellungen.md

P6 Fragestellungen

Probleminstanz 9

In Abb.7 und Abb.8 sind die Lösungen für Probleminstanz 9 abgebildet, wobei Probleminstanz 9 jeweils mit einem naiven oder einem dynamic Ansatz gelöst worden ist. Um die Korrektheit zu überprüfen, müssten alle Kombinationen (mit wiederholten Seillängen) die insgesamt eine Länge von 9 ergeben betrachten. Aber um die Plausibilität grob zu befürworten, können wir jeweils Seilpaare betrachten, die auf eine Länge von 9 kommen. Es gilt $w_6 + w_3 > w_9, w_6 + w_3 > w_8 + w_1, w_6 + w_3 > w_7 + w_2, w_6 + w_3 > w_5 + w_4$. Es gibt natürlich noch eine ganze Vielfalt an Kombinationen, weil Seillängen wiederholt werden können, aber diese Kombinbationen haben auch einen geringeren Wert, wie beispielsweise $w_6 + w_3 > 9 \cdot w_1, w_6 + w_3 > 4 \cdot w_2 + w_1$, usw..

Beide Abbildungen übereinandergestellt zeigen, dass der naive und dynamische Ansatz auf dieselbe Lösung kommen.

Naiver Ansatz

Für den naiven Ansatz wurde eine simple top-down Rekursion verwendet, bei welcher die Auswahl jeder Seillänge ein rekursives Entscheidungsproblem darstellt. In jedem Schritt wird ein Element entweder genommen oder nicht genommen. Bei einem 0-1 Rucksack Problem, würde in beiden Fällen die Suche das gerade betrachtete Element ignorieren können und der Suchraum dadurch eingeschränkt werden. Aber da Seillängen wiederholt genommen werden können, handelt es sich hier um das Bounded Rucksack Problem. Der markante Unterschied liegt allein im rekursiven Aufruf, der geschieht, wenn ein Element genommen wird. Ist der Index des gerade betrachteten Elements $i$, so kann beim 0-1 Rucksack Problem der Suchraum auf $(i, n]$ eingeschränkt werden. In dieser Variante muss nachdem ein Element genommen wird rekursiv wieder der gesamte Suchraum $[1, n]$ betrachtet werden.

Dynamischer Ansatz

Für einen dynamischen Ansatz wird im Allgemeinen von Speicher gebraucht gemacht, um das wiederholte Berrechnen von Lösungen zu verhindern. Hier wurde aber dagegen entschieden, den top-down rekursiven naiven Ansatz dynamisch zu machen und alternativ ein bottom-up iterativer Ansatz dynamisch implementiert. Dabei gibt es nun ein zweidimensionales Array int[][] solution, welches ein $l$ großes Array für jede Seillänge mit Preis hat, wobei $l$ die maximale Länge darstellt. Die Lösung wird nicht wie beim naiven Ansatz on-the-fly aus Vergleichen der Teillösungen integriert, sondern jede Teillösung wird in solution eingetragen und die gesamte Lösung später durch backtracking extrahiert.

Laufzeit

Wie leicht erkennbar ist, outperformed der dynamische Ansatz den naiven um Größenordnungen. Das lässt sich dadurch erklären, dass beim naiven Ansatz besonders viele Teilprobleme häufiger auftreten, aber jedes mal neu berrechnet werden müssen. Dasselbe Problem lässt sich bei der trivialen naiven Berrechnung der Fibonacci Zahlen auch beobachten, wenn der rekursive Ansatz $F_{n+2} = Fn + F{n+1}$ ist. Nach nur einem Schritt wird für die Berrechnung von $F_{n+1}$ nämlich $F_n$ aufgerufen, und wir haben zwei identische voneinander unabhängige call stacks. Durch speichern der Zwischenergebnisse, lässt sich dieses Problem intelligent umgehen.