具有二进制偏好的简单配对匹配算法

Question

我正在寻找一对匹配算法来解决一个非常简单的问题：

• 人们自我分配为A或B类或A和B两类。
• 他们表示偏好:与A类、B类或其中之一的人匹配。
• 每个人都成对(除非是奇数)。如果双方的偏好都得到满足，则得分2分；如果1人的偏好得到满足，则得分1分，否则，得分为0。

我想要找到一个算法，为任何给定的人产生最优的结果。

附加要求:一个人不成对的机会绝不能通过增加一个类别或偏好来减少。(不过，如果删除某个类别或偏好会损害他们的机会，那也没关系。)

对于更复杂的场景，比如稳定婚姻问题，有一些算法，但我的情况似乎很简单--我只是不知道该如何去做。总人数将在20-50的范围内，所以低效的解决方案很好。

示例：

"1. A -> A，B“是指人1属于A类，并希望与A或B中的人匹配。

假设我们有这些人：

1. A -> A，B
2. A -> B
3. A -> B
4. A -> A
5. B -> A
6. B -> A

我认为通过检验我们可以看出，最优解是1+4，2+5，3+6。

成本函数

如果上面的文字描述不够正式，我的意思是：

• A->A + A->A，B->B + B->B ->B+B-> A->B + B->A: 2分
• A->A + B-> A ->B + B->B ->B+ A-> A -> B ->A ->A+ B->B: 1点
• A->A + B->B，A->B + A-> B ->A + B->A: 0

Answer 1

这是一种低效的解决方案，但我认为它有效。首先，我使用的阶级人，有三个私人态度的身份，类别和偏好。

public class Person {
private String category;
private String pref;
private int id;

/**
 * The strings a,b will be A for A, B for B and A,B for Both 
 * @param a expressing the category that they want to go
 * @param b expressing the preference
 */
Person(int id,String a,String b){
    this.id=id;
    category=a;
    pref=b;
}

public String getCategory(){
    return category;
}

public String getPref(){
    return pref;
}

public int getId(){
    return id;
}

}

在主类中，我从一个名为a.txt的txt文件中获取数据，每个人的格式必须是A、-> B，就像您给出的格式一样。它运行3种私人方法，先得到2分的比赛，然后计算出1分，然后补上其余的。

import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;

public class Pairing {
private ArrayList<Person> queue;
private ArrayList<String> matches;
private int ids;

public Pairing() {
    queue = new ArrayList<>();
    ids = 0;

}

public void addPerson(String category, String preference) {
    queue.add(new Person(ids, category, preference));
    ids++;

}

public ArrayList<String> getMatches() {
    matches = new ArrayList<>();
    System.out.println(ids);
    checkFor2Points();
    checkFor1Point();
    //matchTheRest();
    return matches;
}

/**
 * At the begin matches the persons who has strict preferences and belongs
 * in the first 2 categories, then uses the flexibility that A,B category
 * provides to find the rest matches that will give 2 points.
 */
private void checkFor2Points() {
    Person c, p;
    for (int j = 0; j < queue.size(); j++) {
        p = queue.get(j);
        System.out.println(p.getCategory() + " " + p.getPref());
        if ((p.getCategory().equals("A") || p.getCategory().equals("B")) && (p.getPref().equals("A") || p.getPref().equals("B"))) {
            for (int i = 0; i < queue.size(); i++) {
                c = queue.get(i);
                if (c.getPref().equals(p.getCategory()) && c.getCategory().equals(p.getPref()) && c.getId() != p.getId()) {
                    matches.add(p.getId() + 1 + "+" + (c.getId() + 1));
                    queue.remove(c);
                    queue.remove(p);
                } else if (c.getCategory().equals("A,B") && c.getPref().equals(p.getCategory()) && c.getId() != p.getId()) {
                    matches.add(p.getId() + 1 + "+" + (c.getId() + 1));
                    queue.remove(c);
                    queue.remove(p);
                }
            }
        }
    }
    for (int j = 0; j < queue.size(); j++) {
        p = queue.get(j);
        if (p.getPref().equals("A,B")) {
            for (int i = 0; i < queue.size(); i++) {
                c = queue.get(i);
                if (c.getPref().equals(p.getCategory()) && c.getId() != p.getId()) {
                    matches.add(p.getId() + 1 + "+" + (c.getId() + 1));
                    queue.remove(c);
                    queue.remove(p);
                }
            }
        }
    }

}

private void checkFor1Point() {
    Person c, p;
    for (int j = 0; j < queue.size(); j++) {
        p = queue.get(j);
        for (int i = 0; i < queue.size(); i++) {
            c = queue.get(i);
            if ((p.getCategory().equals(c.getPref()) || p.getPref().equals(c.getCategory())) && p.getId() != c.getId()) {
                matches.add(p.getId() + 1 + "+" + (c.getId() + 1));
                queue.remove(c);
                queue.remove(p);
            }
        }
    }

}

private void matchTheRest() {
    for (int i = 0; i < queue.size(); i += 2) {
        matches.add(queue.get(i).getId() + "+" + queue.get(i + 1).getId());
        queue.remove(queue.get(i));
        queue.remove(queue.get(i + 1));
        if (queue.size() == 1) {// that means that the ids is an odd number
            return;
        }
    }
}

/**
 * @param args the command line arguments
 * @throws java.io.FileNotFoundException
 */
public static void main(String[] args) throws FileNotFoundException, IOException {
    String getLineString;
    String toSplit[];
    BufferedReader in = new BufferedReader(new FileReader("a.txt"));
    Pairing pair = new Pairing();
    getLineString = in.readLine();
    while (getLineString != null) {
        toSplit = getLineString.split(" -> ");
        pair.addPerson(toSplit[0], toSplit[1]);
        getLineString = in.readLine();
    }
    ArrayList<String> pairs = pair.getMatches();
    for (int i = 0; i < pairs.size(); i++) {
        System.out.println(pairs.get(i));
    }

}

}