等距生成树的优缺点
今天是新年，仍然无法解决我关于生成树算法的问题。我还不能插入图片，所以我必须尝试用文字解释环境。
它有 36 个节点，并且到每个节点的距离是均匀的。问题是，如果距离是偶数，那么从 ID 为 1 的节点（根）到最后一个 ID 为 36 的节点采用哪种方式传递消息并不重要。因为距离是偶数，所以不会节省时间、能源或消息保存算法对吗？我希望有人理解我
编辑的问题：
环境
<前><代码>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 并不重要，因为成本仍然相同。
我的生成树算法
- 启动时，仅标记根。
- 根向其邻居发送搜索消息
- 如果一个节点没有被标记，当它收到其他节点的搜索消息时：
- 它标记自己
- 选择 ID 最低的节点作为“父节点”，并对其他节点回复“非父节点”
- 如果该节点已被标记，则回复“非父节点”
- 如果节点已被标记并收到父消息，则会将发送者标记为子节点
我无法向你们展示流程图，因为我没有插入图像的权限。
伪代码（没做过）
结论 - 在这里我应该写下我的算法的优点和缺点，但现在我不能想想有什么优点和缺点
It's new year day and still can't solve my problem about a spanning tree algorithm. I can't insert picture yet so I have to try to explain the enviroment with words.
It's 36 nodes and the distance to every nodes is even. The question is if the distance is even, it doesn't matter which way to pass message from node with ID 1 (the root) to the last node with ID 36. Because the distance is even there's no time saving, energy saving or message saving algorithm right? I hope someone understand my question
edited:
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
This is my choice of spanning tree. Node with ID 36 send it information thru 30,24,18,12,6,5,4,3,2,1 (one is the root) and then node 1 send information to the base station. Because it doesn't have any cost it doesn't really matter which path I choose to send the information from node 36 to node 1 because the cost will still be the same.
My Spanning tree Algorithm
- When start, only the root is marked.
- The root send search message to it neighbor
- If a node is not marked, when it recieves search messages from other nodes:
- it mark itself
- Select the nodes with lowest ID as a "parent" and reply "non-parent" to the other nodes
- If the node is already mark, it replies "non-parent"
- If a node is already marked and recieve a parent message it marks the sender as a child
I can't show you guys the flowchart because I don't have the privilege to insert images.
Pseudo Code (haven't done it)
Conclusion - Here I should write down the advantage and disadvantage of my algorithm, but right now I can't think of any advantage and disadvantage
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
我认为“偶”的意思是“无论我从哪里开始，在我的图表中水平移动一个节点的距离始终为 1，垂直移动的距离始终为 6”。
那么你的问题听起来像“从左上角到右下角的所有路径的总长度都相同吗？”如果我们将注意力限制在每一步总是向下或向右移动的路径上，那么答案是“是”。
要看到这一点，请注意我们总共需要向下跳 5 次，向右跳 5 次。假设我们选择一条这样做的路径（但不一定按该顺序）。由于所有向下的跳跃具有相同的成本，并且所有向右的跳跃具有相同的成本，因此我们可以通过按顺序考虑每个跳跃来找到路径的总成本，为每个向下跳跃写入 6，为每个向右跳跃写入 1，并将列表加在一起。
例如，路径
RRDDRDRDDR的成本为1 + 1 + 6 + 6 + 1 + 6 + 1 + 6 + 6 + 1。现在我们可以看到一些有趣的东西。具有 5 个下跳和 5 个右跳的不同路径将具有相同的 5 个
6和 5 个1列表，只是以不同的顺序求和。我们现在可以观察到加法是可交换的，并得出结论：这两个和必须相等。也就是说，任何向下和向右移动的路径都与其他路径具有相同的总长度 (35)。鉴于此，假设底层图确实是一个网格，那么您的生成树与其他生成树一样好。
By "even" I think you mean "Irregardless of where I start, the distance to move one node horizontally in my diagram is always 1, and the distance to move vertically is always 6."
Your question then sounds like "Do all paths from the upper left to the lower right have the same total length?" If we restrict our attention to paths that, at each step, always move either down or to the right, then the answer is "yes".
To see this, note we need in total to make 5 hops down, and 5 hops to the right. Suppose we pick a path that does so (but not necessarily in that order.) Since all downward hops have the same cost, and all rightward hops have the same cost, we can find the total cost of the path by considering each hop in order, writing a 6 for each downward hop and 1 for each rightward hop, and add the list together.
For example, the cost of path
RRDDRDRDDRis1 + 1 + 6 + 6 + 1 + 6 + 1 + 6 + 6 + 1.Now we can see something interesting. A different path with 5 down hops and 5 right hops will have the same list of 5
6s and 51s, just summed in a different order. We can now observe that addition is commutative, and conclude that these two sums must come out equal. That is, any path moving down and to the right has the same total length (35) as any other.Given that, your spanning tree is as good as any other, assuming the underlying graph really is a grid.