Für eine bestimmte Person i steht in m_ij, wie sehr sie die Person j nicht leiden kann. Je höher der Wert, desto größer die Abneigung.

Gesucht ist eine Positionierung der n Personen in einem 2-dimensionalen Koordinatengitter, das ich mir unbegrenzt vorstelle.

Die Gitterpunkte haben ganzzahlige Koordinaten.
Die Personen i = 1, ..., n werden auf den Gitterpunkten beliebig verteilt. Erlaubt ist sogar, daß 2 Personen auf eine Gitterpunkt kommen. Wenn sich Person i im Gitter an (x₁,y₁) und Person j an (x₂,y₂) befindet, dann soll der Abstand der Gitterpunkte den gegenseitigen Präferenzen entsprechen.
Wie definieren wir den Abstand?
Der Aufgabe entsprechend sollten benachbarte Gitterpunkte den Abstand 1 haben.
Welche Gitterpunkte sind z.B. mit (2,2) benachbart?
Auf jeden Fall die Gitterpunkte (1,2),(2,3),(3,2),(2,1) den Abstand 1 haben.
Wie ist es mit (1,1),(1,3),(3,1) und (3,3)? Abstand 1 oder Abstand 2?
Man muß sich entscheiden, wenn die Aufgabe das offen läßt.
Und (2,2) hat von (2,2) sinnvollerweise den Abstand 0.

Ich definiere den Abstand d(p₁,p₂) zweier Gitterpunkte p₁=(x₁,y₁) und p₂=(x₂,y₂) als

d(p₁,p₂) := |x₁-x₂|+|y₁-y₂|

Sei p_i jetzt der Gitterpunkt, an dem Person i sich befindet.

Der Abstand zweier Personen i und j ist d(p_i,p_j) und dieser Abstand soll möglichst nahe an m_ij und m_ji liegen.

Für 'möglichst nahe' konstruiere ich eine Zielfunktion

z = S_i=1ⁿ S_j=1ⁿ |m_ij-d(p_i,p_j)|

Eine Anordnung der Personen mit minimalem z hat auf jeden Fall eine Stabilitätseigenschaft.
Ich nenne einen Zustand stabil, wenn durch eine Bewegung einer Person um einen Schritt kein besserer z-Wert erreicht werden kann.

Es ist nicht ausschließbar, daß es stabile Zustände gibt, die nicht optimal sind. So ein Zustand ist vergleichbar der Suche nach einem Maximum einer Funktion mit numerischen, iterativen Methoden, bei der man schließlich an ein lokales Maximum kommt, das aber nicht das absolute Maximum ist.

Soweit der theoretische Teil.

Im praktischen Teil muß man nun versuchen eine optimale Lösung zu finden.
Die Frage ist zunächst, ob nur für dieses eine Problem (mit der gegebenen Matrix) eine Lösung gesucht wird, oder ob ein allgemeines Verfahren gewünscht wird.

Dafür gibt es sicher viele Methoden. Eine einfache ist:

Algorithmus 1
Iteration ausgehend von einer beliebigen Anfangsaufstellung, z.B. p_i = (0,0) für alle Personen.
Dafür könnte man ein einfaches Programm schreiben, das für jede Person die Änderung des z-Wertes durch eine Bewegung um 1 prüft. Wenn der neue z-Wert kleiner ist, dann führe den Schritt aus und prüfe dann einen Schritt der nächsten Person; ansonsten lasse die Person auf ihrem Platz. Abbruchbedingung: Wenn ein kompletter Durchlauf über alle n Personen keine Veränderung mehr ergeben hat, das ist: wenn ein stabiler Zustand erreicht ist.

Man kann gewiß Beispiele konstruieren, für die dieses einfache Verfahren nicht die optimale Lösung findet, weil es an einem lokale Minimum 'gestrandet' ist, aber ohne die gleichzeitige Bewegung mehrerer Personen der z-Wert nicht verbessert werden kann.

So, nun sind weitere Vorschläge gefragt, wie man das Verfahren verbessern kann oder welche anderen Verfahren besser sind.

Optimierung, d.h. die Suche nach der "besten" Lösung einer veränderlichen Größe, ist Teil unseres täglichen Lebens. Ständig sind wir auf der Suche nach einem möglichst kleinen (Minimum) oder möglichst großen Wert (Maximum): Wie komme ich am schnellsten nach Hause? Wo gibt es das billigste Benzin? Was ist der kürzeste Weg zum Kino? Meist denken wir gar nicht darüber nach, dass wir Optimierungsstrategien anwenden und handeln intuitiv. In der Wirtschaft und in der Industrie ist es aber wichtig, die beste Lösung eines Problems exakt ermitteln zu können oder wenigstens die optimale Lösung möglichst gut anzunähern. Nicht optimierte Verfahren kosten Zeit und Geld. Hier kann die mathematische Disziplin der Optimierungtheorie helfen. Bis vor Kurzem war es fast unmöglich, rechentechnisch realisierbare Algorithmen für komplexe Probleme anzugeben: Die Programmierung war zu aufwendig, die Rechenleistung nicht ausreichend. Erst durch die Entwicklung neuer Algorithmen und durch den Einsatz moderner leistungsstarker Computer können nun immer kompliziertere Aufgaben in kürzester Zeit gelöst werden. Einer dieser neuen Algorithmen ist der Sintflutalgorithmus.

Optimierung für n Personen.

Wähle n=2, trage die Sympathiewerte der beiden ein. Starte 'run'.
Die gefundene Aufstellung ist optimal.

Lasse die nächste Person den Partyraum betreten, d.h. setze n=3 und klicke 'Aktualisieren'. Trage die Sympathiezahlen der 3-ten Person ein und die Sympathiewerte der ersten 2 Personen bzgl. der 3-ten Person ein. Setze den Startpunkt der Person auf (-5,-5) [die Position der Tür, durch die der Raum betreten wird.] Starte 'run'. Gefunden wurde eine optimale Lösung (die also der unteren Schranke entspricht).

Lasse nun sukzessive Person um Person in den Raum. Für jede Person trage die Sympathiewerte ein und setze ihre Startposition auf (-5,-5) [oder einen anderen Wert weit draußen, auf jeden Fall einen Wert der von allen vorhandenen Personen großen Abstand hat]. Starte 'run'.
Überraschenderweise habe ich für mein Übungsbeispiel mit n=5 eine optimale, nicht verbesserbare Aufstellung gefunden.

.

Wenn man alle Personen bei (0,0) starten läßt, wird das Optimum nicht gefunden.