How to sort / sort a 2D dependency table

Question

I am curious if there is a higher level theory / approaches / algorithm to solve this problem.

I am working on the issue of network routing (proprietary radio network). As an example, I have a network of 5 devices. For each device, I can measure how well it can hear other devices. The 0th root node is only interesting as a source. So in tabular form, I could get something like:

_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 - 

Each line indicates how well this device can hear the other 5 sources. I want to sort them so that each device receives the best sums of signals from previous elements. Therefore, for this simple case, the order can be 1, 3, 2, 4 . But it could also be 3, 1, 2, 4 . In fact, this second would be better, because 1 could hear both 0 and 3. 3, 2, 1, 4 also worked.

I am trying to determine which algorithm I can use to organize them. There are few salespeople there, and I don't need the “best” look. Just probably a pretty good variety. I need to scale to 9 devices with 10 sources.

Any thoughts, help, pushing, tips, tricks appreciated.

Answer 1

This problem can be modeled as a minimal feedback problem , which is an NP-hard problem. The source graph is a complete directional graph, the weight of each edge (v0, v1) is the signal strength from v0 to v1 . After calculating the maximum set of the feedback arc, topological sorting will give an order having the maximum common signal.