Hinweise zu Aufgabenblatt 4

Aufgabe 23

Zunächste einmal muss man verstehen, was überhaupt zu tun ist. Eine Hash-Funktion ordnet einem Objekt eine ganze Zahl zu, wobei für je zwei verschiedene Objekte die zugeordneten Zahlen auch verschieden sein müssen, die Funktion ist also injektiv. Bei den Objekten handelt es sich in dieser Aufgabe um ungeordnete Paare {i, j}, wobei immer 1<=i<j<=n gelten soll. Die Hash-Funktion wollen wir mit Hilfe von Zahlen t1,...,tn bilden, nämlich nach der Vorschrift: h({i, j}) = ti+tj. Um die geforderte Injektivität sicherzustellen, müssen alle paarweisen Summen ti+tj. verschieden sein. Das ist die hinreichende und notwendige Bedingung. Eine Lösung für n=3 lautet beispielsweise t1=1, t2=3, t3=5. Als paarweise Summen regeben sich: 1+3=4, 1+5=6, 3+5=8.

Für jedes n gibt es unendlich viele Lösungen. Für eine Hash-Funktion ist es jedoch sinnvoll, wenn ihre Funktionswerte möglichst nah beeinander liegen. Oder genauer: Wenn man das Intervall, welches alle Funkionswerte enthält, möglichst klein machen kann. Also ein Optimierungsproblem. In unserem Beispiel muss die Differenz zwischen der kleinsten Summe und der größten Summe möglichst klein sein. Diese Differenz lautet im obigen Beispiel 8-4=4. Eine optimale Lösung für n=3 lautet beispielsweise t1=1, t2=2, t3=3. Als paarweise Summen ergeben sich: 1+2=3, 1+3=4, 2+3=5, die Differenz liegt bei 5-3=2, die Intervalllänge ist 1 größer, also 3.

Wie geht man vor? Das Problem ist ähnlich wie das Achtdamenproblem, mit dem Unterschied, dass man über die Summen-Intervallänge optimieren soll. Es lässt sich auch ähnlich programmieren, nämlich durch backtracking. Man fängt mit einer leeren Lösung (Lösung: Folge t1,...,tn) an, mit der man die rekursive Funktion aufruft. Diese geht nun alle theoretischen Möglichkeiten durch, eine weitere Zahl hinzuzufügen. Falls sich für eine Möglichkeit ergibt, dass zwei Summen gleich sind, lassen wir sie fallen. Falls die Summen nicht kollidieren, Fügen wir die Zahl zur Lösung hinzu und rufen wieder die rekursive Funkion auf. Wenn wir bei einem Aufruf auf Tiefe n angekommen sind, haben wir eine Lösung für n gefunden.

Und wie optimiert man? Da gibt es verschiedene Möglichkeiten. Eine ist, dass man zunächst versucht, eine Lösung zu finden, zwischen deren Summen es keine Lücken gibt, deren Summen also in ein Intervall der theoretisch kleinsten Länge von n*(n-1)/2 passen (Achtung! Druckfehler bei A24b). Für n=2, 3 und 4 gibt es solch eine Lösung, für größere n nicht mehr. Man findet also beim ersten Durchlauf keine Lösung, erhöht d dann Schritt für Schritt, bis man einmal geeignete Zahlen gefunden hat, deren Summen in das Intervall der Länge d passen. Das Problem hierbei ist, wie man einen Backtracking-Algorithmus finden kann, der irgendwann feststellt, dass alle theoretischen Möglichkeiten für die Zahlen t1,...,tn, aus denen sich eine Lösung mit Intervalllänge d ergeben könnte, schon durchprobiert wurden. Hierzu überlege man sich, wie groß bei gegebener Summen-Intervalllänge d die Differenz tn-t1 maximal sein kann. Oder andersrum: Wenn ich n Zahlen habe mit z.B. t1,=1 und tn=100, wie groß muss die Summen-Intervalllänge dann mindestens sein? Könnte sie kleiner als 100 sein? Wovon hängt das ab?

Oder man sucht zunächst Lösungen beliebiger Güte, bis man sicher sein kann, dass man keine bessere mehr finden kann. Man fängt z.B. mit Zahlen t1=1 und tn=2 an, und versucht, auf die richtige Lösung zu kommen, indem man die fehlenden n-2 Zahlen dazwischen einordnet. Zwischen 1 und 2 ist natürlich nicht genug Platz, also erhöht man tn um 1 und probiert es wieder. Nun passt die 2 dazwischen, und im Falle n=3 hätten wir bereits die Lösung. Na gut, man erhöht weiter und weiter. Bis man eine Lösung findet. Die erste Lösung (die mit dem kleinsten tn) ist jedoch nicht immer die beste. man sucht also weiter. Wann kann man aufhören? Dafür braucht man eine ähnliche Abbruchbedingung wie oben. Der Vorteil an diesem Verfahren ist, dass man auf der Suche nach einer Lösung für n nebenher auch Lösungen für 2,3, ... ,n-1 bekommt.

Noch Fragen? Eine Frage wäre z.B., warum man einfach t1=1 setzen kann. Verpasst man so nicht mögliche Lösungen? Oder: Wieso reicht es nicht aus, eine Lösung mit möglichst kleinem tn zu finden? Ist dann nicht logischerweise auch die Summen-Intervallänge kleinstmöglichst? Warum das nicht der Fall ist, überlege man sich als weiteren Einstieg in die Problemstellung.

Wenn ihr einen Algorithmus gefunden habt, müsst ihr ihn auch implementieren. Der zeitkritische Teil des Algorithmus ist der rekursive Aufruf. Man hat eine Teillösung, der man eine weitere Zahl hinzufügen möchte. Dazu muss man die sich neu ergebenden Summen mit den alten vergleichen. Falls sich keine Kollision ergibt, fügt man die neuen Summen hinzu. Wenn man in der Rekursion wieder zurückspringt, entfernt man sie wieder. Für die Summen überlege man sich eine geeignete Repräsentation. Am einfachsten ist es, alle der Reihe nach in ein int-Array zu schreiben. Aber dann ist das Vergleichen sehr teuer, da man das ganze Array durchgeht. Das Vergleichen ist günstig, wenn man das Array sortiert (vgl. Arrays.sort(), Arrays.binarySearch()) oder z.B. ein HashSet verwendet. Aber dann ist das Wegnehmen wieder schwierig. Oder man erzeugt vor jedem Rekursionsaufruf eine Kopie des Teillösungsobjektes, dann braucht man keine Summen zu entfernen, man vergisst einfach das Objekt und erinnert sich an das vorige. Oder man macht es noch anders. Das Problem ist eine schöne Spielwiese, um ein Gefühl für Vor- und Nachteile der verschiedenen Varianten zu bekommen. Einfach mal ausprobieren. Meine erste Implementation hatte ungefähr 5 Minuten Laufzeit. Nach diversen Optimierungen sind es nur noch 7 Sekunden (Prozessor: P4).

Nun zu den Anforderungen. Ich erwarte von euch ein Programm in Java oder Haskell, welches
  1. sich ohne Parameter starten lässt (z.B. »java HashZahlen«),
  2. irgendwann fertig wird (sagen wir, nach etwa 5 Minuten),
  3. optimale Lösungen für n=5,6,7,8,9,10 ausgibt,
  4. mit einer zutreffenden Abbruchbedingung dafür, wann weiteres Suchen nicht mehr erfolgreich sein kann (vgl. Beschreibungen der beiden Ansätze)
  5. und einer Begründung der Korrektheit der Abbruchbedingung.
Die Zahlen allein reichen nicht! Nur für ein Programm gibt es Punkte!

Und sonst...