我有一组评价一组n个对象的r评论者.每个评论者独立地生成他或她选择排名的对象的有序列表.目标是生成一个列表,该列表是各种有序列表的排序规则.我们可以假设每个评论者的观点具有相同的权重.
这与大多数合并和排序列表问题的不同之处在于没有全局排序.一个评论者可以评价A> B,而另一个评论者评价B> A.如上所述,每个评论者不一定评价每个对象.
我目前的想法是将每个评论者的列表分解为列表中每个m*(m-1)*.5个唯一条目对的一组有序元组,其中m是评级的对象数.现在从所有评论者那里获取所有元组.对于给定的组合(a,b)找到所有这样的元组并将多数投票(那些投票)作为a <b的确定者.
现在我有一组有序的元组代表了所有人的智慧.但是如何将这些变成一个有序列表呢？我可以从随机选择的一对对象开始,然后对它们进行排序,然后按正确的顺序添加另一个,但输出将取决于我选择从哪一个开始.也可能有循环.
我很欣赏任何想法.
Jon*_*ker 27
您导航的问题空间基本上(同构)投票理论的一个子集,即投票和结果都是有序候选人列表的部分.
您可能会从阅读以下内容中受益:
根据我对投票理论的了解,我会给你一个建议:如果你有理由相信O(n 3)算法对你的特定数据集是可行的,那就试试Schulze方法.否则,Borda Count是唯一列出的方法,它在O(n)时间内运行并将排名作为选票输入,因此坚持下去.
jkr*_*ill 10
一个似乎优雅且仍然需要做的事情的解决方案是将每个排序转换为从1到0的分数,其中1是给定评论者列表中的第一个(顶部)排名项目,0是他们的最后一个(底部项目) )并且其间的所有项目都获得线性缩放分数.因此,如果评论者1只对3个项目进行排名,那么他们将获得该分数为1,0.5和0的分数.然后,您只需获取每个项目的平均分数即可生成整理列表.可以通过项目的"评论"数量来打破关系(以便3个评论者一致标记为最佳的项目在最终列表中看起来比2个评论者一致标记为最佳的项目更高,等等)
您的要求"目标是生成一个列表,该列表是各种有序列表的整理.我们可以假设每个评论者的观点具有相同的权重." 这种简单的算法肯定能满足这一要求,但是一旦你深入研究这些问题,这类问题往往会有一些复杂的要求.
合并排名有些不简单。我认为也许您需要更清楚地了解“有序列表的排序规则”的含义 - 即您希望它具有哪些属性？
例如，请参阅康奈尔大学的这些 CS 课程笔记。考虑到全球排名应该具有的一些合理的属性，实际上不可能创建一个绝对满足这些属性的算法。您可能需要在您所接受的全球排名的合理属性方面做出妥协。