- Es gibt n Knoten (normalerweise irgendwas zwischen 100 und im mittleren 5stelligen Bereich)
- Jeder Knoten hat m Verbindungen zu anderen Knoten (m >= 2, m < 20)
- Ich benötige die Verbindung(en) zwischen zwei wahlfrei herausgegriffenen Knoten
Jan
Moderator: Moderatoren
Das heißt, Du suchst nach der kürzesten Verbindung?Jan hat geschrieben:Es gibt sowas ähnliches z. B. in Xing, wo mir angezeigt wird, über wie viele Zwischenstufen ich mit jemandem anderen bekannt bin.
Ein Top Beispiel für eine mehr als sinnvolle rekursive Lösung .Tom hat geschrieben:Kann man rekursiv machen.
Jup. Die Funktion "KenntXdiePersonY(x,y)" ruft sich, wenn kein Treffer gefunden wurde (also y nicht unter den Ergebnissen war), mit den bekannten Personen von x (!) wieder selbst auf, bis nichts mehr gefunden wird oder das y unter den Treffern war. Da es vermutlich Kreuzverbindungen gibt, muss sie sich lediglich merken, wer bereits gefunden worden ist* - und für diese Personen dann nicht mehr weitersuchen. Oder wenn eine bestimmte Suchtiefe erreicht wurde, die auch eine Begrenzung darstellen kann (maximal 5 Stufen o.ä.).Ein Top Beispiel für eine mehr als sinnvolle rekursive Lösung
Code: Alles auswählen
FUNCTION KnotenNachbarn( K ) // Liefert Array mit allen direkten Nachbarknoten zurück
..
RETURN( aNachbarn )
FUNCTION KnotenNachbarnTeilmenge( K,aOhneKnoten ) // Liefert Array mit allen direkten Nachbarknoten ohne die aus aKnotenErreicht zurück
LOCAL aNachbarn,I
aNachbarn := KnotenNachbarn( K )
FOR I = len( aNachbarn ) TO 1 STEP -1
IF .NOT. empty( aOhneKnoten,aNachbarn[I] ) // Diesen Knoten aus aNachbarn eliminieren
ARemove( aNachbarn )
ENDIF
NEXT I
RETURN( aNachbarn )
FUNCTION Knotenentfernung( K1,K2,nLevel,aKnotenErreicht,xMaxLevel )
LOCAL xResult,aNachbarn,I,xResult2
DEFAULT nLevel := 0
DEFAULT aKnotenErreicht TO {}
IF K1==K2 // Entfernung bestimmt
xResult := nLevel
ELSEIF nMaxLevel<>NIL .AND. nLevel>=nMaxLevel
xResult := NIL // Es gibt schon eine kürzere Entfernung, diese Suche abbrechen!
ELSE
aNachbarn := KnotenNachbarnTeilmenge( K1 ) // Den Weg von K1 zu K2 suchen
IF AScan( aNachbarn,K2 ) // Weg gefunden!
xResult := nLevel+1
ELSE
AEval( aNachbarn,{|K,J|AAdd( aKnotenErreicht,K } ) // Alle Nachbarknoten in aKnotenErreicht eintragen
FOR I := len( aNachbarn ) TO 1 STEP -1
xResult := Knotenentfernung( aNachbarn[I],K2,nLevel+1,@aKnotenErreicht,nMaxLevel,xResult/*xMaxLevel*/ )
// xResult<>NIL: ein Ergebnis gefunden! Wenn I>1 noch nach besseren Lösungen suchen!
NEXT I
ENDIF
ENDIF
RETURN( xResult ) // Wenn xResult==NIL: dann gibt es keine Lösung :-(
FUNCTION Main()
....
? Knotenentfernung( 3,3 ) // Entfernung zwischen Knoten 3 und 3 ausgeben: = 0 :-)
? Knotenentfernung( 3,7 ) // Entfernung zwischen Knoten 3 und 7 ausgeben
...
RETURN( 0 )
Ja, dann sind wir wieder eher bei einer iterativen Lösung. Wenn ich darüber nachdenke, vermute ich, dass obiger Algorithmus vermutlich korrigiert werden muß:brandelh hat geschrieben:Für deine obige Lösung wäre also ein Ansatz sinnvoll, bei dem alle möglichen Kombinationen einer Ebene abgearbeitet werden, bevor es in eine tiefere Ebene geht.
Code: Alles auswählen
AEval( aNachbarn,{|K,J|AAdd( aKnotenErreicht,K } ) // Alle Nachbarknoten in aKnotenErreicht eintragen
nLen := len( aKnotenErreicht )
FOR I := len( aNachbarn ) TO 1 STEP -1
xResult := Knotenentfernung( aNachbarn[I],K2,nLevel+1,@aKnotenErreicht,nMaxLevel,xResult/*xMaxLevel*/ )
// xResult<>NIL: ein Ergebnis gefunden! Wenn I>1 noch nach besseren Lösungen suchen!
aSize( aKnotenErreicht,nLen ) // NEU: Erreichte Knoten wieder zurücksetzen!
NEXT I
Code: Alles auswählen
FindeBeziehung(x,y) // findet heraus, ob es Kontakt zwischen x und y gibt - und auf welcher Ebene. Antwort 0 = sie haben keine Beziehung
LOCAL nTiefe := 0, i
IF SindNachbarn(x,y) // sucht in der Beziehungentabelle, ob es eine direkte Verbindung zwischen x und y gibt
nTiefe ++
RETURN nTiefe
ELSE
a := GetNachbarn(y,x) // erhebt alle Nachbarn von y - AUSSER x
nTiefe ++
FOR i := 1 TO Len(a)
nBeziehung := FindeBeziehung(y,a[i])
IF nBeziehung > 0
RETURN nTiefe + nBeziehung
ENDIF
NEXT
ENDIF
RETURN 0 // keine Beziehung
Aber ziemlich Blau .Tom hat geschrieben:Ins Blaue. "SindNachbarn" und "GetNachbarn" müssten noch umgesetzt werden, aber das ist pillepalle.
ach ja, was genau brauchst du am Ende ?brandelh hat geschrieben:Wenn ich die Eckdaten richtig werte, hast du zwischen 100 und 99999 Knoten, die max 20 Verbindungen haben, richtig ?
Auf UNS ? Bin ich dein SchulmeisterUliTs hat geschrieben:Hubert und Tom,
Ich bin ein bischen beleidigt
Keiner kommentiert meinen Code ...
Und das ist mehr als ein Geruest
Uli
Ui. Bei 50.000 "Knoten" ist das schon eine Aufgabe mit Optimierungspotential (Daten in Arrays einlesen?). Bei durchschnittlich 4 Verbindungen je Knoten hat man es da schnell mit einer kombinatorischen Explosion zu tun. Hängt aber von der Struktur des "Netzes" ab. Viel Spaß dabei!Und innerhalb weniger Sekunden müsste ich das schon haben.
Und ich hatte gehofft, man kann ihn innerhalb 10 Minuten verstehen .brandelh hat geschrieben:ich wollte damit aber nicht andeuten, dass dein Code verbessert werden muss, ich habe aktuell keine Zeit mich mit anderem Code zu beschäftigen