Die Brücken ...

Insgesamt benutzt Zeynep 14 Baumstämme, um Brücken für einen Weg vom Start zum Ziel bauen. Ginge es auch mit weniger Stämmen? Dazu müssen alle möglichen Wege untersucht werden. Weil die alle über die lange Insel in der Mitte führen, lässt sich das Problem in zwei Teile zerlegen: Von der linken Insel zu Insel in der Mitte, und von ihr zum Ziel:

Für die erste Hälfte hat Zeynep 8 Stämme benutzt und kam ohne Stamm an. Wir notieren ihren Weg so: 2-[2,2]-4. Ein Weg mit weniger Stämmen wäre 3-4, kann aber nur mit Umweg gebaut werden (3-[2,2]-4), verbraucht also 9 Stämme, wobei Zeynep in der Mitte mit einem Stamm im Vorrat ankommt. Alle anderen Wege verbrauchen 9 Stämme oder mehr.

Für die Brücken der zweiten Hälfte hat Zeynep 6 Stämme benutzt. Den direkten Weg 3-2 kann sie nicht bauen, auch nicht mit einem Stamm im Vorrat. Alle anderen Wege verbrauchen 6 Stämme oder mehr.

Es ist also nicht möglich, mit weniger als 14 Stämmen Brücken zu bauen, der Brückenbau ist also korrekt.

Die Insel-Karte mit den durch Linien angezeigten „Brücken-Bauplätzen“ kann als Graph modelliert werden: Das ist eine mathematische Struktur, die Objekte (auch Knoten genannt) paarweise miteinander in Relation setzt (die Paare nennt man auch Kanten). In einem Graphen man die Inseln als Knoten und die Linien als Kanten modellieren. Dabei haben die Kanten Gewichte, nämlich die Anzahl der für den Brückenbau entlang einer Linie benutzten Baumstämme, aber auch die Knoten (die Anzahl der Stämme auf einer Insel) – das ist eher ungewöhnlich. Für Graphen, bei denen nur die Kanten gewichtet sind, kennt die Informatik mehrere effiziente Algorithmen, die einen kürzesten Weg (über Kanten mit minimaler Summe der Gewichte) zwischen zwei Knoten berechnen können.

Das Problem, das Zeynep in dieser Challenge optimal lösen möchte, ist komplizierter: Sie möchte zwar auch einen kürzesten Weg gehen, hat aber eine Randbedingung: Die Summe der Knotengewichte auf ihrem bisherigen Weg (die Stämme, die sie nehmen konnte) abzüglich der Summe der Kantengewichte auf ihrem Weg (die Stämme, die sie für den Brückenbau benutzt hat) muss größer sein als das Gewicht der Kante, die sie als nächste gehen bzw. wo sie eine Brücke bauen möchte. Um den optimalen Weg zu finden, müssen hier eventuell alle Möglichkeiten ausprobiert werden. Die Zerlegung des Problems in zwei Teile hilft, die Anzahl der Möglichkeiten zu reduzieren. Und wegen der Randbedingung kann man viele Möglichkeiten ausschließen, bevor man sie komplett probiert hat. In der Informatik ist ein solches Vorgehen (Probieren und Ausschließen) als Backtracking bekannt.