Mei*_*eir 11 algorithm treenode graph-theory energy
我有一个(理论上)网络,有N个节点,每个节点都有自己的固定位置.每个节点每个周期发送一条消息,需要直接或通过其他节点到达根节点.
从节点A向节点B发送消息的能量成本是它们之间的距离,平方.
挑战在于如何以树形格式链接这些节点以产生最节能的网络.
例如,有两种可能的方式来链接这些节点,左边的节点更节能.
我正在研究遗传算法来解决这个问题,但我想知道是否有人有任何其他想法,或者知道任何相关的开源代码.
编辑:网络的另一个方面,我忘了提到,每个节点都是电池供电的.因此,如果我们通过同一节点路由太多消息,那么该节点的电池将耗尽,导致网络出现故障.网络的能效是通过在任何节点电池耗尽之前可以从每个节点成功传输到根节点的消息来衡量的.
编辑#2:对于问题原始文本中的遗漏,我很抱歉.不管怎么说,你之前的一些答案并不是我想要的,但我不熟悉MST算法,所以感谢你告诉我它们.
为了让事情更清楚,让我补充一点:
所有节点每个周期发送一个自己的消息,包括内部节点.内部节点还负责中继它们收到的任何消息.这增加了电池的压力,如果他们发送了他们自己的附加信息.目标是在任何节点电池耗尽之前最大化循环次数.
在不考虑电池最小化的情况下，您要寻找的是最短路径生成树，它与最小生成树类似，只是具有不同的“成本”函数。（您可以运行Dijkstra 算法来计算最短路径生成树，因为成本似乎总是为正。）
但这并未考虑电池最小化。在这种情况下，（我不太确定您首先要最小化的是什么）您可能需要研究Min-cost max flow。然而，这将首先优化（最大化）“流量”，然后再最小化成本。这可能是理想的，也可能不是理想的。
要创建顶点约束（每个节点只能操作k消息），您只需要创建第二个图，在其中为每个G_1节点添加一个额外的顶点- 并让流成为任何您的约束，在本例中为 ，成本为。所以基本上如果原始图中有一条边，那么在 中，每条边都会有一条边。实际上，您正在创建第二层顶点，将流限制为。（根的特殊情况，除非您还希望对根进行消息约束。）u_iv_iv_iu_ik+10(a,b)GG_1(u_a,v_b)k
标准最大流解决方案G_1应该足够了 - 一个源指向每个顶点，流为1，以及一个连接到根的接收器。如果 的 maxflow是，即顶点数，则有一个解决方案G_1（随 变化）。kG_1N