我很好奇是否有一些更高级别的理论/方法/算法来解决我遇到的这个问题.
我正在研究网络路由问题(专有无线电网络).举例来说,我有一个由5个设备组成的网络.对于每个设备,我可以测量它能听到其他设备的程度.第0个根节点仅作为源使用.所以在表格形式中,我可能会得到类似的结果：
_0_ _1_ _2_ _3_ _4_ 1 | 21 - 42 55 0 2 | 0 63 - 18 20 3 | 20 0 0 - 0 4 | 0 0 13 0 -
每行表示该设备可以听到其他5个源的情况.我想要做的是对它们进行排序,以便每个设备从前面的元素中获得最佳的和信号.所以对于这个简单的情况,排序可能是1,3,2,4.但它也可能是3,1,4.事实上,这第二个会更好,因为1可以听到0和3. 3,4也可以.
我正在尝试确定我可以使用哪种算法来订购这些算法.有一些旅行推销员,我不需要“最好的”.只是一个非常好的排序.我需要扩展到9个具有10个源的设备.
这个问题可以建模为
minimum feedback arc set problem,这是一个NP难问题.原始图是一个完整的有向图,每条边的权重(v0,v1)是从v0到v1的信号强度.在计算最大反馈弧设置之后,拓扑排序将给出具有最大总信号的排序.
