IMIT25A SGD/ ILS

1. Bei der Einführung zum Thema Suche wurde ausführlich das Wasserproblem behandelt. Mit den beiden 5- und 4-Liter-Eimern ist es gelungen, die Mengen von 0, 1, 3,
4 und 5 Liter zu erreichen.
Ist es möglich, 2 Liter zu bekommen? Wenn ja, schreiben Sie die kürzeste Aktionsreihenfolge mit den jeweiligen Knoten (Zuständen) auf!
15 Pkt.
2. Wie lange wird der schnellste Superrechner Sunway TaihuLight brauchen, um alle
praktisch möglichen Stellungen auf einem internationalen Go-Brett zu errechnen?
Gehen Sie vereinfacht davon aus, dass pro FLOP (1 Sekunde) eine Stellung errechnet
wird. Geben Sie alle Rechenschritte mit an!
15 Pkt.
3. Untersuchen Sie, ob beim Wasserproblem die Tiefen- oder Breitensuche schneller
zum Ergebnis der gesuchten 3 Liter führt. Berücksichtigen Sie bei der Lösung nur die
Knoten, die auch in den Abbildungen vorhanden sind und zählen alle Einzelschritte,
die zu den Knoten hinführen (auch Rückläufer). Entfernen Sie vorher alle doppelten
Knoten! Geben Sie als Lösung auch die erforderlichen Schritte bei den beiden Suchverfahren an.
30 Pkt.
4. Vorgegeben sei folgendes 8-Schiebepuzzle:
Entwickeln Sie einen Suchgraphen („Wasserproblem“), der zum folgenden Ziel führt:
Geben Sie alle Knoten an, die durchsucht werden. Verschieben Sie zuerst die „7“ für
den linken Teilgraphen. Für den mittleren Teilgraphen verschieben Sie als Start die
„6“ und für den rechten Knoten die „5“.
30 Pkt.
5. Wie lautet der empfohlene h-Wert bei einer maximalen Entfernung von 98 km zwischen zwei Städten, wenn insgesamt 7 Städte besucht werden sollen?
10 Pkt.