Mathematisches Problem - Frage zur Vorgehensweise

[Jan]

Vielleicht hat jemand eine Idee, wie ich folgendes Problem lösen kann. Mir fehlen da einfach die mathematischen Kenntnisse zu. Gegeben ist:

• 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

Es gibt sowas ähnliches z. B. in Xing, wo mir angezeigt wird, über wie viele Zwischenstufen ich mit jemandem anderen bekannt bin.

Jan

[UliTs]

Es gibt sowas ähnliches z. B. in Xing, wo mir angezeigt wird, über wie viele Zwischenstufen ich mit jemandem anderen bekannt bin.

Das heißt, Du suchst nach der kürzesten Verbindung?
Z.B. K1 ist mit K2 über die Knoten K3 und K4 verbindbar und eine kürzere Verbindung mit weniger Knoten gibt es nicht.

Uli

[Tom]

Hallo, Jan.

Jeder Knoten hat eine eindeutige ID. Diese sind in einer Tabelle hinterlegt. Direkte Verbindungen zwischen zwei Knoten sind in einer weiteren Tabelle hinterlegt, diese hat zwei Indexe für jedes ID-Paar einer Verbindung. Willst Du jetzt wissen, mit wem Knoten x verbunden ist, suchst Du zweimal in dieser zweiten Tabelle, wodurch Du die direkten Verbindungen bekommst (Stufe 1). Diesen Suchprozess wiederholst Du für alle Ergebnisse, wodurch Du die Verbindungen der Stufe 2 bekommst. Hier muss dann ausgespart werden, was bereits gefunden wurde. Und so weiter. Kann man rekursiv machen.

[Tom]

Ergänzung:

Für die Frage: Ist x mit y bekannt - und wenn ja, über wie viele Stufen? Vorgehensweise: Alle direkten Verbindungen von x suchen, dann alle direkten Verbindungen für jeden Treffer. Aufhören wenn a) nichts mehr gefunden wird (wichtig: sich merken, was bereits gefunden wurde!), oder wenn b) y gefunden wurde. Es darf also nach Stufe 1 nicht mehr nach Knoten gesucht werden, die bereits in der Ergebnisliste vorhanden waren.

[UliTs]

Kann man rekursiv machen.

Ein Top Beispiel für eine mehr als sinnvolle rekursive Lösung .
Uli

[Tom]

Ein Top Beispiel für eine mehr als sinnvolle rekursive Lösung

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.ä.).

* hierfür kann sie ein Array als STATIC verwenden, das bei Stufe 1 zurückgesetzt wird, und natürlich bei Abbruch der Funktion.

[UliTs]

Ich würde den gleichen Lösungsansatz wie Tom wählen (ist ja bei den heutigen Speicherkapazitäten kein Problem ...):
Ich probiere mal auf die Schnelle (ungetesteten) Code zu schreiben:

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 )

Obiges könnte funktionieren
Über eine Rückmeldung wäre ich dankbar

Uli

[brandelh]

Falls ich es richtig verstanden habe, ist es das gleiche Problem wie beim Suchen des kürzesten Weges von Ort A nach Ort B.

Lösungen hast du ja oben erhalten.

Vor einiger Zeit habe ich mir mal wieder ein Informatik Buch zugelegt, dass auch dieses Problem behandelt hat.
Die Lösungen werden übrigens von Ameisen perfekt umgesetzt

Alle Ameisen rennen wild los und verteilen Duftspuren.
Die ersten die am Futter ankommen holen es sich und laufen zurück und verteilen wieder Duftspuren.
Nach einiger Zeit wird die Duftspur des direkten Weges - ähnlich einem viel benutzten Trampelpfad - immer deutlicher und somit immer öfter benutzt.
Die langsamen oder falschen Wege verblassen ... so finden die Ameisen den besten Weg zu Futter und zurück

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.

[Tom]

Entscheidend ist, dass man jeden Knoten als isoliertes Netz betrachtet, also nur seine direkten Verbindungen, um dann in x Folgeschritten dies wiederum mit allen erreichbaren Knoten zu tun - außer dem-/denjenigen, die man bereits untersucht hat. Dann ist das Problem trivial.

a(0) hat x Verbindungen (Stufe 1)
a(1) bis a(x) haben jeweils wieder n ... m Verbindungen (Stufe 2). Nur die untersuchen, die nicht zu a(0) führen (Stufe 2)
usw.

[UliTs]

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.

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ß:

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

Falls das Ganze zu langsam sein sollte, könnte Huberts Ansatz im Durchschnitt schneller sein ...

Uli

[brandelh]

Wen es interessiert:

http://www.amazon.de/Abenteuer-Informat ... r-mr-title

[Tom]

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

Ins Blaue. "SindNachbarn" und "GetNachbarn" müssten noch umgesetzt werden, aber das ist pillepalle.

[UliTs]

Ins Blaue. "SindNachbarn" und "GetNachbarn" müssten noch umgesetzt werden, aber das ist pillepalle.

Aber ziemlich Blau .
Meiner Meinung nach findet das zwar eine Lösung, aber fast immer nicht die kürzeste ...
Deswegen meine obigen Vergleiche. Ansonsten ist der Algorithmus der Gleiche ...

Uli

[Tom]

Hallo, Uli.

Stimmt, diese Variante verzweigt zuerst für alle Unterknoten bis zum "Ende", bevor sie Nachbarn auf der gleichen Ebene prüft. Es müsste also "FindeBeziehung" mit einem weiteren Parameter geben, der bewirkt, dass nur auf der obersten Ebene gesucht wird, und die Iteration innerhalb der rekursiven Funktion müsste zweimal erfolgen, im zweiten Durchgang dann ohne diesen Parameter. Aber es geht ja auch erstmal nur ums Prinzip.

[brandelh]

Hallo Jan,

wie liegen denn deine "Knotendaten" vor ... Beispieldaten wären nicht schlecht.

Wenn ich die Eckdaten richtig werte, hast du zwischen 100 und 99999 Knoten, die max 20 Verbindungen haben, richtig ?

[Tom]

Im Prinzip ist das tatsächlich das "Traveling-Salesman-Problem", mit dem kleinen Unterschied, dass es zwischen A und B möglicherweise überhaupt keine Verbindung gibt. Und dem anderen, dass die Entfernung keine Rolle spielt, sondern nur die Anzahl der zu überwindenden Zwischenstationen.

[brandelh]

Wenn ich die Eckdaten richtig werte, hast du zwischen 100 und 99999 Knoten, die max 20 Verbindungen haben, richtig ?

ach ja, was genau brauchst du am Ende ?

Eine komplette Liste der Zwischenstationen der/des Knotens mit den wenigsten Zwischenknoten, oder alle, oder nur die Infos von a nach b in 5 Schritten ?

Nur so um den Speicherbedarf und die Geschwindigkeit zu beurteilen.
Welche Laufzeiten der Berechnung wären akzeptabel ?

[UliTs]

Hubert und Tom,

Ich bin ein bischen beleidigt
Keiner kommentiert meinen Code ...
Und das ist mehr als ein Geruest
Uli

[Jan]

Moin Hubert,

ich brauche alle Zwischenstationen. Und innerhalb weniger Sekunden müsste ich das schon haben.

Wie gesagt, ich werde das in den kommenden Tagen mal ausprobieren.

Jan

[brandelh]

Hubert und Tom,
Ich bin ein bischen beleidigt
Keiner kommentiert meinen Code ...
Und das ist mehr als ein Geruest
Uli

Auf UNS ? Bin ich dein Schulmeister
JAN sollte das probieren und entscheiden was er brauchen kann

[UliTs]

Ich hätte halt einen Dialog ganz nett gefunden ...
Uli

Edit: was ist denn ein Schulmeister?

[brandelh]

Hi,

bei uns sagt man sowas zu einem Besserwisser, der einem das eigene Wort im Mund rumdreht, bis nur noch seines richtig ist ...

[Tom]

Hallo, Jan.

Und innerhalb weniger Sekunden müsste ich das schon haben.

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!

[brandelh]

Darum habe ich nach Beispieldaten (wie liegen die vor) und Größenordnungen gefragt, die ist Jan aber noch schuldig

@ Uli

ich wollte damit aber nicht andeuten, dass dein Code verbessert werden muss, ich habe aktuell keine Zeit mich mit anderem Code zu beschäftigen

[UliTs]

ich wollte damit aber nicht andeuten, dass dein Code verbessert werden muss, ich habe aktuell keine Zeit mich mit anderem Code zu beschäftigen

Und ich hatte gehofft, man kann ihn innerhalb 10 Minuten verstehen .

Uli