Hallo, für eine Studienarbeit (nein, Ihr sollt nicht meinen Job machen) stehe ich vor einem Problem, dass ich nicht so richtig zuordnen kann. Ich bräuchte mal ein Stichwort oder einen Begriff, unter dem ich das recherchieren kann. Problematik: Ich habe ein erstmal theoretisches Konstrukt, das einer Bienenwabe ähnelt. Es besteht aus lauter gleichseitigen Sechsecken, die an den Kanten miteinander kommunizieren können. Nun möchte ich, ausgehend von einer Initialzelle (z.B. die, die sich am weitesten links unten befindet), alle anderen Zellen automatisch adressieren, indem diese mit ihrem Nachbarn kommunizieren und ihm ihre Adresse mitteilen. Jede Zelle weiß also erstmal, wie viele Zellen direkt um sie herum liegen und bekommt, wenn eine angrenzende Zelle ihre Adress schon weiß, diese mitgeteilt. Ich habs im Moment so gelöst, dass die Zellen ihren Standort in der Wabe (x,y vom Zellmittelpunkt) mitteilen und die anderen Zellen ihren jeweiligen Standort aus der Größe und dem kommunizieren Standort ausrechnen und ebenfalls weiterleiten. Da die Position eineindeutig ist, kann man sie ja auch als Adresse ansehen. Aber so richtig gefällt mir das noch nicht. Ich hätte gern etwas Allgemeines, wo eine Ganzzahl am Ende rauskommt. Unter welcher Thematik läuft dieses Problem? Graphentheorie vielleicht? Grüße, Alex
Meinst du ein hexagonales Koordinatensystem? http://www.redblobgames.com/grids/hexagons/ Vielleicht wäre das Stichwort "Cellular Automaton" auch noch was für dich (z.B. Conway's Game of Life).
:
Bearbeitet durch User
Ja, so in der Richtung. Mein Ziel es es nun aber, die Adressen als 1,2,3 usw. zu erhalten und nicht als Koordinatenpaar. Aber der Link ist gut, kann ich mich mal noch bisschen belesen. Mein Horizont beschränkte sich bisher auf karthesische, Polar- und Kugelkoordinaten ;)
:
Bearbeitet durch User
Alexander H. schrieb: > Ja, so in der Richtung. Mein Ziel es es nun aber, die Adressen als 1,2,3 > usw. zu erhalten und nicht als Koordinatenpaar. Erscheint dir die mathematische Seite der Umsetzung eines Koordinatenpaars in eine einzelne Zahl als unüberwindliches Hindernis? Oder musst du mit einer unendlichen Wabengrösse rechnen?
:
Bearbeitet durch User
A. K. schrieb: > Erscheint dir die mathematische Seite der Umsetzung eines > Koordinatenpaars in eine einzelne Zahl als unüberwindliches Hindernis? > Oder musst du mit eine unendlichen Wabengrösse rechnen? Nein, das würde ich mir in der Tat noch zutrauen und habe auch schon drüber nachgedacht, das so zu machen. Die Zellanzahl kann einige tausend erreichen, ist also nicht unendlich. Ich hätte nur gern noch eine Alternative präsentiert. Grüße, Alex
Kann davon ausgegangen werden, dass die Wabe konvex ist? Wenn ja, können die Zellen folgendermaßen mit natürlichen Zahlen durchnummeriert werden:
1 | _____ |
2 | / \ |
3 | / 0 \_____ |
4 | \ / \ |
5 | \_____/ 9 \_____ |
6 | / \ / \ |
7 | / 1 \_____/ 10 \_____ |
8 | \ / \ / \ |
9 | \_____/ 8 \_____/ 19 \_____ |
10 | / \ / \ / \ |
11 | / 2 \_____/ 11 \_____/ 20 \_____ |
12 | \ / \ / \ / \ |
13 | \_____/ 7 \_____/ 18 \_____/ 28 \_____ |
14 | / \ / \ / \ / \ |
15 | / 3 \_____/ 12 \_____/ 21 \_____/ 29 \_____ |
16 | \ / \ / \ / \ / \ |
17 | \_____/ 6 \_____/ 17 \_____/ 27 \_____/ 33 \ |
18 | / \ / \ / \ / \ / |
19 | / 4 \_____/ 13 \_____/ 22 \_____/ 30 \_____/ |
20 | \ / \ / \ / \ / \ |
21 | \_____/ 5 \_____/ 16 \_____/ 26 \_____/ 32 \ |
22 | \ / \ / \ / \ / |
23 | \_____/ 14 \_____/ 23 \_____/ 31 \_____/ |
24 | \ / \ / \ / |
25 | \_____/ 15 \_____/ 25 \_____/ |
26 | \ / \ / |
27 | \_____/ 24 \_____/ |
28 | \ / |
29 | \_____/ |
Da die Adressen i und i+1 immer zwei benachbarten Zellen zugeordnet sind, gestaltet sich die Adressvergabe bei der Initialisierung des Systems sehr einfach. Die einzelnen Zellen müssen dabei nur ihre direkten Nachbarn, nicht aber ihre Position innerhalb der Wabe kennen. Der Initiator bei der Adressvergabe ist die oberste Zelle in der am weitesten links liegende Spalte. Ist es nicht möglich, diese Zelle zu bestimmen, kann auch mit einer beliebigen Zelle begonnen werden, wozu allerdings negative Adressen erforderlich werden:
1 | _____ |
2 | / \ |
3 | / -12 \_____ |
4 | \ / \ |
5 | \_____/ -11 \_____ |
6 | / \ / \ |
7 | / -13 \_____/ -2 \_____ |
8 | \ / \ / \ |
9 | \_____/ -10 \_____/ -1 \_____ |
10 | / \ / \ / \ |
11 | / -14 \_____/ -3 \_____/ +8 \_____ |
12 | \ / \ / \ / \ |
13 | \_____/ -9 \_____/ 0 \_____/ +9 \_____ |
14 | / \ / \ / \ / \ |
15 | / -15 \_____/ -4 \_____/ +7 \_____/ +15 \_____ |
16 | \ / \ / \ / \ / \ |
17 | \_____/ -8 \_____/ +1 \_____/ +10 \_____/ +16 \ |
18 | / \ / \ / \ / \ / |
19 | / -16 \_____/ -5 \_____/ +6 \_____/ +14 \_____/ |
20 | \ / \ / \ / \ / \ |
21 | \_____/ -7 \_____/ +2 \_____/ +11 \_____/ +17 \ |
22 | \ / \ / \ / \ / |
23 | \_____/ -6 \_____/ +5 \_____/ +13 \_____/ |
24 | \ / \ / \ / |
25 | \_____/ +3 \_____/ +12 \_____/ |
26 | \ / \ / |
27 | \_____/ +4 \_____/ |
28 | \ / |
29 | \_____/ |
Falls die negativen Adressen stören, kann die Adressvergabe wiederholt werden, wobei diesmal die Zelle mit der negativesten Adresse der Initiator ist. Prinzipiell ist eine Adressvergabe mit einer lückenlosen Folge natürlicher Zahlen auch für nichtkonvexe Waben ohne viel Vorwissen algorithmisch lösbar, wenngleich etwas komplizierter. Ein möglicher Ansatz wäre, einen Baum zu generieren, dessen Knoten die Zellen sind und für den die Kinderknoten jeweils Nachbarn ihres Elternknotens sind. Dieser Baum wird depth-first generiert und seine Knoten während seiner Entstehung fortlaufend durchnummeriert.
Man kann das Problem der undefinierten Breite/Höhe und Löcher bei der Adressierung relativ einfach umgehen: Es sei ein Hexagon "Ursprung" gegeben. Dieses bekommt die Nummer 1. Das Hexagon rechts (oder in der Orientierung wie in yalus Acsii Bildern, das benachbarte Hexagon bei 15°) bekommt die Nummer 2. Von un an: von Hexagon N wird das benachbarte Hexagon gewählt, dass bei einer Linksrotation beginnend bei einem beliebigen noch nicht nummerierten Nachbarn der letzte nicht breits numerierte Nachbar darstellt. Dieser bekommt die Nummer N+1 Sollte kein freier Nachbar zu N mehr existieren, so wird genau das freie Hexagon mit N+1 numeriert, welches die größte eigene Nummer trägt. Dann wieder linkshändig weitergezählt. Am Ende ist das Feld vollständig positiv durchnummeriert (auch mit Löchern!) und das Routing (über welchen Nachbarn muss ich meine Nachricht weiterleiten) bekommst du kostenlos dazu: 1. Ist Ziel# ein Nachbar, dann Nachricht aan Nachbar 2. Ist Ziel# > Eigener#, dann wähle den Nachbarn mit der größten #, die noch unter Ziel# liegt 3. Ist Ziel# < Eigener#, dann wähle den Nachbarn mit der größten #, die jedoch unter der Zielnummer liegt.
Noch eine Idee zur relativen Adressierung. Jedes Hexagon hat 6 Nachbarn, die sich in den 6 "Himmelsrichtungen" dieses speziellen Universums befinden. Nennen wir die Himmelrichtungen einfach A, B, C, D, E und F. Dann können wir jede Zelle relativ zu einem Ursprung adressieren, indem wir eine Zeichenkette aus den Buchstaben A-F bilden: z.B. "AAB" = zwei Schritte in Richtung A, dann einen in Richtung B. Wenn man ein bisschen länger darüber nachdenkt, kommt man zu dem Schluß, daß die Reihenfolge der Schritte dabei egal ist. Und daß sich bestimmte Schritte gegenseitig neutralisieren. Wenn bspw. A und D entgegengesetzte Richtungen sind, dann sind "AADA" und "AA" der gleiche Ort. Wenn wir die Zeichenkette sortieren, dann können wir sie auch kürzer als einen 6-dimensionalen Vektor schreiben: (N_A, N_B, ..., N_F), wobei N_X für die Anzahl der Schritte in Richtung X steht. Da jeweils 2 der 6 Dimensionen des Vektors verbunden sind dahingehend daß sich ihre Wirkungen aufheben, kann man einfach die z.B. letzten 3 auf Null setzen und ihre Wirkung in den jeweiligen Partner ziehen: (N_A, N_B, ..., N_F) => (N_A - N_D, N_B - N_E, N_C - N_F, 0, 0, 0) Jetzt lassen wir die Nullen noch weg und bekommen einen dreidimensionalen Vektor als kanonische Adresse in einem solchen Netz. XL
Axel Schwenke schrieb: > (N_A, N_B, ..., N_F) => (N_A - N_D, N_B - N_E, N_C - N_F, 0, 0, 0) N_C - N_F kann man ebenfalls weglassen, da jeder Schritt in Richtung C aus je einem Schritt in Richtung B und D, und jeder Schritt in Richtung F aus je einem Schritt in Richtung A und E zusammengesetzt werden kann. Der verbleibende zweidimensionaler Vektor ist sogar eindeutig und entspricht exakt dem, was auf der von Boris verlinkten Webseite http://www.redblobgames.com/grids/hexagons/ als "Axial coordinates" bezeichnet wird, also einem Punkt in einem Koordinatensystem, dessen Achsen in einem Winkel von 60° zueinander stehen ;-)
:
Bearbeitet durch Moderator
Hallo, vielen Dank für den tollen Input. Ich muss mir das erstmal alles zu Gemüte führen und durchlesen/denken. Grüße, Alex
Yalu X. schrieb: > N_C - N_F kann man ebenfalls weglassen, da jeder Schritt in Richtung C > aus je einem Schritt in Richtung B und D, und jeder Schritt in Richtung > F aus je einem Schritt in Richtung A und E zusammengesetzt werden kann. Stimmt ... > Der verbleibende zweidimensionaler Vektor ist sogar eindeutig und > entspricht exakt dem, was auf der von Boris verlinkten Webseite > > http://www.redblobgames.com/grids/hexagons/ > > als "Axial coordinates" bezeichnet wird Ach. Nett. Manchmal lohnt es also doch, gegebenen URLs mal nachzubrowsen :) XL
Tim Seidel schrieb: >Es sei ein Hexagon "Ursprung" gegeben. Dieses bekommt die Nummer 1. >Das Hexagon rechts (oder in der Orientierung wie in yalus Acsii Bildern, >das benachbarte Hexagon bei 15°) bekommt die Nummer 2. Ich nehme an, Du meinst 30°. Bis hier hin kann ich dir noch folgen (hoffe ich). >Von un an: von Hexagon N wird das benachbarte Hexagon gewählt, dass bei >einer Linksrotation beginnend bei einem beliebigen noch nicht >nummerierten Nachbarn der letzte nicht breits numerierte Nachbar >darstellt. Dieser bekommt die Nummer N+1 Bei obigem Satz wird mir etwas schwindelig beim lesen. Kannst Du mir das nochmal genauer erklären. Wenn diese Lösung funktioniert, wäre es das, was ich suche. Konvexität des Feldes kann ich nämlich nicht gerantieren und dass das Routing mit dabei ist, ist auch praktisch. Ich habe mal ein Bild angehängt mit mit einem Feld ohne Lücken, aber nicht konvex. Wo wäre da die 3, 4 usw. Damit ich das System mal verstehe. Grüße, Alex
:
Bearbeitet durch User
Alexander H. schrieb: > > Ich nehme an, Du meinst 30°. Bis hier hin kann ich dir noch folgen > (hoffe ich). > Japp. >>Von un an: von Hexagon N wird das benachbarte Hexagon gewählt, dass bei >>einer Linksrotation beginnend bei einem beliebigen noch nicht >>nummerierten Nachbarn der letzte nicht breits numerierte Nachbar >>darstellt. Dieser bekommt die Nummer N+1 > > Bei obigem Satz wird mir etwas schwindelig beim lesen. Kannst Du mir das > nochmal genauer erklären. Wenn diese Lösung funktioniert, wäre es das, > was ich suche. Konvexität des Feldes kann ich nämlich nicht gerantieren > und dass das Routing mit dabei ist, ist auch praktisch. > > Ich habe mal ein Bild angehängt mit mit einem Feld ohne Lücken, aber > nicht konvex. Wo wäre da die 3, 4 usw. Damit ich das System mal > verstehe. > > Grüße, Alex Ich hab das mal mit zwei verschiedenen Ursprüngen eingetragen und angehangen. Die Routing Pfade sind nach den einfachen Regeln nicht optimal, kommen aber immer zum Ziel, es sei denn dein Graph ist nicht zusammenhängend und die Endpunkte liegen in getrennten Partitionen.
Alexander H. schrieb: > Unter welcher Thematik läuft dieses Problem? Graphentheorie vielleicht? Wenn es sich wirklich immer um Sechsecke handelt, könnte das tatsächlich unter Graphen-Theorie falles: http://de.wikipedia.org/wiki/Graphen ;-)
Tim Seidel schrieb: > Alexander H. schrieb: >> >> Ich nehme an, Du meinst 30°. Bis hier hin kann ich dir noch folgen >> (hoffe ich). >> > > Japp. nochmal blöd gefragt: meint ihr nicht beide 60°?
Vlad Tepesch schrieb: > Tim Seidel schrieb: >> Alexander H. schrieb: >>> >>> Ich nehme an, Du meinst 30°. Bis hier hin kann ich dir noch folgen >>> (hoffe ich). >>> >> >> Japp. > > nochmal blöd gefragt: meint ihr nicht beide 60°? Nein. In dem Sechseck sind die Innenwinkel zwr 60°, hier ist aber der Winkel von Ecke zu Mittelpunkt zu Mitte einer Seite gesucht. Also die Hälfte von Ecke - Mitte - Ecke. :edit: Ich hab noch mal den Pfad entlang der Nummerierung angehangen. Rot: erster Pfad bis "alle Nachbarn sind nummeriert" Blau: Pfad rückwärts bis zum ersten freien Nachbarn Grün: 2. Pfad bis alle Nachbarn sind bereits nummeriert
:
Bearbeitet durch User
Hallo Tim, vielen Dank für deine Mühe. Was bei mir allerdings noch eine Frage aufwirft, ist die 14, die da so "verlassen" rumsteht. Da der Algorithmus ja automatisch ablaufen soll, frage ich mich, wie das gehen soll. Denn die 14 bekommt ja nicht mit, dass irgendwo eine 13 existiert, wenn diese nicht einer ihrer Nachbarn ist. Das stünde aber einer automatischen Adressierung entgegen. Oder sehe ich da was falsch? Grüße, Alex
Alexander H. schrieb: > Hallo Tim, > > vielen Dank für deine Mühe. Was bei mir allerdings noch eine Frage > aufwirft, ist die 14, die da so "verlassen" rumsteht. Da der Algorithmus > ja automatisch ablaufen soll, frage ich mich, wie das gehen soll. In dem Fall in dem du in die Sackgasse gelaufen bist (hier z.B. die 13) dann gehst du von diesem entlang der Routing-Regeln zu dem Hexagon mit N-1 (hier also 12) dort prüfst du ob er einen freien Nachbarn hat. Wenn ja, beginne wieder mit der Nummernvergabe, ansonsten gehe wieder zum Hexagon mit der nächst niedrigeren Nummer und wiederhole den Test. > Denn > die 14 bekommt ja nicht mit, dass irgendwo eine 13 existiert, wenn diese > nicht einer ihrer Nachbarn ist. Das stünde aber einer automatischen > Adressierung entgegen. Oder sehe ich da was falsch? Braucht die 14 nicht mitzubekommen. Sie weiss, dass 13 existiert, da sie ein numerischer Nachfolger von 13 ist. Ist 14 also bereits veregebn ist 13 vorher vergeben worden. Wie ich zu 13 komme wird anhand der Routing-Regeln ermittelt. In dem Beispiel: 14 (Start) -> 6 (größter Nachbar von 14 < Ziel#) -> 7 (größter Nachbar von 6 < Ziel#) -> 13 (Ziel ist Nachbar von 7)
Tim Seidel schrieb: > In dem Fall in dem du in die Sackgasse gelaufen bist (hier z.B. die 13) > dann gehst du von diesem entlang der Routing-Regeln zu dem Hexagon mit > N-1 (hier also 12) Implementiert man des Vor- und Zurücklaufen als Versenden von Nachrichten zwischen benachbarten Zellen, kann man den Algorithmus wie in den folgenden Abschnitten gezeigt formulieren. Der Algorithmus entspricht dabei dem, was ich auch beim Schreiben dieses Beitrags im Kopf hatte: Yalu X. schrieb: > Ein möglicher Ansatz wäre, einen Baum zu generieren, dessen Knoten die > Zellen sind und für den die Kinderknoten jeweils Nachbarn ihres > Elternknotens sind. Dieser Baum wird depth-first generiert und seine > Knoten während seiner Entstehung fortlaufend durchnummeriert. Jede Zelle reagiert aus ihrer Sicht auf den Empfang einer Nachricht folgendermaßen:
1 | Bei Empfang der Nachricht "Verteile Adressen beginnend mit A" über die Schnittstelle S: |
2 | Wenn ich selber noch keine Adresse habe: |
3 | Weise mir selbst die Adresse A zu |
4 | A := A + 1 (die nächste freie Adresse) |
5 | Für alle N aus der Menge meiner Nachbarn (jeweils repäsentiert durch eine der Schnittstellen): |
6 | Sende an N die Nachricht "Verteile Adressen beginnend mit A" |
7 | Warte auf die Antwort von N mit dem Inhalt "Die nächste freie Adresse ist A'" |
8 | A := A' (die nächste freie Adresse) |
9 | Sende die Antwort "Die nächste freie Adresse ist A" über die Schnittstelle S an den Absender zurück |
Ein externer Master startet die Adressvergabe:
1 | Adressvergabe: |
2 | Wähle unter allen Zellen einen beliebigen Initiator I aus |
3 | Sende an I die Nachricht "Verteile Adressen beginnend mit 0" |
4 | Warte auf die Antwort von I mit dem Inhalt "Die nächste freie Adresse ist A" |
5 | Wenn A gleich der Anzahl der Zellen ist: |
6 | -> Adressvergabe war erfolgreich |
7 | Sonst |
8 | -> Nicht alle Zellen konnten bei der Adressvergabe erreicht werden. |
Wenn I zu Beginn schon weiß, dass er der Initiator ist, kann er die Initiative natürlich auch selbst übernehmen. Ein externer Master wird dann nicht benötigt. Ich habe ein kleines Python-Programm angehängt, das diesen Algorithmus demonstriert. Es funktioniert nicht nur für hexagonale Strukturen, sondern für beliebige zusammenhängende Graphen, in dem die einzelnen Knoten entlang der Kanten bidirektional kommunizieren können. Die einzelnen Knoten werden als Instanzen der Klasse Node angelegt. Die Topologie wird mit der Funktion add_neighbors festgelegt. Das Senden einer Nachricht und der Empfang der zugehörigen Antwort ist hier der Einfachheit halber als Funktionsaufruf implementiert:
1 | lowest_free_address = node.assign_addresses(lowest_free_address) |
Das Funktionsargument ist dabei die gesendete Nachricht, der Rückgabewert die empfangene Antwort. Die Ausgabe des Programms listet die nacheinander zugewiesenen Adressen auf:
1 | node E <- address 0 |
2 | node F <- address 1 |
3 | node H <- address 2 |
4 | node K <- address 3 |
5 | node N <- address 4 |
6 | node M <- address 5 |
7 | node L <- address 6 |
8 | node I <- address 7 |
9 | node G <- address 8 |
10 | node D <- address 9 |
11 | node A <- address 10 |
12 | node B <- address 11 |
13 | node C <- address 12 |
14 | node J <- address 13 |
15 | 14 addresses assigend |
Grafisch sieht dies folgermaßen aus:
1 | __ __ |
2 | __/9 \__/7 \__ |
3 | /10\__/8 \__/6 \ |
4 | \__/0 \__/13\__/ |
5 | /11\__/2 \__/5 \ |
6 | \__/1 \__/3 \__/ |
7 | /12\__/ \__/4 \ |
8 | \__/ \__/ |
Der Ablauf und damit das Ergebnis ist prinzipiell gleich wie bei Tim, nur die Reihenfolge ist anders, da sie von der Reihenfolge der Nachbarn im Aufruf von add_neighbors abhängt. Abar auch hier ist die höchste Adresse (13) nicht mit der zweithöchsten (12) benachbart. Für das Routing lässt sich auch hier Tims Vorschlag anwenden, für ein optimales Routing ist aber vermutlich eine Routing-Tabelle in jedem Knoten erforderlich, die für jede Adresse A im Netzwerk einen Eintrag (S,D) enthält, so dass der Knoten mit der Adresse A über die Schnittstelle S auf kürzestem Weg über die Distanz D erreicht werden kann. Diese Routing-Tabellen können mit einer Art Wellenausbreitungsverfahren wie folgt generiert werden: Am Anfang werden alle Distanzeinträge D in der Routing-Tabelle jedes Knotens auf unendlich (oder auf die Gesamtzahl der Knoten im Netzwerk) gesetzt. Nur die Distanz der eigenen Adresse wird auf 0 gesetzt. Dann sendet jeder Knoten seine eigene Adresse A und die Distanz 1 als Paar (A,1) an seine Nachbarn. Empfängt ein Knoten ein Paar (A,D) über die Schnittstelle S, liest er aus der Tabelle den zu A zugehörigen Eintrag (S',D') aus und prüft, ob D<D'. Ist dies der Fall, ersetzt er den Eintrag durch (S,D) und sendet das Paar (A,D+1) an eine Nachbarn. Ist hingegen D≥D', erfolgt keine Aktion. Irgendwann kommt dieser Austausch von Nachrichten zum Erliegen. Dann sind die Routing-Tabellen der einzelnen Knoten vollständig und optimal. Wie effizient dieses Verfahren bei einer großen Zahl von Knoten abläuft, hängt stark davon ab, in welcher Reihenfolge die jeweils aktualisierten (A,D)-Nachrichten an die einzelnen Nachbarn weitergeleitet werden. Da kann man sicher noch etwas Gehirnschmalz hineinstecken.
Oh man, was für ein Beitrag! Wie lange hast Du dafür gebaucht? Als ich in einer ruhigen Minute mal drüber nachgedacht habe (bis die kleine Motte endlich eingeschlafen ist), hatte ich schon den Aha-Effekt, dass man sich einfach die höchste Adresse merken muss und wenn es nicht weitergeht, den Weg zurück muss, bis es wieder unadressierte Zellen gibt. Sozusagen einen Token, den man durch die Wabe wandern lässt. Ich werde Yalu's Beitrag noch ein bisschen sacken lassen und dann sollte alles klar sein. Danke für eure viele Mühe. Grüße, Alex
Bitte 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.