Vorteil und Nachteil von Spanning Tree mit gleichmäßigen Abstand

Question

Es ist Neujahrstag und kann immer noch nicht mein Problem über einen Spanning-Tree-Algorithmus lösen. Ich kann noch kein Bild einfügen, also muss ich versuchen, die Umgebung mit Worten zu erklären.

Es ist 36 Knoten und die Entfernung zu jedem Knoten ist gleichmäßig. Die Frage ist, ob die Entfernung gerade ist, es ist egal, auf welche Weise die Nachricht vom Knoten mit der ID 1 (der Wurzel) an den letzten Knoten mit der ID 36 weitergeleitet wird. Da die Entfernung gerade ist, gibt es keine Zeitersparnis, Energieeinsparung oder Nachricht Sparalgorithmus richtig? Ich hoffe, dass jemand verstehen meine Frage

bearbeitet:

1. Enviroment

   1 - 2 - 3 - 4 - 5 - 6 
   | | | | | | 
   7 8 9 10 11 12 
   | | | | | | 
   13 14 15 16 17 18 
   | | | | | | 
   19 20 21 22 23 24 
   | | | | | | 
   25 26 27 28 29 30 
   | | | | | | 
   31 32 33 34 35 36 
   

Das ist meine Wahl Baum überspannen. Der Knoten mit ID 36 sendet Information durch 30,24,18,12,6,5,4,3,2,1 (einer ist die Wurzel) und dann sendet der Knoten 1 Informationen an die Basisstation. Da es keine Kosten hat, ist es nicht wirklich wichtig, welchen Pfad ich auswähle, um die Information von Knoten 36 an Knoten 1 zu senden, da die Kosten immer gleich sind.

1. Mein Spanning Tree-Algorithmus

   • Wenn der Start nur die Wurzel markiert ist.
   • Die Wurzel senden Suche Nachricht an es Nachbar
   • Wenn ein Knoten nicht markiert, wenn sie Such Nachrichten von anderen Knoten recieves:
   • markieren Sie sich
   • Wählen Sie die Knoten mit der niedrigsten ID als „Eltern“ und antworten „nicht-Eltern“ zu den anderen Knoten
   • Wenn der Knoten bereits markiert, antwortet sie „nicht-Eltern“
   • Wenn ein Knoten bereits markiert ist und empfangen eine übergeordnete Nachricht markiert er den Absender als Kind

2. Ich kann Ihnen das Flussdiagramm nicht zeigen, da ich nicht das Recht habe, Bilder einzufügen.

3. Pseudo-Code (habe es nicht getan)

4. Fazit - Hier soll ich den Vorteil und Nachteil meines Algorithmus aufschreiben, aber im Moment kann ich mich nicht jeden Vorteil und Nachteil

Answer 1

Von "even" Ich denke du meinst "Unabhängig davon, wo ich beginne, ist die Entfernung um einen Knoten horizontal in meinem Diagramm immer 1, und die Entfernung vertikal zu bewegen ist immer 6."

Ihre Frage klingt dann wie "Haben alle Wege von oben links nach unten die gleiche Gesamtlänge?" Wenn wir unsere Aufmerksamkeit auf Pfade beschränken, die sich bei jedem Schritt immer entweder nach unten oder nach rechts bewegen, lautet die Antwort "ja".

Um dies zu sehen, beachten Sie, wir brauchen insgesamt 5 Hops nach unten und 5 Hops nach rechts. Angenommen, wir wählen einen Pfad, der dies tut (aber nicht unbedingt in dieser Reihenfolge).) Da alle Abwärtssprünge die gleichen Kosten haben und alle Rechtssprünge die gleichen Kosten haben, können wir die Gesamtkosten des Pfades finden, indem wir jeden Sprung in der Reihenfolge betrachten, eine 6 für jeden Abwärtssprung und 1 für jeden Rechtssprung schreiben und füge die Liste zusammen.

Zum Beispiel sind die Kosten für den Pfad RRDDRDRDDR1 + 1 + 6 + 6 + 1 + 6 + 1 + 6 + 6 + 1.

Jetzt können wir etwas interessantes sehen. Ein anderer Pfad mit 5 Abwärts-Hops und 5 Rechts-Hops hat die gleiche Liste von 5 6 s und 5 1 s, nur in einer anderen Reihenfolge summiert. Wir können jetzt beobachten, dass Addition kommutativ ist, und schließen, dass diese beiden Summen gleich herauskommen müssen. Das heißt, jeder Pfad, der sich nach unten und nach rechts bewegt, hat die gleiche Gesamtlänge (35) wie jeder andere.

Vor diesem Hintergrund ist der Spanning Tree so gut wie jeder andere, vorausgesetzt, der zugrunde liegende Graph ist ein Gitter.