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
- sich ohne Parameter starten lässt (z.B. »java
HashZahlen«),
- irgendwann fertig wird (sagen wir, nach etwa 5 Minuten),
- optimale Lösungen für n=5,6,7,8,9,10 ausgibt,
- mit einer zutreffenden Abbruchbedingung dafür, wann weiteres
Suchen nicht mehr erfolgreich sein kann (vgl. Beschreibungen der beiden
Ansätze)
- und einer Begründung der Korrektheit der Abbruchbedingung.
Die Zahlen allein reichen nicht! Nur für ein Programm gibt es
Punkte!
Und sonst...
- Aufgabe 24b: Die Lösung ist wieder eine Hash-Funktion. Bitte
mit Nachweis der Injektivität
- Aufgabe 27: Gesucht ist eine Formel zur Bestimmung der t1,...,tn:
Bitte ebenfalls mit Nachweis der Injektivität und mit einer
asymptotischen Analyse der erzielten Summen-Intervalllängen.
- Aufgabe 28: Der modifizierte Quelltext reicht.