我如何完成这个双向匹配程序？

Question

我正在为 class 做作业，我必须读取邻接矩阵并在 Java 中输出二分匹配。我已经获得了两种填写方法来完成此操作，并且我已经设法让它适用于一个用例，但我在让它适用于其他两个用例时遇到了一些麻烦。我将在下面粘贴我的源代码。程序开头有 3 个测试用例，每个测试用例的预期输出显示在结尾处。

我需要将矩阵实现为二维字符数组。我遇到的问题似乎与它的回溯部分有关。第二个测试用例 returns 结果正确。如果有人可以帮助我理解我做错了什么，我将不胜感激。我寻找匹配的过程是：

从最后一行开始
遍历每一列
如果该列标记为 Y 且该列当前未被占用（标记为 'T'），则将该列标记为已占用 'T'。
为下一行递归调用方法

遍历矩阵，显示匹配

public class BiPartiteMatch
{
// **************** main  ****************
public static void main(String[] args)
{
    System.out.println("Case 1: No matching exists. \n");

    //                     a    b    c    d    e    No matching A, C, E
    //                    -----------------------   will only take a & d 
    char [][]M = { /*E*/ {'y', 'n', 'n', 'y', 'n'},
                   /*D*/ {'n', 'y', 'n', 'y', 'n'},
                   /*C*/ {'y', 'n', 'n', 'y', 'n'},
                   /*B*/ {'y', 'n', 'y', 'y', 'y'},
                   /*A*/ {'y', 'n', 'n', 'y', 'n'} };


    System.out.println("Case 2: Matching with no backtracking needed. \n"); 

    //                     a    b    c    d    e    Matching with no 
    //                    -----------------------   backtracking needed
    char [][]M = { /*E*/ {'y', 'n', 'n', 'y', 'y'},
                   /*D*/ {'n', 'y', 'n', 'y', 'n'},
                   /*C*/ {'n', 'y', 'y', 'n', 'n'},
                   /*B*/ {'y', 'n', 'y', 'n', 'n'},
                   /*A*/ {'n', 'y', 'n', 'n', 'y'} };


    System.out.println("Case 3: Matching with backtracking. \n");

    //                     a    b    c    d    e    Matching with 
    //                    -----------------------   backtracking
    char [][]M = { /*E*/ {'n', 'y', 'n', 'n', 'y'},
                   /*D*/ {'y', 'n', 'y', 'n', 'n'},
                   /*C*/ {'n', 'y', 'y', 'n', 'n'},
                   /*B*/ {'n', 'y', 'n', 'y', 'n'},
                   /*A*/ {'y', 'n', 'n', 'y', 'y'} };


 if (findMatch(M, M.length-1)) // Find matches starting with the last row
     displayMatches(M); 
 else
     System.out.println("There is no matching.");         

}// end main



// **************** recursive findMatch  ****************
public static boolean findMatch(char [][]M, int myRow)
{           
        if(myRow < 0)
            return false;            

        for(int c = 0; c < M.length; c++)
        {
            if(M[myRow][c] == 'y' && !isTaken(M, myRow, c))
            {
                M[myRow][c] = 't';
                break;
            }
        }

        findMatch(M, myRow-1);

        return true;

}// end findMatch      


// **************** isTaken  ******************
// *******is this column already taken? ********
public static boolean isTaken(char [][]M, int row_Im_In, int col_Im_In)
{
        for(int r = row_Im_In+1; r < M.length; r++)
        {
            if(M[r][col_Im_In] == 't')
                return true;
        }

        return false;

}// end isTaken


// **************** displayMatches  ****************
public static void displayMatches(char [][]M)
{
    final char []MatchFrom = {'E', 'D', 'C', 'B', 'A'};
    final char []MatchTo   = {'a', 'b', 'c', 'd', 'e'};

            for(int r = M.length-1; r > -1; r--)
            {
                for(int c = 0; c < M.length; c++)
                {
                    if(M[r][c] == 't')
                    {
                        System.out.println(MatchFrom[r] + " matches to " + MatchTo[c]);
                    }
                }
            }


}// end displayMatches

}// end class declaration

预期结果：

Case 1: No mathing exists. 

There is no matching.


Case 2: Matching with no backtracking needed. 

A matches to b
B matches to a
C matches to c
D matches to d
E matches to e


Case 3: Matching with backtracking. 

A matches to a
B matches to d
C matches to b
D matches to c
E matches to e

Answer 1

您需要将 findMatch 替换为如下内容：

public static boolean findMatch(char [][]M, int myRow)
{           
        if(myRow < 0)
            return true;            

        for(int c = 0; c < M.length; c++)
        {
            if(M[myRow][c] == 'y' && !isTaken(M, myRow, c))
            {
                M[myRow][c] = 't';
                if (findMatch(M, myRow-1))
                    return true;
                M[myRow][c] = 'y';
            }
        }
        return false;

}

目前，您的代码只会尝试为每个元素找到第一个可能的匹配项。

要进行正确的回溯，您需要从循环内部调用递归函数，然后如果找不到完全匹配，您需要测试下一个位置。

我如何完成这个双向匹配程序？

How do I complete this BiPartite Matching program?

java

algorithm

recursion

bipartite

adjacency-matrix