0

我正在尝试从该期刊制作 java 代码：

期刊贪婪 LCS

这段代码是关于 afroza begum 计算最长公共子序列的一种贪婪方法。

这是我的[编辑]代码：

public class LCS_Greedy {

public static void main(String[] args) {
//        String X_awal = "ABCBDABE";
//        String Y = "BDCABA";

//        String X_awal = "XMJYAUZ";
//        String Y = "MZJAWXU";
    
//        String X_awal ="AGGTAB";
//        String Y="GXTXAYB";
    
//        String X_awal = "ABCDGH";
//        String Y = "AEDFHR";
    
//        String X_awal = "AHBCDG";
//        String Y = "AEDFHR";       
    
    //greedy not always optimum
    String X_awal = "bcaaaade";
    String Y = "deaaaabc";
    String X = match(X_awal, Y);
    int[] Penanda_Y = new int[Y.length()];
    int y_length = Y.length();
    for (int k = 0; k < y_length; k++) {
        Penanda_Y[k] = 0;
    }
    int m = X.length();
    int n = Y.length();
    String L = "";
    String LSym = "";
    int R = 0;
    int i = 1;
    int[] P = new int[100];
    P[i] = posisi(X, Y, i, Penanda_Y, R);
    i = 1;
    while (i <= m) {
        if (i != m) {
            P[i + 1] = posisi(X, Y, (i + 1), Penanda_Y, R);
        }
        if (P[i + 1] == 0) {
            if (P[i] > R) {
                L = L + " " + Integer.toString(P[i]);
                LSym = LSym + " " + X.charAt(i - 1);
            }
            break;
        }

        if (P[i + 1] < R || P[i] < R) {
            R = 0;
        }
        if (P[i] > P[i + 1]) {
            if (R == 0 && i > 1) {
                L = L + " " + Integer.toString(P[i]);
                LSym = LSym + " " + X.charAt(i - 1);
                Penanda_Y[P[i] - 1] = 1;
                R = P[i];
                i = i + 1;
                if (R == Y.length() || i > X.length()) {
                    break;
                }
                P[i] = posisi(X, Y, i, Penanda_Y, R);
            } else {
                L = L + " " + Integer.toString(P[i + 1]);
                LSym = LSym + " " + X.charAt(i + 1 - 1);
                Penanda_Y[P[i + 1] - 1] = 1;
                R = P[i + 1];
                i = (i + 1) + 1;
                if (R == Y.length() || i > X.length()) {
                    break;
                }
                P[i] = posisi(X, Y, i, Penanda_Y, R);
            }

        } else {

            if (R == 0 && i > 1) {
                L = L + " " + Integer.toString(P[i + 1]);
                LSym = LSym + " " + X.charAt(i + 1 - 1);
                Penanda_Y[P[i + 1] - 1] = 1;
                R = P[i + 1];
                i = (i + 1) + 1;
                if (R == Y.length() || i > X.length()) {
                    break;
                }
                P[i] = posisi(X, Y, i, Penanda_Y, R);
            } else {
                L = L + " " + Integer.toString(P[i]);
                LSym = LSym + " " + X.charAt(i - 1);
                Penanda_Y[P[i] - 1] = 1;
                R = P[i];
                i = i + 1;
                if (R == Y.length() || i > X.length()) {
                    break;
                }
                P[i] = posisi(X, Y, i, Penanda_Y, R);
            }
        }
    }
    System.out.println("X = " + X_awal);
    System.out.println("X = " + Y);
    System.out.println("L = " + L);
    System.out.println("LSym = " + LSym);
    System.out.println("Length = " + LSym.length() / 2);
}

public static String match(String X, String Y) {
    String hasil = "";
    for (int i = 0; i < X.length(); i++) {
        for (int j = 0; j < Y.length(); j++) {
            if (X.charAt(i) == Y.charAt(j)) {
                hasil = hasil + X.charAt(i);
                break;
            }
        }
    }
    return hasil;
}

public static int posisi(String X, String Y, int i, int[] Penanda_Y, int R) {
    int n = Y.length();
    int k;
    int kr = 0;
    i = i - 1;
    for (k = 0; k < n; k++) {
        if ((X.charAt(i) == Y.charAt(k)) && Penanda_Y[k] == 0) {
            kr = k + 1;
            break;
        }
    }
    for (k = R; k < n; k++) {
        if ((X.charAt(i) == Y.charAt(k)) && Penanda_Y[k] == 0) {
            kr = k + 1;
            break;
        }
    }
    return kr;
}
}

但是当我运行该程序时，在某些情况下它有真实的输出，但在另一种情况下它是错误的。该代码有什么问题？谁能给我解释一下？谢谢

编辑：

我的代码现在可以完美运行了，但与那本日记中的伪代码似乎相去甚远。有人可以解释一下吗？为什么我不能完全从期刊中制作代码？当我使用该期刊中给出的伪代码进行制作时，它总是出错。谢谢。

4

1 回答 1

0

该算法不会导致 LCS。贪婪的猜测是错误的。它假设早期的比赛将保证形成 LCS。即使，伪代码取 X 中前两个的较早匹配，这可能会跳过 Y 开头的许多公共子字符串。另一个简单的测试是将 X 中的最后一个 'E' 更改为 'A'，算法会赢'肯定不能找到最后一个匹配的“A”。事实是早期的比赛可能会锁定位置以禁止更长的比赛。换句话说，我们可能需要跳过一些早期的匹配，以便我们可以找到更长的匹配。动态规划方法在数学上被证明是正确的，但是，该算法没有。

于 2015-05-06T14:22:17.597 回答