Преимущество и недостаток остовного дерева с четным расстоянием

Question

Это новый год и все еще не может решить мою проблему об алгоритме spanning tree. Я не могу вставить картинку, поэтому я должен попытаться объяснить среду словами.

Это 36 узлов и расстояние до всех узлов равно. Вопрос в том, является ли расстояние четным, не имеет значения, каким образом передать сообщение с узла с идентификатором 1 (корень) на последний узел с идентификатором 36. Поскольку расстояние даже не позволяет экономить время, экономить энергию или сообщение Сохранить алгоритм? Я надеюсь, что кто-то понять мой вопрос

отредактирован:

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 
   

Это мой выбор связующего дерева. Узел с идентификатором 36 отправляет информацию через 30,24,18,12,6,5,4,3,2,1 (один из них является корневым), а затем узел 1 отправляет информацию на базовую станцию. Поскольку он не имеет каких-либо затрат, на самом деле не имеет значения, какой путь я выбираю для отправки информации с узла 36 на узел 1, потому что стоимость будет по-прежнему одинаковой.

1. Мой Spanning дерево Алгоритм

   • При запуске, только корень отмечен.
   • Сообщение корневая поиск отправить к нему соседа
   • Если узел не помечен, когда он recieves поиска сообщений от других узлов:
   • это пометить себя
   • Выберите узлы с наименьшим идентификатором, как «родитель» и ответ «не-родитель» к другим узлам
   • Если узел уже отмечает, что ответ «не-родителю»
   • Если узел уже помечен и получать родительское сообщение помечает отправитель, как ребенок

2. Я не могу показать вам ребята блок-схему, потому что у меня нет привилегии вставлять изображения.

3. псевдокод (не сделали этого)

4. Вывода - Здесь я должен записать преимущества и недостатки моего алгоритма, но сейчас я не могу думать о каких-либо преимуществах и недостатках

Answer 1

Под «четным» Я думаю, вы имеете в виду «независимо от того, где я начинаю, расстояние для перемещения одного узла по горизонтали на моей диаграмме всегда равно 1, а расстояние до вертикального перемещения всегда равно 6.»

Ваш вопрос звучит так: «Все ли дорожки из верхнего левого нижнего правого имеют одинаковую общую длину?» Если мы ограничим наше внимание на пути, которые на каждом шаге всегда перемещаются либо вниз, либо вправо, тогда ответ «да».

Чтобы увидеть это, обратите внимание, что нам нужно всего 5 прыжков вниз и 5 прыжков вправо. Предположим, что мы выбираем путь, который делает это (но не обязательно в этом порядке.) Поскольку все нисходящие прыжки имеют одинаковую стоимость, а все правые хмель имеют одинаковую стоимость, мы можем найти общую стоимость пути, рассматривая каждый прыжок по порядку, записывая 6 для каждого нисходящего прыжка и 1 для каждого прыжка вправо и добавьте список вместе.

Например, стоимость дорожного просвета RRDDRDRDDR is 1 + 1 + 6 + 6 + 1 + 6 + 1 + 6 + 6 + 1.

Теперь мы можем видеть что-то интересное. Другой путь с 5 прыжками вниз и 5 правыми прыжками будет иметь тот же список из 5 6 s и 5 1 s, просто подведённый в другом порядке. Теперь мы можем заметить, что сложение коммутативно и заключают, что эти две суммы должны быть равны. То есть любой путь, перемещающийся вниз и вправо, имеет такую ​​же общую длину (35), как и любой другой.

Учитывая, что ваше связующее дерево так же хорошо, как и любое другое, предполагая, что основной граф действительно является сеткой.