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

Question

我正在为一个非常简单的问题寻找配对匹配算法:

• 人们 self 分配到 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，A->B + B->A:2 分
• A->A + B->A，A->B + B->B，A->B + A->A，B->A + B->B:1 分
• A->A + B->B，A->B + A->B，B->A + B->A:0 分

Answer 1

这是一种低效的解决方案，但我认为它可行。首先，我使用具有 3 个私有(private)态度 id、类别和偏好的类 person。

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 个私有(private)方法来首先获得给出 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));
    }

}