algorithm - 等距生成树的优缺点

Question

这是元旦，仍然无法解决我关于生成树算法的问题。我还不能插入图片，所以我不得不尝试用文字来解释环境。

它有 36 个节点，到每个节点的距离是均匀的。问题是如果距离是均匀的，那么从 ID 为 1 的节点（根）到最后一个 ID 为 36 的节点以哪种方式传递消息并不重要。因为距离是均匀的，所以没有节省时间、节能或消息保存算法对吗？我希望有人能理解我的问题

编辑：

1. 环境

   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
   

这是我选择的生成树。ID 为 36 的节点通过 30,24,18,12,6,5,4,3,2,1（一个是根）向其发送信息，然后节点 1 向基站发送信息。因为它没有任何成本，所以我选择哪条路径将信息从节点 36 发送到节点 1 并不重要，因为成本仍然相同。

1. 我的生成树算法

   • 启动时，仅标记根。
   • 根向它的邻居发送搜索消息
   • 如果一个节点没有被标记，当它收到来自其他节点的搜索消息时：
   • 它标记自己
   • 选择ID最低的节点作为“父节点”，向其他节点回复“非父节点”
   • 如果节点已经被标记，它会回复“非父节点”
   • 如果一个节点已被标记并收到父消息，则它将发送者标记为子节点

2. 我不能向你们展示流程图，因为我没有插入图像的特权。

3. 伪代码（没做过）

4. 结论 - 在这里我应该写下我的算法的优点和缺点，但现在我想不出任何优点和缺点

Answer 1

“偶数”我认为您的意思是“无论我从哪里开始，在我的图表中水平移动一个节点的距离始终为 1，垂直移动的距离始终为 6。”

然后你的问题听起来像“从左上角到右下角的所有路径都具有相同的总长度吗？” 如果我们将注意力限制在每一步总是向下或向右移动的路径上，那么答案是“是”。

要看到这一点，请注意我们总共需要向下跳 5 跳，向右跳 5 跳。假设我们选择了一条这样做的路径（但不一定按该顺序）。由于所有向下的跃点具有相同的成本，并且所有向右的跃点具有相同的成本，我们可以通过按顺序考虑每个跃点来找到路径的总成本，为每个向下跳写一个 6，为每个向右跳写一个 1，然后将列表加在一起。

例如，路径的成本RRDDRDRDDR是1 + 1 + 6 + 6 + 1 + 6 + 1 + 6 + 6 + 1。

现在我们可以看到一些有趣的东西。具有 5 个向下跳和 5 个右跳的不同路径将具有相同的 56秒和 51秒列表，只是以不同的顺序求和。我们现在可以观察到加法是可交换的，并得出结论这两个和必须相等。也就是说，任何向下和向右移动的路径都具有与其他路径相同的总长度 ( 35)。

鉴于此，假设底层图确实是一个网格，您的生成树与其他任何树一样好。