Forum: Offtopic Graphen adressieren, Algorithmus


von Alexander H. (ill_son)


Lesenswert?

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

von Borislav B. (boris_b)


Lesenswert?

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
von Alexander H. (ill_son)


Lesenswert?

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
von (prx) A. K. (prx)


Lesenswert?

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
von Alexander H. (ill_son)


Lesenswert?

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

von Yalu X. (yalu) (Moderator)


Lesenswert?

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.

von Tim S. (tim_seidel) Benutzerseite


Lesenswert?

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.

von Axel S. (a-za-z0-9)


Lesenswert?

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

von Yalu X. (yalu) (Moderator)


Lesenswert?

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
von Alexander H. (ill_son)


Lesenswert?

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

von Axel S. (a-za-z0-9)


Lesenswert?

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

von Alexander H. (ill_son)


Angehängte Dateien:

Lesenswert?

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
von Tim S. (tim_seidel) Benutzerseite



Lesenswert?

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.

von S. E. (crayse)


Lesenswert?

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

;-)

von Vlad T. (vlad_tepesch)


Lesenswert?

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°?

von Tim S. (tim_seidel) Benutzerseite



Lesenswert?

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
von Alexander H. (ill_son)


Lesenswert?

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

von Tim S. (tim_seidel) Benutzerseite


Lesenswert?

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)

von Yalu X. (yalu) (Moderator)


Angehängte Dateien:

Lesenswert?

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.

von Alexander H. (ill_son)


Lesenswert?

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
Noch kein Account? Hier anmelden.