不一致（非传递）人类偏好的排序算法

Question

7

假设我有一个文件，每行都有一个幽默笑话。我想根据我发现的有趣程度对这些笑话进行排序。我的第一个想法是实现任何排序算法（最好是尽可能少地进行比较），并使比较算法使用我的输入；我只需坐在那里选择它呈现给我的每个笑话对中更有趣的那个。

但是存在一个问题。我的笑话喜好不是一个全序。它缺乏传递性。例如，当提出它们时，我可能认为B比A更有趣，C比B更有趣，但当提出A和C时，我不知怎么会发现A比C更有趣。如果“>”表示“比…更有趣”，则这意味着C>B和B>A并不意味着C>A。所有排序算法的正确性都取决于此。

但似乎仍然应该有一种算法，可以对笑话列表进行排序，以便顶部的笑话比其他笑话更受欢迎，底部的笑话比其他笑话不太受欢迎，即使有个别例外也是如此。

我不知道如何在Google上搜索这个。是否有这种偏好排序的算法？这里的答案不适用，因为它强制用户的偏好是传递性的。

- nebuch

2

你能完成你的例子吗？如果你有三个笑话 A、B、C，且你发现 B 比 A 更有趣，C 比 B 更有趣，A 比 C 更有趣，你期望在输出中看到它们的什么顺序？另外，输入的只有你一个人吗？ - Jason C

请注意，您的笑话偏好甚至不是部分顺序！我想知道是否有任何投票系统允许选民说“ A > C”，而不提供任何其他投票。如果有的话，那么您可能可以使用其中一个系统，只需假装您的每个比较偏好来自不同的选民。 - ruakh

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - nebuch

@nebuch 好的，如果这三个笑话是更大列表的一部分，你希望它们在那个更大的列表中出现的顺序是什么？ - Jason C

因为如果你比较每一对笑话，那么你实际上可以数一下每个笑话比多少个笑话更有趣，然后在这些计数上进行确定性排序。 - ruakh

显示剩余7条评论

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- vowel-house-might · Accepted Answer

如果您将决策表示为有向图，其中每个笑话都是一个节点，每个有向边表示一个笑话比另一个笑话更好，则可以通过构造遵循边并恰好访问每个节点的路径来检索排序。

这种类型的图称为锦标赛，路径是哈密顿路径。我有好消息告诉您，如果图形是强连通的，则已经证明存在哈密顿路径。强连通只意味着可以从每个节点到达每个节点，遵守边的方向，因此请继续添加边直到达到此目的。