python - 如何对 2D 依赖表进行排序/排序

Question

我很好奇是否有更高层次的理论/方法/算法来解决我遇到的这个问题。

我正在处理网络路由问题(专有 radio 网络)。例如，我有一个包含 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, 2, 4。事实上，这一秒会更好，因为 1 可以同时听到 0 和 3。3, 2, 1, 4 也可以。

我正在尝试确定可以使用哪种算法来对这些进行排序。有一些旅行推销员，我不需要“最好”的那种。只是一种可能相当不错的类型。我需要使用 10 个源扩展到 9 台设备。

任何想法、帮助、插入、提示、暗示表示赞赏。

Answer 1

这个问题可以建模为 minimum feedback arc set problem ，这是一个 NP-hard 问题。原图是一个完全有向图，每条边(v0, v1)的权重为v0到v1的信号强度。计算出最大反馈弧集后，进行拓扑排序，得到总信号最大的排序。