Hallo zusammen, ich hätte da ein Problem: Ich habe ein Funknetz, bei dem alle Teilnehmer (Knoten) bekannt sind. Nun wird ein Knoten als Basisstation definiert. Nun möchte ich das Netzwerk durchsuchen und für jeden Knoten seinen erreichbaren Nachbarn bestimmen (die Qualität der Verbindung wird über die RSSI bestimmt). Jetzt meine ich mich an einen rekursiven Algorithmus zu erinnern, der diese Aufgabe ausführt. Also von Knoten zu Knoten springt und dessen Nachbarn herausfindet, bis alle Verbindungen gefunden sind. Die große Frage die sich nun stellt: Wie heißt dieser Algorithmus? Grüße lighninglord
Google scheint den Algorithmus nicht zu kennen. Hmm. Aber ich lande beim Königsberger Brückenproblem. Ob der Graph eulersch ist ist mir eigentlich latte.
Soweit bin ich schon: Ich suche eine Algorithmus zur Erstellung der Adjazenzmatrix aus einem (physikalisch) bestehenden Graphen.
Lord of Lightning schrieb: > Soweit bin ich schon: Ich suche eine Algorithmus zur Erstellung der > Adjazenzmatrix aus einem (physikalisch) bestehenden Graphen. Das ist eine reine Formatierung. Du hast doch die direkten Nachbarn, bzw die "Kanten": Mache eine Tabelle mit Spalten = Zeilen mit den Knoten als Zeilen/Spaltenbeschriftung und trage überall da 0 ein, wo keine direkte Nachbarschaft besteht, eine 1 wo es diese gibt. (Entweder in dem du jede Kante durchgeshst und (A,B) und (B,A) mit 1 markierst und den Rest 0 lässt, oder indem du alle Spalten (betrachtete Knoten) durchgehst und alle Zeilen(direkt erreichbare Knoten) mit 1 markierst und den Rest 0 lässt. Voila.
da findest du alles was du dazu brauchst http://de.wikipedia.org/wiki/Flüsse_und_Schnitte_in_Netzwerken https://video.tu-clausthal.de/vorlesung/401.html
Hauptsache der Handelsmann macht sich einen Knoten ins Taschentuch, daß er seine Nachbarn nicht wieder vergisst (duck und weg :-))
Tiefensuche wäre geschickte zum implementieren.
> Wie heißt dieser Algorithmus?
Spanning Tree und eine Loesung des im Post
beschriebenen (verteilten) Netzwerkproblems
waere OSPF.
Der gesuchte Algorithmus heist: Travelling Salesman Einfach Googeln, da findest Du jede Menge Infos.
Lord of Lightning schrieb: > Ich habe ein Funknetz, bei dem alle Teilnehmer > (Knoten) bekannt sind. Okay. > Nun wird ein Knoten als Basisstation definiert. "Weiss" dieser Knoten, dass er Basisstation ist? > Nun möchte ich das Netzwerk durchsuchen Wer ist "ich" in dem Netzwerk? Wer will die Struktur des Netzwerkes wissen? Alle Knoten oder nur die Basis-Station?
Flipper schrieb: > Der gesuchte Algorithmus heist: Travelling Salesman Aus irgendwelchen Gründen soll man den jetzt "Travelling Salesperson" nennen...
Lord of Lightning schrieb: > Hallo zusammen, > > ich hätte da ein Problem: Ich habe ein Funknetz, bei dem alle Teilnehmer > (Knoten) bekannt sind. Es sind alle "Adressen"/MAC-Adressen o.ä. vorab bekannt? Die Topologie des Netzes? > Nun wird ein Knoten als Basisstation definiert. > Nun möchte ich das Netzwerk durchsuchen und für jeden Knoten seinen > erreichbaren Nachbarn bestimmen (die Qualität der Verbindung wird über > die RSSI bestimmt). Die Basisstation muss zumindest wissen an wen sie die Pakete schicken soll und da jeder Knoten als Basisstation definiert werden kann (?) kennt zumindest jeder Knoten seine erreichbaren Nachbarn... Falls bestimmt werden soll, ob ein Knoten einen bestimmten anderen erreichen kann: Erreichbarkeitproblem (es kann bspw. passieren das ein Knoten einen anderen sieht aber nicht hört...) Ansonsten stellt sich die Frage wie groß der Graph werden kann... Oder was passiert wenn die alle hintereinander "hängen" a -> b -> c -> ... -> n oder jeder jeden sieht... Vielleicht ein interessantes Paper das ein paar Ideen liefert: "Tree-Based Data Broadcast in IEEE802.15.4 and ZigBee Networks", Mobile Computing, IEEE Transactions on, 2006 http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.417.2657&rep=rep1&type=pdf
:
Bearbeitet durch User
Tiramisu schrieb: >> Wie heißt dieser Algorithmus? > Spanning Tree und eine Loesung des im Post > beschriebenen (verteilten) Netzwerkproblems > waere OSPF. OSPF implemtiert Dystra
Beim Travelling Salesman (engl.) oder Königsberger Brückenproblem (dtsch.) geht es darum, einen Pfad in einem Graphen zu finden, der jeden Knoten einmal berührt und das nach Möglichkeit genau einmal. Ist das wirklich das, worum es hier geht? Geht es nicht vielmehr darum, zu jedem beliebigen Koten den günstigsten Pfad von oder zur Basisstation zu finden? In diesem Fall würde ich die priorisierte Breitensuche bevorzugen: Man bestimmt, ausgehend vom Startknoten, alle unmittelbar erreichbaren Nachbarknoten und sortiert sie entsprechend der Kosten, die es verursacht, sie zu erreichen, in eine Warteschlange ein. Dann wird der erste, also der bisher günstigste Pfad aus der Warteschlange entfernt und der Vorgang mit dem Koten, zu dem er führt, wiederholt. Pfade, die mindestens einen Knoten mehrfach enthalten, werden ignoriert. Der Vorgang wird wiederholt, bis ein Pfad zu dem gewünschten Knoten am Anfang der Warteschlange erscheint oder die Warteschlange leer ist. Dieser Algorithmus terminiert garantiert, auch in zyklischen Graphen, und liefert stets den günstigsten Pfad (bzw. einen der günstigsten, sofern es mehrere gleichwertige gibt).
Um die kürzesten (besten) Wege von einem ausgezeichneten Knoten zu allen anderen Knoten eines Graphen zu berechnen, eignet sich Dijkstras Algorithmus sehr gut. Oder suchst du nach einem Algorithmus, um den Graphen zu ermitteln?
Stryker schrieb: >> Der gesuchte Algorithmus heist: Travelling Salesman > > Aus irgendwelchen Gründen soll man den jetzt "Travelling Salesperson" > nennen... Muss man jetzt "mankind" auch in "personkind" umbenennen? :-)
Lord of Lightning schrieb: > Wie heißt dieser Algorithmus? Einfach machen? Einfach jeden erreichbaren Knoten vom Basisknoten daraufhin überprüfen, ob er ein direkter Nachbarknoten ist. Das dann für jeden Nachbarknoten wsiederholen (schon bekannte Nachbarknoten überspringen). Kann man rekusiv machen, muß man aber nicht. Oliver
Thread beobachten
Seitenaufteilung abschaltenBitte melde dich an um einen Beitrag zu schreiben. Anmeldung ist kostenlos und dauert nur eine Minute.
Bestehender Account
Schon ein Account bei Google/GoogleMail? Keine Anmeldung erforderlich!
Mit Google-Account einloggen
Mit Google-Account einloggen
Noch kein Account? Hier anmelden.