稳定婚姻问题Rotation查找算法实现故障排查求助

我们正在实现Dan Gusfield 1987年论文《Three Fast Algorithms for Four Problems in Stable Marriage》第6-7页描述的稳定婚姻问题旋转查找算法，但代码出现以下问题：

• breakmarriage函数本不应失败退出，实际却触发失败分支，导致内存随机访问引发程序崩溃；
• 部分测试用例中，旋转总数正确，但无前驱的Rotation数量超出预期。

数据结构定义 #

#include <stdlib.h>

struct ResultsList {
    struct ResultsListElement* first;
    struct ResultsListElement* last;
};

struct ResultsListElement {
    char* value;    // 匹配结果
    struct ResultsListElement* next;
};

struct RotationList { // list_el
    char man;
    char woman;
    struct RotationList* next;
};

struct RotationNode {
    struct RotationList* rotation;
    int index;
    int missing_predecessors;
    struct SuccessorsList* successors;
};

struct SuccessorsList {
    struct RotationNode* value;
    struct SuccessorsList* next;
};

struct RotationsList { // free_rotations_list
    struct RotationsListElement* first;
    struct RotationsListElement* last;
};

struct RotationsListElement { // free_rotations_list
    struct RotationNode* value;
    struct RotationsListElement* next;
};

void appendResultsList(struct ResultsList* list, char* result){
    struct ResultsListElement *new = malloc(sizeof (struct ResultsListElement));
    new->value = result;
    new->next = NULL;
    if (list->first==NULL){
        list->first = new;
        list->last=new;
    }else{
        list->last->next = new;
        list->last = new;
    }
}

void appendRotationsList(struct RotationsList* list, struct RotationNode* rotation_node){
    struct RotationsListElement *new = malloc(sizeof (struct RotationsListElement));
    new->value = rotation_node;
    new->next = NULL;
    if (list->first==NULL){
        list->first = new;
        list->last=new;
    }else{
        list->last->next = new;
        list->last = new;
    }
}

算法实现代码 #

#include <stdlib.h>
#include "..\data_structures\data_structures.h"

#define false 0
#define true 1

char* gale_shapley(int, int*, int*);
int accept_proposal(int*, int, int, int, int);
struct RotationsList* find_all_rotations(int*, int*, int, char*);
void breakmarriage(char*, int, int, int*, int*, int*, int*, struct RotationsList*, struct RotationNode**, int*, int*, int);
void pause_breakmarriage(int*, char*, char*, char*, struct RotationsList*, int, int, struct RotationNode**, int*, int*);
void recursive_search(char*, int, struct RotationsListElement*, struct ResultsList*);


char* gale_shapley(int n, int* men_preferences, int* women_preferences) {
    int women_partners[n], men_free[n];
    for (int i = 0; i < n; i++) {
        women_partners[i] = -1;
        men_free[i] = true;
    }

    while (true) {
        int m = -1;
        for (int i = 0; i < n; i++) {
            if (men_free[i]){
                m = i;
                break;
            }
        }
        if (m == -1) {
            break;
        }

        for (int i = 0; i < n && men_free[m]; i++) {
            int w = men_preferences[m * n + i];
            if (women_partners[w] == -1) {
                women_partners[w] = m;
                men_free[m] = false;
            } else {
                int m1 = women_partners[w];
                if (accept_proposal(women_preferences, n, w, m, m1)) {
                    women_partners[w] = m;
                    men_free[m] = false;
                    men_free[m1] = true;
                }
            }
        }
    }
    char* matching = (char*)malloc(n * sizeof(char));
    for (char i = 0; i < n; i++) {
        matching[women_partners[i]] = i;
    }
    return matching;
}


int accept_proposal(int* women_preferences, int n, int w, int m, int m1) {
    for (int i = 0; i < n; i++) {
        if (women_preferences[w * n + i] == m) {
            return true;
        }
        if (women_preferences[w * n + i] == m1) {
            return false;
        }
    }
    return 0;
}


struct RotationsList* find_all_rotations(int* men_preferences, int* women_preferences, int n, char* top_matching) {
    struct RotationsList* free_rotations_list = (struct RotationsList*) malloc(sizeof (struct RotationsList));
    free_rotations_list->first=NULL;
    free_rotations_list->last=NULL;
    struct RotationNode** last_to_have_modified = (struct RotationNode**)malloc(sizeof (struct RotationNode) * n); // 记录每个男人最后被哪个旋转节点修改的指针数组
    char* m_i = (char*) malloc(sizeof (char) * n);
    char* inverted_bottom_matching = gale_shapley(n, women_preferences, men_preferences);
    char* bottom_matching = (char*)malloc(sizeof (char) * n);
    for(int i=0;i<n;i++){
        bottom_matching[inverted_bottom_matching[i]]=i;
    }
    
    int* marking = (int*) malloc(sizeof (int) * n); // -1=未标记，n=标记但未配对，其他值为前一个女人
    int rotation_index = 0; // 用于给旋转节点编号，对应already_added_predecessors的索引
    int* already_added_predecessors = (int*) malloc(sizeof (int) * (n*n)); // 用于减少旋转图中的重复边

    for (int j = 0; j < n; j++) {
        m_i[j] = top_matching[j];
        marking[j] = -1;
        last_to_have_modified[j] = NULL;
    }
    int* men_preferences_indexes = (int*) malloc(sizeof (int) * n);
    for (int j = 0; j < n*n; j++) {
        already_added_predecessors[j] = false;
    }
    // 排除不可能出现在稳定匹配中的偏好
    for (int j = 0; j < n; j++) {
        int k = 0; 
        while (men_preferences[j * n + k] != m_i[j]) {
            k++;
        }
        men_preferences_indexes[j] = k+1; // 跳过当前匹配的偏好，只保留后续的
    }

    int old_m = 0;
    while (true) {
        // STEP 1
        int m = -1;
        // 找到第一个在m_i和bottom_matching中匹配不同的男人
        for (int j = old_m; j < n; j++) {
            if (m_i[j] != bottom_matching[j]) {
                m = j; 
                old_m = j;
                break;
            }
        }

        if (m < 0) { // m_i等于bottom_matching，结束循环
            break;
        }
        
        // STEP 2
        char w = m_i[m];
        marking[w] = n;
        breakmarriage(m_i, m, n, men_preferences, men_preferences_indexes, women_preferences, marking, free_rotations_list, 
                      last_to_have_modified, &rotation_index, already_added_predecessors, w);
    }
    free(last_to_have_modified);
    free(m_i);
    free(marking);
    free(already_added_predecessors);
    free(men_preferences_indexes);
    free(inverted_bottom_matching);
    free(bottom_matching);
    return free_rotations_list;
}


void breakmarriage(char* M, int m, int n, int* men_preferences, int* men_preferences_indexes, int* women_preferences, int* marking,
                   struct RotationsList* free_rotations_list, struct RotationNode** last_to_have_modified, int* rotation_index, 
                   int* already_added_predecessors, int first_woman) {
    int i = 0;
    while (men_preferences[m * n + i] != M[m]) { // 是否需要？
        i++;
    }
    men_preferences_indexes[m] = i + 1;
    int former_wife = M[m]; // 论文中的w，即当前男人的配偶，需要解除婚姻
    char* reversed_M = (char*)malloc(sizeof (char) * n);
    char* old_reversed_M = (char*)malloc(sizeof (char) * n);
    for (i = 0; i < n; i++) {
        reversed_M[M[i]] = i;
        old_reversed_M[M[i]] = i;
    }
    int w, m1, breakmarriage_fail, k, old_marking;
    int previous_woman = first_woman;

    while(true) {
        breakmarriage_fail = true;
        // 遍历m的偏好列表
        // 循环内m会变成论文中的m'
        for (i = men_preferences_indexes[m]; i < n; i++) {
            w = men_preferences[m * n + i]; // 论文中的w
            // 获取w当前的配偶m1，并和m比较
            m1 = reversed_M[w];
            // 如果w更偏好m而非m1，解除(w,m1)并配对(w,m)
            if (marking[w] < 0 && accept_proposal(women_preferences, n, w, m, m1)) { // step 2a
                k = men_preferences_indexes[m]; // 更新索引
                while (men_preferences[k] != w) {
                    k++;
                }
                men_preferences_indexes[m] = k+1;
                reversed_M[w] = m;
                marking[w] = previous_woman;
                previous_woman = w;
                m = m1; // 新的未配对男人
                breakmarriage_fail = false;
                break;
            } else if (accept_proposal(women_preferences, n, w, m, old_reversed_M[w])) { // step 2b
                breakmarriage_fail = false;
                old_marking = marking[w];
                reversed_M[w] = m;
                pause_breakmarriage(marking, M, reversed_M, old_reversed_M, free_rotations_list, w, previous_woman, 
                                    last_to_have_modified, rotation_index, already_added_predecessors);
                reversed_M[w] = m1;
                if (former_wife == w) { // 3c: w = w'
                    reversed_M[w] = m;
                    free(reversed_M);
                    free(old_reversed_M);
                    return; // 返回step 1
                } else {
                    if (!accept_proposal(women_preferences, n, w, m, m1)) {
                        marking[w] = old_marking;
                        previous_woman = w;
                        continue; // 返回step 2
                    } else {
                        reversed_M[w] = m;
                        m = m1; // m1是否正确？还是应该是其他值？
                        break;
                    }
                }
            }
        }
        if (breakmarriage_fail) { // 无法为m找到稳定配对
            free(reversed_M);
            free(old_reversed_M);
            return;
        }
    }
}


void pause_breakmarriage(int* marking, char* M, char* reversed_M, char* old_reversed_M, struct RotationsList* free_rotations_list, int w, 
                         int previous_woman, struct RotationNode** last_to_have_modified, int* rotation_index, int* already_added_predecessors) {
    int no_predecessors = true;
    struct RotationList* prev_list_el = NULL;
    int w2 = w;
    int go_on = true;
    struct RotationNode* rotation_node = (struct RotationNode*)malloc(sizeof (struct RotationNode));
    rotation_node->missing_predecessors = 0;
    rotation_node->index = *rotation_index;
    rotation_node->successors=NULL;
    *rotation_index += 1;
    struct RotationsList* predecessors_list = (struct RotationsList*)malloc(sizeof (struct RotationsList)); // 记录当前旋转节点的前驱，用于重置already_added_predecessors
    predecessors_list->first = NULL;
    predecessors_list->last=NULL;
    struct RotationList* list_el = NULL;
    struct SuccessorsList* new_successor;
    while(w2 != w || go_on) {
        go_on = false;
        // 从尾到头构建旋转列表
        list_el = (struct RotationList*)malloc(sizeof (struct RotationList));
        list_el->man = old_reversed_M[w2];
        list_el->woman = w2;
        list_el->next = prev_list_el;
        prev_list_el = list_el;
        // 更新前驱和last_to_have_modified
        if (last_to_have_modified[old_reversed_M[w2]] != NULL && !already_added_predecessors[last_to_have_modified[old_reversed_M[w2]]->index]) {
            new_successor = (struct SuccessorsList*)malloc(sizeof (struct SuccessorsList));
            new_successor->value = rotation_node;
            // 每个前驱只添加一次当前旋转节点
            new_successor->next = last_to_have_modified[old_reversed_M[w2]]->successors;
            last_to_have_modified[old_reversed_M[w2]]->successors = new_successor;
            no_predecessors = false;
            rotation_node->missing_predecessors += 1;
            already_added_predecessors[last_to_have_modified[old_reversed_M[w2]]->index] = true;
            appendRotationsList(predecessors_list, last_to_have_modified[old_reversed_M[w2]]);
        }
        last_to_have_modified[old_reversed_M[w2]] = rotation_node;
        // 更新old_reversed_M (i = i+1)
        old_reversed_M[w2] = reversed_M[w2];
        // 更新M
        M[old_reversed_M[w2]] = w2;
        // 重置marking
        marking[w2] = -1;
        // 更新previous_woman
        w2 = previous_woman;
        previous_woman = marking[w2];
    }

    rotation_node->rotation = prev_list_el;

    if (no_predecessors) {
        appendRotationsList(free_rotations_list, rotation_node);
    }

    // 重置already_added_predecessors并释放空间
    struct RotationsListElement* rot_list_el = predecessors_list->first;
    struct RotationsListElement * temp;
    
    while (rot_list_el != NULL) {
        already_added_predecessors[rot_list_el->value->index] = false;
        temp = rot_list_el;
        rot_list_el = rot_list_el->next;
        free(temp);
    }

    free(predecessors_list);
    return;
}

触发问题的测试输入示例 #

2 0 1
0 1 2
1 0 2

2 0 1
0 1 2
1 2 0

内容的提问来源于stack exchange，提问作者StefanoTrv