我经营着一个体育网站,根据人们以前的会议情况来对对方进行排名通常是很有用的。
参见此示例数据集:

左边是原始的“未排序”视图。右边是正确排序的列表(在我看来)。
每个方块显示了他们互相竞争的次数,以及胜利的百分比。他们的阴影是根据百分比。
我有一个网页,与“向上”和“向下”控制与每一行,我可以手动推动他们,直到我得到我想要的。
我只是不太确定有什么最好的方法来实现这一点。
每一行末尾的数字是我粗略计算出来的一个快速想法,它等于整个行的总和(百分比-50*列号)。正如您所看到的,它们做得相当好,只有前两行是“错误的”。不过,他们并不重视会议次数,只考虑获胜的百分比。
最后的列数也会根据行的顺序而变化,通过比较图像中的左表和右表可以看出,因此对初始值的排序不会有那么好的效果。循环一个排序+重新计算几次可能会完成任务。
我希望我能拼凑些东西让这件事成功..。但是我觉得我会有一些更好的想法,我都会听的。
发布于 2015-06-19 16:20:42
锦标赛是一个图,其中每对顶点之间正好有一个有向边;要从输入中创建这样一个图,您可以为每个玩家创建一个带有顶点的图,然后将两个玩家之间的每一个边“指向”赢得大多数游戏的玩家的方向(您将需要以某种方式打破关系)。
如果您这样做,并且没有循环A>B>.>我在这个图中提到的类型的A,那么这个图是传递的,您可以使用图的拓扑排序命令玩家。这只需要线性时间的边数,即O(n^2)对n个玩家。
如果有这样的循环,那么玩家就没有“完美”的顺序:任何命令都会在他们击败的某个玩家之后放置至少一个玩家。在这种情况下,一个合理的选择是寻找秩序,以尽量减少这些“边缘违规”的数量。这是计算机科学中一个研究得很好的NP难题,称为比赛中的最小反馈弧集(FAST)。反馈弧集是一组有向边(“弧”),如果从图中删除,就会留下没有有向圈的图--然后就可以像以前一样使用拓扑排序很容易地转换成一个顺序。
本论文描述了最近对这个问题的一次攻击。我还没有读过这篇论文,但这是一个活跃的研究领域,所以算法可能相当复杂--但它可能会给你一些想法,如何创建一个运行速度更慢的更简单的算法(但在如此小的实例上运行得可接受的速度),或者如何创建一个启发式算法。
发布于 2015-06-19 20:54:53
为了添加到j_random的答案中,您可以使用类似于Tarjan强连通分量算法的方法来隔离循环。在强连接组件中,可以使用另一种方法对项进行排序。
https://stackoverflow.com/questions/30941465
复制相似问题