friendster, open BC, kontakte 6. Ebene

[Andreas Müller]

Hallo,
das ist mal ein nettes Problem, aber auf MySQL etwas OT da an sich ein rein
algorithmisches Problem. 

Zunächst sollte man feststellen das es beliebig viele "Ebenen" geben kann
und das man auch eine Rückbezüglichkeit zu beachten hat (A kennt B, B kennt
A).
Je nach dem ob es auch den Fall gibt A kennt B aber B kennt A nicht gibt
muss man das ganze uni- oder bi-direktional betrachten. Unidirektional wäre
natürlich am einfachsten weil dann A kennt B und B kennt A nur eine
Information ist. Hier sollte man sich auf eine Notation (z.B. x<y) einigen
das man später gezielt suchen kann und nicht A,B und B,A testen muss.

Um nun den kürzesten Weg zu finden brauchst du eine rekursive Funktion die
ausgehend von einem Punkt die ihm bekannten Punkte absucht. Von jedem
gefundenen Punkt aus geht es nun rekursiv weiter, d.h. diese werden
ebenfalls durchsucht. Dabei sollte man sich den bereits gegangenen Weg
merken und aufpassen das man nicht im Kreis läuft. Das ganz geht solange
weiter bis du einen Weg gefunden hast. Nun kennst du erstmal einen Weg. Auf
deiner Suche hast du bereits einige Abstände zwischen Punkten merken können
und evtl. durch frühere suchen in einer DB gespeichert:

E->G 2
A->B 1
etc.

Nun kannst du optimieren in dem du unter Zuhilfenahme der bekannten Abstände
oder unter Erforschung neuer Abstände versuchst den einmal gefunden Weg zu
verkürzen.

Es gäbe dazu noch eine alternative, die aber viel Speicherplatz benötigt:
Man kann beim einfügen eines neuen Datensatzes die Abstände gleich
berechnen. So entsteht eine Tabelle mit von,nach,Abstand und du kannst die
Frage später sehr schnell beantworten. Je nach dem ob uni- oder
bidirektional entstehen so n*(n-1)/2 oder n*(n-1) Datensätze.

Immer dann wenn es keinen Weg zwischen 2 Punkten gibt ist das Ansatzpunkt
für weitere Optimierungen. Denn jetzt kann man hergehen und "Wolken"
definieren, d.h. Listen von Punkten die überhaupt miteinander verbunden sein
können. Auch sowas kann man bei der Erfassung der Daten bereits tun und
somit wertvolle Suchzeit sparen. Aber immer dran denken: Ein neuer Kontakt
kann Wolken verbinden.

Prinzipiell glaube ich das so ein Problem NP vollständig ist, kann mich aber
auch gerade irren. Weiteres dazu in guten Algorithmenbüchern :-) 

Gruß,
Andreas


-- 
Infos zur Mailingliste, zur Teilnahme und zum An- und Abmelden unter
-->>  http://www.4t2.com/mysql