2

我有一个 15 个城市的列表。我从可能的 15*14/2=105 对城市中随机抽取 70 对。对于 70 对中的每一对，我要求我的参与者判断 A 城市是否大于 B 城市。重要的是，有时参与者会犯“错误”并给出与他们之前的答案不相容的答案。（即，它违反了传递性）。

我需要一种方法来根据每个参与者的反应对我的城市进行排序，以最大限度地减少违反传递性的试验次数。

我不需要城市的实际顺序，因为可能没有唯一的解决方案。我只需要计算每个参与者给出的不及物答案的（最小）数量。

除了使用详尽搜索之外，我怎么能做到这一点？

编辑：举个例子，以城市 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 中的答案不兼容。要么一项试验（nr. 5）不符合 Jon 的信念，要么 2 项试验（2 和 4）不符合。我不在乎弄清楚 Jon 的信念（ABCDE）是什么，我只需要知道 Jon Doe 的“不及物答案的最小数量”是 1。

4

1 回答 1

2

所以......这个问题可能很有趣，但不清楚你想要什么。您需要对城市进行排序，但不需要它们的顺序？

尽量减少违反传递性的试验次数……你是怎么做到的？不及物性在于你得到的答案，而不是你对它们做了什么。

计算每个参与者给出的不及物答案的数量......如果你有每个主题的所有答案，那么不一致是直接图中的一个循环，其中节点是城市，如果参与者说它的节点指向另一个节点城市比其他城市大。有算法，见这个问题。

当然，一条边可能是多个循环的一部分，在这种情况下，我们可以尝试找到必须删除的最小边数，以使其成为非循环的。不幸的是，问题是 NP 完备的；所以你不会找到一个快速的答案。但是，由于您的数字相当低，您可能会设法找到一个相当快速的解决方案。

希望这可以帮助。

于 2015-08-03T09:27:14.063 回答