2

我正在开发名为Lights Out的游戏。所以为了解决这个问题，我必须在模块 2 中计算AX = B的答案。因此，我选择jscience库。在这个游戏中，A 的大小是 25x25 矩阵，X 和 B 都是 25x1 矩阵。我写了如下代码：

AllLightOut.java班级 ：

public class AllLightOut {
    public static final int SIZE = 5;

    public static double[] Action(int i, int j) {
        double[] change = new double[SIZE * SIZE];
        int count = 0;

        for (double[] d : Switch(new double[SIZE][SIZE], i, j))
            for (double e : d)
                change[count++] = e;

        return change;
    }

    public static double[][] MatrixA() {
        double[][] mat = new double[SIZE * SIZE][SIZE * SIZE];

        for (int i = 0; i < SIZE; i++)
            for (int j = 0; j < SIZE; j++)
                mat[i * SIZE + j] = Action(i, j);

        return mat;
    }

    public static SparseVector<ModuloInteger> ArrayToDenseVectorModule2(
            double[] array) {
        List<ModuloInteger> list = new ArrayList<ModuloInteger>();

        for (int i = 0; i < array.length; i++) {
            if (array[i] == 0)
                list.add(ModuloInteger.ZERO);
            else
                list.add(ModuloInteger.ONE);
        }

        return SparseVector.valueOf(DenseVector.valueOf(list),
                ModuloInteger.ZERO);
    }

    public static SparseMatrix<ModuloInteger> MatrixAModule2() {
        double[][] mat = MatrixA();
        List<DenseVector<ModuloInteger>> list = new ArrayList<DenseVector<ModuloInteger>>();

        for (int i = 0; i < mat.length; i++) {
            List<ModuloInteger> l = new ArrayList<ModuloInteger>();
            for (int j = 0; j < mat[i].length; j++) {
                if (mat[i][j] == 0)
                    l.add(ModuloInteger.ZERO);
                else
                    l.add(ModuloInteger.ONE);
            }

            list.add(DenseVector.valueOf(l));
        }

        return SparseMatrix.valueOf(DenseMatrix.valueOf(list),
                ModuloInteger.ZERO);
    }

    public static double[][] Switch(double[][] action, int i, int j) {
        action[i][j] = action[i][j] == 1 ? 0 : 1;

        if (i > 0)
            action[i - 1][j] = action[i - 1][j] == 1 ? 0 : 1;

        if (i < action.length - 1)
            action[i + 1][j] = action[i + 1][j] == 1 ? 0 : 1;

        if (j > 0)
            action[i][j - 1] = action[i][j - 1] == 1 ? 0 : 1;

        if (j < action.length - 1)
            action[i][j + 1] = action[i][j + 1] == 1 ? 0 : 1;

        return action;
    }
}

主要课程如下：

public class Main {
    public static void main(String[] args) {
        double[] bVec = new double[] { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
                1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 };

        SparseMatrix<ModuloInteger> matA = AllLightOut.MatrixAModule2();
        SparseVector<ModuloInteger> matB = AllLightOut
                .ArrayToDenseVectorModule2(bVec);

        ModuloInteger.setModulus(LargeInteger.valueOf(2));
    Vector<ModuloInteger> matX = matA.solve(matB);

        System.out.println(matX);
    }
}

我运行了这个程序大约 30 分钟，但没有结果。我的代码是否包含致命错误或错误？为什么需要太长时间？

感谢您的关注 ：）

编辑 这一行发生的减速Matrix<ModuloInteger> matX = matA.inverse();。请注意，JScience 基准测试结果，这个库的速度非常快，但我不知道为什么我的程序运行速度太慢！

EDIT2 请注意，当我尝试时SIZE = 3，我得到了真正的答案。例如： MatA ：

{{1, 1, 0, 1, 0, 0, 0, 0, 0},
{1, 1, 1, 0, 1, 0, 0, 0, 0},
{0, 1, 1, 0, 0, 1, 0, 0, 0},
{1, 0, 0, 1, 1, 0, 1, 0, 0},
{0, 1, 0, 1, 1, 1, 0, 1, 0},
{0, 0, 1, 0, 1, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 1, 1, 0},
{0, 0, 0, 0, 1, 0, 1, 1, 1},
{0, 0, 0, 0, 0, 1, 0, 1, 1}}

垫子：

{1, 1, 1, 1, 1, 1, 1, 0, 0}

垫：

{0, 0, 1, 1, 0, 0, 0, 0, 0}

但是当我尝试时SIZE = 5，速度变慢了。

4

2 回答 2

4

这条线发生的放缓Matrix<ModuloInteger> matX = matA.inverse();

那将是因为系数矩阵对于（或 4、9、11、14、16，...？）matA是不可逆的。SIZE == 5

我有点惊讶图书馆没有检测到这一点并抛出异常。如果库试图反转 中的矩阵solve()，那将产生相同的后果。

某些尺寸的系数矩阵的奇异性的结果是，并非这些尺寸的所有谜题都是可解的，而其他谜题有多个解。

由于我们正在计算模 2，我们可以使用 bits 或booleans 来模拟我们的状态/切换，XOR用于加法和&乘法。我已经使用高斯消元法制作了一个简单的求解器，也许它可以帮助你（我没有花太多时间考虑设计，所以它并不漂亮）：

public class Lights{
    private static final int SIZE = 5;

    private static boolean[] toggle(int i, int j) {
        boolean[] action = new boolean[SIZE*SIZE];
        int idx = i*SIZE+j;
        action[idx] = true;
        if (j > 0)      action[idx-1] = true;
        if (j < SIZE-1) action[idx+1] = true;
        if (i > 0)      action[idx-SIZE] = true;
        if (i < SIZE-1) action[idx+SIZE] = true;
        return action;
    }
    private static boolean[][] matrixA() {
        boolean[][] mat = new boolean[SIZE*SIZE][];
        for(int i = 0; i < SIZE; ++i) {
            for(int j = 0; j < SIZE; ++j) {
                mat[i*SIZE+j] = toggle(i,j);
            }
        }
        return mat;
    }
    private static void rotateR(boolean[] a, int r) {
        r %= a.length;
        if (r < 0) r += a.length;
        if (r == 0) return;
        boolean[] tmp = new boolean[r];
        for(int i = 0; i < r; ++i) {
            tmp[i] = a[i];
        }
        for(int i = 0; i < a.length - r; ++i) {
            a[i] = a[i+r];
        }
        for(int i = 0; i < r; ++i) {
            a[i + a.length - r] = tmp[i];
        }
    }
    private static void rotateR(boolean[][] a, int r) {
        r %= a.length;
        if (r < 0) r += a.length;
        if (r == 0) return;
        boolean[][] tmp = new boolean[r][];
        for(int i = 0; i < r; ++i) {
            tmp[i] = a[i];
        }
        for(int i = 0; i < a.length - r; ++i) {
            a[i] = a[i+r];
        }
        for(int i = 0; i < r; ++i) {
            a[i + a.length - r] = tmp[i];
        }
    }
    private static int count(boolean[] a) {
        int c = 0;
        for(int i = 0; i < a.length; ++i) {
            if (a[i]) ++c;
        }
        return c;
    }
    private static void swapBits(boolean[] a, int i, int j) {
        boolean tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void addBit(boolean[] a, int i, int j) {
        a[j] ^= a[i];
    }
    private static void swapRows(boolean[][] a, int i, int j) {
        boolean[] tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    private static void xorb(boolean[] a, boolean[] b) {
        for(int i = 0; i < a.length; ++i) {
            a[i] ^= b[i];
        }
    }
    private static boolean[] boolBits(int bits, long param) {
        boolean[] bitArr = new boolean[bits];
        for(int i = 0; i < bits; ++i) {
            if (((param >> i) & 1L) != 0) {
                bitArr[i] = true;
            }
        }
        return bitArr;
    }
    private static boolean[] solve(boolean[][] m, boolean[] b) {
        // Move first SIZE rows to bottom, so that on the diagonal
        // above the lowest SIZE rows, there are unit matrices
        rotateR(m, SIZE);
        // modify right hand side accordingly
        rotateR(b,SIZE);
        // clean first SIZE*(SIZE-1) columns
        for(int i = 0; i < SIZE*(SIZE-1); ++i) {
            for(int k = 0; k < SIZE*SIZE; ++k) {
                if (k == i) continue;
                if (m[k][i]) {
                    xorb(m[k], m[i]);
                    b[k] ^= b[i];
                }
            }
        }
        // Now we have a block matrix
        /*
         * E 0 0 ... 0 X
         * 0 E 0 ... 0 X
         * 0 0 E ... 0 X
         * ...
         * 0 0 ... E 0 X
         * 0 0 ... 0 E X
         * 0 0 ... 0 0 Y
         *
         */
        // Bring Y to row-echelon form
        int i = SIZE*(SIZE-1), j, k, mi = i;
        while(mi < SIZE*SIZE){
            // Try to find a row with mi-th bit set
            for(j = i; j < SIZE*SIZE; ++j) {
                if (m[j][mi]) break;
            }
            if (j < SIZE*SIZE) {
                // Found one
                if (j > i) {
                    swapRows(m,i,j);
                    swapBits(b,i,j);
                }
                for(k = 0; k < SIZE*SIZE; ++k) {
                    if (k == i) continue;
                    if (m[k][mi]) {
                        xorb(m[k], m[i]);
                        b[k] ^= b[i];
                    }
                }
                // cleaned up column, good row, next
                ++i;
            }
            // Look at next column
            ++mi;
        }
        printMat(m,b);
        boolean[] best = b;
        if (i < SIZE*SIZE) {
            // We have zero-rows in the matrix,
            // check whether the puzzle is solvable at all,
            // i.e. all corresponding bits in the rhs are 0
            for(j = i; j < SIZE*SIZE; ++j) {
                if (b[j]) {
                    System.out.println("Puzzle not solvable, some lights must remain lit.");
                    break;
//                     throw new IllegalArgumentException("Puzzle is not solvable!");
                }
            }
            // Pretending it were solvable if not
            if (j < SIZE*SIZE) {
                System.out.println("Pretending the puzzle were solvable...");
                for(; j < SIZE*SIZE; ++j) {
                    b[j] = false;
                }
            }
            // Okay, puzzle is solvable, but there are several solutions
            // Let's try to find the one with the least toggles.

            // We have the canonical solution with last bits all zero
            int toggles = count(b);
            System.out.println(toggles + " toggles in canonical solution");
            int freeBits = SIZE*SIZE - i;
            long max = 1L << freeBits;
            System.out.println(freeBits + " free bits");
            // Check all combinations of free bits whether they produce
            // something better
            for(long param = 1; param < max; ++param) {
                boolean[] base = boolBits(freeBits,param);
                boolean[] c = new boolean[SIZE*SIZE];
                for(k = 0; k < freeBits; ++k) {
                    c[i+k] = base[k];
                }
                for(k = 0; k < i; ++k) {
                    for(j = 0; j < freeBits; ++j) {
                        c[k] ^= base[j] && m[k][j+i];
                    }
                }
                xorb(c,b);
                int t = count(c);
                if (t < toggles) {
                    System.out.printf("Found new best for param %x, %d toggles\n",param,t);
                    printMat(m,c,b);
                    toggles = t;
                    best = c;
                } else {
                    System.out.printf("%d toggles for parameter %x\n", t, param);
                }
            }
        }
        return best;
    }
    private static boolean[] parseLights(int[] lights) {
        int lim = lights.length;
        if (SIZE*SIZE < lim) lim = SIZE*SIZE;
        boolean[] b = new boolean[SIZE*SIZE];
        for(int i = 0; i < lim; ++i) {
            b[i] = (lights[i] != 0);
        }
        return b;
    }
    private static void printToggles(boolean[] s) {
        for(int i = 0; i < s.length; ++i) {
            if (s[i]) {
                System.out.print("(" + (i/SIZE + 1) + ", " + (i%SIZE + 1) + "); ");
            }
        }
        System.out.println();
    }
    private static void printMat(boolean[][] a, boolean[] rhs) {
        for(int i = 0; i < SIZE*SIZE; ++i) {
            for(int j = 0; j < SIZE*SIZE; ++j) {
                System.out.print((a[i][j] ? "1 " : "0 "));
            }
            System.out.println("| " + (rhs[i] ? "1" : "0"));
        }
    }
    private static void printMat(boolean[][] a, boolean[] sol, boolean[] rhs) {
        for(int i = 0; i < SIZE*SIZE; ++i) {
            for(int j = 0; j < SIZE*SIZE; ++j) {
                System.out.print((a[i][j] ? "1 " : "0 "));
            }
            System.out.println("| " + (sol[i] ? "1" : "0") + " | " + (rhs[i] ? "1" : "0"));
        }
    }
    private static void printGrid(boolean[] g) {
        for(int i = 0; i < SIZE; ++i) {
            for(int j = 0; j < SIZE; ++j) {
                System.out.print(g[i*SIZE+j] ? "1" : "0");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int[] initialLights = new int[] { 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0,
                1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0 };
        boolean[] b = parseLights(initialLights);
        boolean[] b2 = b.clone();
        boolean[][] coefficients = matrixA();
        boolean[] toggles = solve(coefficients, b);
        printGrid(b2);
        System.out.println("--------");
        boolean[][] check = matrixA();
        boolean[] verify = new boolean[SIZE*SIZE];
        for(int i = 0; i < SIZE*SIZE; ++i) {
            if (toggles[i]) {
                xorb(verify, check[i]);
            }
        }
        printGrid(verify);
        xorb(b2,verify);
        if (count(b2) > 0) {
            System.out.println("Aww, shuck, screwed up!");
            printGrid(b2);
        }
        printToggles(toggles);
    }
}
于 2012-07-21T23:25:12.737 回答
2

如果可以避免，您几乎永远不想计算矩阵的实际逆。这样的操作是有问题的并且非常耗时。查看 JScience 的文档，您是否考虑过使用解决方法？类似于 matX = matA.solve(matB) 的东西应该会给你你正在寻找的东西，我怀疑他们是否使用逆来计算它，尽管我还没有深入研究 JScience，所以这不是不可能的。

于 2012-07-18T23:41:36.923 回答