用于人类比较的列表排序算法

Question

这个问题曾被问过一次,但没有回答,所以我想我会再次询问我的具体情况.

我正在尝试开发一个应用程序,让您放入一个离散项目列表(例如,水果),它为您提供两者之间的比较.你选择你最喜欢的两个,然后重复这个过程,直到你最终有一个按这些对象的优先顺序排序的列表(在这个例子中,按顺序排列你最喜欢的水果).

问题在于,传统的排序策略,无论多快,都必然涉及更多的操作,而不是人类在任何合理的时间内完成的操作(即使列表短至50,因为我目前的测试列表是).

由于很明显没有一个保证排序算法的复杂度足够低,我想有些补贴必须要做.有没有办法跳过大块的排序？我考虑了一些根据他们"赢得"的比较为项目分配值的方法,然后在一段时间后停止排序并假设这些值给出正确的顺序,类似于您可能解决瑞士国际象棋的风格锦标赛,如果你不能完成足够的轮次来正常确定胜利者.我不知道这是否合情合理.

一个澄清我的意思的例子:说你有一份清单

Apple
Orange
Kiwi
Banana
Melon

它会为你提供比较

Do you prefer:
A Apple
B Kiwi

等等,直到你有一个看起来像的列表

Kiwi
Apple
Orange
Melon
Banana

这是你对这些水果的偏好顺序.

Answer 1

您喜欢什么水果？您的脑海中是否有一个完整有序的偏好列表，或者您是否有“比大多数人更喜欢”的水果、“比大多数人不太喜欢”的水果，以及您对其他水果没有任何强烈感觉的水果 - 或者你甚至没有尝试过。

您如何表述问题的问题在于您假设一个人的偏好是一个全序，它自然地编码为一个列表。实际上，一个人的偏好通常是一个偏序，它自然地被编码为有向无环图。

例如，对于水果集{Apple, Orange, Kiwi, Banana, Melon, Starfruit}，我可能有如下水果偏好：

Melon < Apple
Apple < Banana
Banana < Kiwi
Banana < Orange

根据用户输入获得偏序的一个好方法是模仿基数排序。首先，要求用户为每种水果选择他们是否喜欢、不喜欢、对此持中立态度或不知道。我会回答如下：

            Like Dislike Neutral Unknown
Apple                    x
Orange      x
Kiwi        x
Banana      x
Melon            x
Starfruit                        x

假设Dislike < Neutral < Like，这些答案编码了以下信息，尽管我只回答了与水果一样多的问题：

Melon < Apple
Apple < Orange
Apple < Kiwi
Apple < Banana

接下来，确定哪些答案获得最多的复选标记。在这种情况下，我似乎有 3 种水果我喜欢，1 种我不喜欢，1 种我感觉中立（除非涉及花生酱），1 种我从未尝试过（所以我对其他水果）。

因此，进一步研究我的偏好的自然地点是我喜欢的水果。问题是递归的：现在你想确定我在水果集中的偏好{Orange, Kiwi, Banana}。你可以问我我最喜欢哪种水果，我会点击Orange和Kiwi。这告诉你以下信息：

Banana < Orange
Banana < Kiwi

结合第一轮信息，您现在拥有：

Melon < Apple
Apple < Orange
Apple < Kiwi
Apple < Banana
Banana < Kiwi
Banana < Orange

Apple < Banana并Banana < Kiwi暗示Apple < Kiwi；Apple < Banana并Banana < Orange暗示Apple < Orange。因此，我们可以消除冗余信息，得到：

Melon < Apple
Apple < Banana
Banana < Kiwi
Banana < Orange