基于二进制比较对数组进行排序，同时最大限度地减少不及物试验
Sort array based on binary comparisons while minimizing intransitive trials
我有 15 个城市的列表。我从可能的 15*14/2=105 对城市中随机抽取 70 对。对于 70 对中的每一对，我要求我的参与者决定城市 A 是否比城市 B 大。
重要的是，有时参与者会做出 'mistakes' 并给出与他们之前的答案不相符的答案。 （即，它违反了传递性）。
我需要一种方法来根据每个参与者的反应对我的城市进行排序，从而最大限度地减少违反传递性的试验次数。
我不需要城市的实际 顺序，因为可能没有唯一的解决方案。我只需要计算每个参与者给出的不及物答案的（最小）数量。
除了使用穷举搜索，我还能怎么做？
编辑：举个例子，以城市 A、B、C、D 和 E 为例。参与者 Jon Doe 认为城市的正确顺序（从小到大）是 ABCDE。我不关心他是否真的正确，我只关心他的回答（如下所列）与他的信念相符的程度。
在三个独立试验中，乔恩回答如下：
试验 1：A < B
试验 2：B < C (+)
试验 3：C < D
试验 4：D < E (+)
试验 5：E > B (*)
因此，试题 5 (*) 中的答案与试题 2 和试题 4 中的答案不一致。要么一项试验（第 5 项）不符合 Jon 的信念，要么 2 项试验（2 和 4）不符合。我不想弄清楚哪个是 Jon 的信念 (ABCDE)，我只需要知道 Jon Doe 的 "minimum number of intransitive answers" 是 1。
所以...这个问题可能很有趣，但不清楚你想要什么。您需要对您的城市进行排序但是您不需要他们的顺序？
尽量减少违反传递性的试验次数...你是怎么做到的？不及物性存在于你得到的答案中，而不是你对它们所做的任何事情。
计算每个参与者给出的不及物答案的数量...如果你有每个主题的所有答案，那么不一致是直接图中的一个循环，其中节点是城市，一个节点指向另一个当且仅当参与者说它的城市比另一个的大。有一些算法，请参阅 this 问题。
当然，一条边可能是多个循环的一部分，在这种情况下，我们可以尝试找到我们必须删除的最小边数，以使其成为非循环的。不幸的是，问题is NP complete；所以你不会找到一个快速的答案。但是，由于您的数字相当低，您可能会设法找到一个还过得去的快速解决方案。
希望这对您有所帮助。
我有 15 个城市的列表。我从可能的 15*14/2=105 对城市中随机抽取 70 对。对于 70 对中的每一对，我要求我的参与者决定城市 A 是否比城市 B 大。 重要的是，有时参与者会做出 'mistakes' 并给出与他们之前的答案不相符的答案。 （即，它违反了传递性）。
我需要一种方法来根据每个参与者的反应对我的城市进行排序，从而最大限度地减少违反传递性的试验次数。
我不需要城市的实际 顺序，因为可能没有唯一的解决方案。我只需要计算每个参与者给出的不及物答案的（最小）数量。
除了使用穷举搜索，我还能怎么做？
编辑：举个例子，以城市 A、B、C、D 和 E 为例。参与者 Jon Doe 认为城市的正确顺序（从小到大）是 ABCDE。我不关心他是否真的正确，我只关心他的回答（如下所列）与他的信念相符的程度。
在三个独立试验中，乔恩回答如下：
试验 1：A < B
试验 2：B < C (+)
试验 3：C < D
试验 4：D < E (+)
试验 5：E > B (*)
因此，试题 5 (*) 中的答案与试题 2 和试题 4 中的答案不一致。要么一项试验（第 5 项）不符合 Jon 的信念，要么 2 项试验（2 和 4）不符合。我不想弄清楚哪个是 Jon 的信念 (ABCDE)，我只需要知道 Jon Doe 的 "minimum number of intransitive answers" 是 1。
所以...这个问题可能很有趣，但不清楚你想要什么。您需要对您的城市进行排序但是您不需要他们的顺序？
尽量减少违反传递性的试验次数...你是怎么做到的？不及物性存在于你得到的答案中，而不是你对它们所做的任何事情。
计算每个参与者给出的不及物答案的数量...如果你有每个主题的所有答案，那么不一致是直接图中的一个循环，其中节点是城市，一个节点指向另一个当且仅当参与者说它的城市比另一个的大。有一些算法，请参阅 this 问题。
当然，一条边可能是多个循环的一部分，在这种情况下，我们可以尝试找到我们必须删除的最小边数，以使其成为非循环的。不幸的是，问题is NP complete；所以你不会找到一个快速的答案。但是，由于您的数字相当低，您可能会设法找到一个还过得去的快速解决方案。
希望这对您有所帮助。