基于1对1选择的协同排序算法

Question

我不知道这是否是一个更加数学的对象,但我潜伏在mathexchange并且看起来不是面向算法,所以我更喜欢在这里问.

我想知道以下问题是否已经解决:

假设我们有10个对象,我们希望根据它们对它们进行排序.如果排序属于一个人,没问题,我们要求他回答我们的问题(使用bubblesort或类似的)并回答,在一堆问题之后,他将获得最终排名.

现在让我们说有10个人.我们希望在全球排名.变得困难,任何人都可以找到解决问题的方法(例如,向每个人询问"第一个最喜欢的三个"并分配点数,然后进行排名);

我希望更科学,因此更具算法性,换句话说,使用冒泡排序(其实现,就像一系列问题1vs1对象,并询问你最喜欢的是什么,然后进行排名),最大限度地减少要问的问题.

因此,我们应该有一种方法对对象进行全局排名,同时分配给那些将要排序,重要的人,如果可能的话,不要等待任何人按照百分比和统计数据进行排名.

希望能够很好地解释我的问题,如果您觉得不适合这个团队,请告诉我并转让其他服务.谢谢!

Answer 1

在我之前的回答没有希望的结果之后，我决定开始解决这个问题的一个实际方面：如何以最佳方式提出问题来确定一个人的偏好。

跳过不必要的问题

如果要订购 10 件商品，则需要比较 45 对商品。这 45 个决策组成了一个三角矩阵：

   0  1  2  3  4  5  6  7  8
1  >
2  >  <
3  <  >  =
4  =  >  <  =
5  >  <  <  <  >
6  <  >  >  <  >  <
7  <  >  <  =  =  <  >
8  <  <  =  >  =  <  <  <
9  =  >  >  <  <  >  >  =  >

在最坏的情况下，您必须先问一个人 45 个问题，然后才能填写整个矩阵并了解他在 10 个项目中的排名。但是，如果一个人更喜欢第 1 项而不是第 2 项，并且更喜欢第 2 项而不是第 3 项，您可以推断他更喜欢第 1 项而不是第 3 项，并跳过该问题。事实上，在最好的情况下，只需 9 个问题就足以填写整个矩阵。

回答二分问题以推断项目在有序列表中的位置与填充二叉搜索树非常相似。然而，在一个 10 项的 b 树中，最好的情况是 16 个问题，而不是我们理论上的最小值 9；所以我决定尝试寻找另一种解决方案。

下面是一个基于三角矩阵的算法。它以随机顺序提出问题，但在每个答案之后，它会检查可以推断出哪些其他答案，并避免提出不必要的问题。

实际填写45题矩阵所需题数平均为25.33，90.5%的实例在20-30范围内，最小值为12，最大值为40（在10万个样本上测试，随机问题顺序，没有“=”答案）。

当系统地问问题时（从上到下，从左到右填充矩阵），分布非常不同，平均值较低，为 24.44，低于 19 的奇怪截止值，少数样本上升到最大值 45，以及奇数和偶数之间的明显区别。

我没有预料到这种差异，但它让我意识到这里有优化的机会。我正在考虑与 b-tree 想法相关的策略，但没有固定的根。那将是我的下一步。（更新：见下文）

   0  1  2  3  4  5  6  7  8
1  >
2  >  <
3  <  >  =
4  =  >  <  =
5  >  <  <  <  >
6  <  >  >  <  >  <
7  <  >  <  =  =  <  >
8  <  <  =  >  =  <  <  <
9  =  >  >  <  <  >  >  =  >

更新 1：按正确的顺序提问

如果你按顺序提问，从上到下填满三角矩阵，你实际上在做的是：保持你已经问过的项目的初步顺序，一次引入一个新项目，比较它与以前的项目一起，直到您知道将其插入到初步顺序中的位置，然后继续下一个项目。

这个算法有一个明显的优化机会：如果你想将一个新项目插入到一个有序列表中，而不是依次将它与每个项目进行比较，而是将它与中间的项目进行比较：这会告诉你新项目的哪一半进入；然后将它与那一半中间的项目进行比较，依此类推......这将最大步数限制为 log2(n)+1。

下面是使用此方法的代码版本。在实践中，它提供了非常一致的结果，平均所需题数为 22.21，不到最大值 45 的一半。而且所有结果都在 19 到 25 范围内（在 100,000 个样本上测试，没有“=”答案）。

随着项目数量的增加，这种优化的优势变得更加明显；对于 20 个项目，在可能的 190 个问题中，随机方法给出的平均值为 77（40.5%），而优化方法给出的平均值为 62（32.6%）。在 50 个项目中，即 300/1225 (24.5%) 与 217/1225 (17.7%)。

function PrefTable(n) {
    this.table = [];
    for (var i = 0; i < n; i++) {
        this.table[i] = [];
        for (var j = 0; j < i; j++) {
            this.table[i][j] = null;
        }
    }

    this.addAnswer = function(x, y, pref, deduced) {
        if (x < y) {
            var temp = x; x = y; y = temp; pref *= -1;
        }
        if (this.table[x][y] == null) {
            this.table[x][y] = pref;
            if (! deduced) this.deduceAnswers();
            return true;
        }
        else if (this.table[x][y] != pref) {
            console.log("INCONSISTENT INPUT: " + x + ["<", "=", ">"][pref + 1] + y);
        }
        return false;
    }

    this.deduceAnswers = function() {
        do {
            var changed = false;
            for (var i = 0; i < this.table.length; i++) {
                for (var j = 0; j < i; j++) {
                    var p = this.table[i][j];
                    if (p != null) {
                        for (var k = 0; k < j; k++) {
                            var q = this.table[j][k];
                            if (q != null && p * q != -1) {
                                changed |= this.addAnswer(i, k, p == 0 ? q : p, true);
                            }
                        }
                        for (var k = i + 1; k < this.table.length; k++) {
                            var q = this.table[k][j];
                            if (q != null && p * q != 1) {
                                changed |= this.addAnswer(i, k, p == 0 ? -q : p, true);
                            }
                        }
                        for (var k = j + 1; k < i; k++) {
                            var q = this.table[i][k];
                            if (q != null && p * q != 1) {
                                changed |= this.addAnswer(j, k, p == 0 ? q : -p, true);
                            }
                        }
                    }
                }
            }
        }
        while (changed);
    }

    this.getQuestion = function() {
        var q = [];
        for (var i = 0; i < this.table.length; i++) {
            for (var j = 0; j < i; j++) {
                if (this.table[i][j] == null) q.push({a:i, b:j});
            }
        }
        if (q.length) return q[Math.floor(Math.random() * q.length)]
        else return null;
    }

    this.getOrder = function() {
        var index = [];
        for (i = 0; i < this.table.length; i++) index[i] = i;
        index.sort(this.compare.bind(this));
        return(index);
    }

    this.compare = function(a, b) {
        if (a > b) return this.table[a][b]
        else return 1 - this.table[b][a];
    }
}

// CREATE RANDOM ORDER THAT WILL SERVE AS THE PERSON'S PREFERENCE
var fruit = ["orange", "apple", "pear", "banana", "kiwifruit", "grapefruit", "peach", "cherry", "starfruit", "strawberry"];
var pref = fruit.slice();
for (i in pref) pref.push(pref.splice(Math.floor(Math.random() * (pref.length - i)),1)[0]);
pref.join(" ");

// THIS FUNCTION ACTS AS THE PERSON ANSWERING THE QUESTIONS
function preference(a, b) {
    if (pref.indexOf(a) - pref.indexOf(b) < 0) return -1
    else if (pref.indexOf(a) - pref.indexOf(b) > 0) return 1
    else return 0;
}

// CREATE TABLE AND ASK QUESTIONS UNTIL TABLE IS COMPLETE
var t = new PrefTable(10), c = 0, q;
while (q = t.getQuestion()) {
    console.log(++c + ". " + fruit[q.a] + " or " + fruit[q.b] + "?");
    var answer = preference(fruit[q.a], fruit[q.b]);
    console.log("\t" + [fruit[q.a], "whatever", fruit[q.b]][answer + 1]);
    t.addAnswer(q.a, q.b, answer);
}

// PERFORM SORT BASED ON TABLE
var index = t.getOrder();

// DISPLAY RESULT
console.log("LIST IN ORDER:");
for (var i in index) console.log(i + ". " + fruit[index[i]]);

我认为这是您可以优化单个人的二元问题过程的范围。下一步是弄清楚如何询问几个人的偏好并将它们组合起来，而不会将相互冲突的数据引入矩阵。

更新2：根据多人的喜好排序

在试验（在我之前的答案中）不同的人会回答每个问题的算法时，很明显，相互冲突的偏好会创建一个包含不一致数据的偏好表，这对于排序算法中的比较没有用处。

本答案前面的两种算法提供了处理此问题的可能性。一种选择是用百分比投票而不是“之前”、“之后”和“相等”作为唯一选项来填写偏好表。之后，您可以搜索不一致之处，并通过更改最接近投票的决定来解决它们，例如，如果苹果对橘子是 80/20%，橘子对梨是 70/30%，梨对苹果是 60/ 40%，将偏好从“梨先于苹果”更改为“苹果先于梨”将是解决不一致的最佳方法。

另一种选择是跳过不必要的问题，从而消除偏好表中出现不一致的可能性。这将是最简单的方法，但问题的顺序会对最终结果产生更大的影响。

第二种算法将每个项目插入到初步顺序中，首先检查它是在前半部分还是后半部分，然后是在前半部分还是后半部分，依此类推……稳步放大正确的位置在不断减少的步骤。这意味着用于确定每个项目位置的决策序列的重要性逐渐降低。这可能是一个系统的基础，在这个系统中，更多的人被要求为重要的决定投票，而更少的人为不太重要的决定投票，从而减少每个人必须回答的问题数量。

如果人数远大于项目数，您可以使用这样的方法：对于每一个新项目，第一个问题被问到一半的人，然后每一个进一步的问题都被问到剩下的一半人. 这样一来，每个人每个项目最多只能回答一个问题，而对于整个列表，每个人最多只能回答与项目数量相等的问题。

同样，对于大量人群，有可能使用统计数据。这可以决定某个答案在哪个点产生了统计上显着的领先，并且该问题可以被视为已回答，而无需询问更多人。它还可用于决定投票必须接近多少才能被视为“平等”答案。

更新 3：根据问题的重要性询问分组

如更新 2 中所讨论的，此代码版本通过向人口的大子群提出重要问题并向较小的子群提出不太重要的问题来减少每个人的问题数量。7 题，最多需要 3 题才能找到正确的位置；因此，人口将被分成 3 组，其相对大小为 4:2:1。
该示例根据 20 人的喜好订购 10 件商品；任何人被问的最大问题数为 9。

function PrefList(n) {
    this.size = n;
    this.items = [{item: 0, equals: []}];
    this.current = {item: 1, try: 0, min: 0, max: 1};

    this.addAnswer = function(x, y, pref) {
        if (pref == 0) {
            this.items[this.current.try].equals.push(this.current.item);
            this.current = {item: ++this.current.item, try: 0, min: 0, max: this.items.length};
        } else {
            if (pref == -1) this.current.max = this.current.try
            else this.current.min = this.current.try + 1;
            if (this.current.min == this.current.max) {
                this.items.splice(this.current.min, 0, {item: this.current.item, equals: []});
                this.current = {item: ++this.current.item, try: 0, min: 0, max: this.items.length};
            }
        }
    }

    this.getQuestion = function() {
        if (this.current.item >= this.size) return null;
        this.current.try = Math.floor((this.current.min + this.current.max) / 2);
        return({a: this.current.item, b: this.items[this.current.try].item});
    }

    this.getOrder = function() {
        var index = [];
        for (var i in this.items) {
            index.push(this.items[i].item);
            for (var j in this.items[i].equals) {
                index.push(this.items[i].equals[j]);
            }
        }
        return(index);
    }
}

// PREPARE TEST DATA
var fruit = ["orange", "apple", "pear", "banana", "kiwifruit", "grapefruit", "peach", "cherry", "starfruit", "strawberry"];
var pref = fruit.slice();
for (i in pref) pref.push(pref.splice(Math.floor(Math.random() * (pref.length - i)),1)[0]);
pref.join(" ");

// THIS FUNCTION ACTS AS THE PERSON ANSWERING THE QUESTIONS
function preference(a, b) {
    if (pref.indexOf(a) - pref.indexOf(b) < 0) return -1
    else if (pref.indexOf(a) - pref.indexOf(b) > 0) return 1
    else return 0;
}

// CREATE TABLE AND ASK QUESTIONS UNTIL TABLE IS COMPLETE
var t = new PrefList(10), c = 0, q;
while (q = t.getQuestion()) {
    console.log(++c + ". " + fruit[q.a] + " or " + fruit[q.b] + "?");
    var answer = preference(fruit[q.a], fruit[q.b]);
    console.log("\t" + [fruit[q.a], "whatever", fruit[q.b]][answer + 1]);
    t.addAnswer(q.a, q.b, answer);
}

// PERFORM SORT BASED ON TABLE
var index = t.getOrder();

// DISPLAY RESULT

console.log("LIST IN ORDER:");
for (var i in index) console.log(i + ". " + fruit[index[i]]);

Answer 2

你的问题是艾睿定理的主题.简而言之,一般来说,你想做的事情是不可能的.

如果您仍想尝试,我建议在有向图中使用有向边来表示偏好; 类似多数的东西更喜欢A到B,包括边A-> B,并且在连接的情况下没有边缘.如果结果是有向无环图,恭喜您,您可以使用toposort订购商品.否则使用Tarjan的算法识别强连接组件,这是故障点.

总的来说,在我看来,摆脱这个难题的最好方法是获得分数而不是对项目进行排序.然后你只是平均得分.