如何对依赖关系的2D表进行排序/排序

发布时间：2020-12-13 20:48:00 所属栏目：百科来源：网络整理

导读：我很好奇是否有一些更高级别的理论/方法/算法来解决我遇到的这个问题. 我正在研究网络路由问题(专有无线电网络).举例来说,我有一个由5个设备组成的网络.对于每个设备,我可以测量它能听到其他设备的程度.第0个根节点仅作为源使用.所以在表格形式中,我可能会得

我很好奇是否有一些更高级别的理论/方法/算法来解决我遇到的这个问题.

我正在研究网络路由问题(专有无线电网络).举例来说,我有一个由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的信号强度.在计算最大反馈弧设置之后,拓扑排序将给出具有最大总信号的排序.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!