我正在尝试解决“15 个难题”，但出现“OutOfMemoryError”

Question

有没有一种方法可以优化此代码以免耗尽内存？

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Random;
import java.util.Stack;

public class TilePuzzle {

    private final static byte ROWS = 4;
    private final static byte COLUMNS = 4;
    private static String SOLUTION = "123456789ABCDEF0";
    private static byte RADIX = 16;

    private char[][] board = new char[ROWS][COLUMNS];
    private byte x; // Row of the space ('0')
    private byte y; // Column of the space ('0') private String representation;
    private boolean change = false; // Has the board changed after the last call to toString?

    private TilePuzzle() {
        this(SOLUTION);
        int times = 1000;
        Random rnd = new Random();
        while(times-- > 0) {
            try {
                move((byte)rnd.nextInt(4));
            }
            catch(RuntimeException e) {
            }
        }
        this.representation = asString();
    }

    public TilePuzzle(String representation) {
        this.representation = representation;
        final byte SIZE = (byte)SOLUTION.length();
        if (representation.length() != SIZE) {
            throw new IllegalArgumentException("The board must have " + SIZE + "numbers.");
        }

        boolean[] used = new boolean[SIZE];
        byte idx = 0;
        for (byte i = 0; i < ROWS; ++i) {
            for (byte j = 0; j < COLUMNS; ++j) {
                char digit = representation.charAt(idx++);
                byte number = (byte)Character.digit(digit, RADIX);
                if (number < 0 || number >= SIZE) {
                    throw new IllegalArgumentException("The character " + digit + " is not valid.");
                } else if(used[number]) {
                    throw new IllegalArgumentException("The character " + digit + " is repeated.");
                }
                used[number] = true;
                board[i][j] = digit;
                if (digit == '0') {
                    x = i;
                    y = j;
                }
            }
        }
    }

    /**
     * Swap position of the space ('0') with the number that's up to it.
     */
    public void moveUp() {
        try {
            move((byte)(x - 1), y);
        } catch(IllegalArgumentException e) {
            throw new RuntimeException("Move prohibited " + e.getMessage());
        }
    }

    /**
     * Swap position of the space ('0') with the number that's down to it.
     */
    public void moveDown() {
        try {
            move((byte)(x + 1), y);
        } catch(IllegalArgumentException e) {
            throw new RuntimeException("Move prohibited " + e.getMessage());
        }
    }

    /**
     * Swap position of the space ('0') with the number that's left to it.
     */
    public void moveLeft() {
        try {
            move(x, (byte)(y - 1));
        } catch(IllegalArgumentException e) {
            throw new RuntimeException("Move prohibited " + e.getMessage());
        }
    }

    /**
     * Swap position of the space ('0') with the number that's right to it.
     */
    public void moveRight() {
        try {
            move(x, (byte)(y + 1));
        } catch(IllegalArgumentException e) {
            throw new RuntimeException("Move prohibited " + e.getMessage());
        }
    }

    private void move(byte movement) {
        switch(movement) {
        case 0: moveUp(); break;
        case 1: moveRight(); break;
        case 2: moveDown(); break;
        case 3: moveLeft(); break;
        }
    }

    private boolean areValidCoordinates(byte x, byte y) {
        return (x >= 0 && x < ROWS && y >= 0 && y < COLUMNS);
    }

    private void move(byte nx, byte ny) {
        if (!areValidCoordinates(nx, ny)) {
            throw new IllegalArgumentException("(" + nx + ", " + ny + ")");
        }
        board[x][y] = board[nx][ny];
        board[nx][ny] = '0';
        x = nx;
        y = ny;
        change = true;
    }

    public String printableString() {
        StringBuilder sb = new StringBuilder();
        for (byte i = 0; i < ROWS; ++i) {
            for (byte j = 0; j < COLUMNS; ++j) {
                sb.append(board[i][j] + " ");
            }
            sb.append("\r\n");
        }
        return sb.toString();
    }

    private String asString() {
        StringBuilder sb = new StringBuilder();
        for (byte i = 0; i < ROWS; ++i) {
            for (byte j = 0; j < COLUMNS; ++j) {
                sb.append(board[i][j]);
            }
        }
        return sb.toString();
    }

    public String toString() {
        if (change) {
            representation = asString();
        }
        return representation;
    }

    private static byte[] whereShouldItBe(char digit) {
        byte idx = (byte)SOLUTION.indexOf(digit);
        return new byte[] { (byte)(idx / ROWS), (byte)(idx % ROWS) };
    }

    private static byte manhattanDistance(byte x, byte y, byte x2, byte y2) {
        byte dx = (byte)Math.abs(x - x2);
        byte dy = (byte)Math.abs(y - y2);
        return (byte)(dx + dy);
    }

    private byte heuristic() {
        byte total = 0;
        for (byte i = 0; i < ROWS; ++i) {
            for (byte j = 0; j < COLUMNS; ++j) {
                char digit = board[i][j];
                byte[] coordenates = whereShouldItBe(digit);
                byte distance = manhattanDistance(i, j, coordenates[0], coordenates[1]);
                total += distance;
            }
        }
        return total;
    }

    private class Node implements Comparable<Node> {
        private String puzzle;
        private byte moves; // Number of moves from original configuration
        private byte value; // The value of the heuristic for this configuration.
        public Node(String puzzle, byte moves, byte value) {
            this.puzzle = puzzle;
            this.moves = moves;
            this.value = value;
        }
        @Override
        public int compareTo(Node o) {
            return (value + moves) - (o.value + o.moves);
        }
    }

    private void print(Map<String, String> antecessor) {
        Stack toPrint = new Stack();
        toPrint.add(SOLUTION);
        String before = antecessor.get(SOLUTION);
        while (!before.equals("")) {
            toPrint.add(before);
            before = antecessor.get(before);
        }
        while (!toPrint.isEmpty()) {
            System.out.println(new TilePuzzle(toPrint.pop()).printableString());
        }
    }

    private byte solve() {
        if(toString().equals(SOLUTION)) {
            return 0;
        }

        PriorityQueue<Node> toProcess = new PriorityQueue();
        Node initial = new Node(toString(), (byte)0, heuristic());
        toProcess.add(initial);

        Map<String, String> antecessor = new HashMap<String, String>();
        antecessor.put(toString(), "");

        while(!toProcess.isEmpty()) {
            Node actual = toProcess.poll();
            for (byte i = 0; i < 4; ++i) {
                TilePuzzle t = new TilePuzzle(actual.puzzle);
                try {
                    t.move(i);
                } catch(RuntimeException e) {
                    continue;
                }
                if (t.toString().equals(SOLUTION)) {
                    antecessor.put(SOLUTION, actual.puzzle);
                    print(antecessor);
                    return (byte)(actual.moves + 1);
                } else if (!antecessor.containsKey(t.toString())) {
                    byte v = t.heuristic();
                    Node neighbor = new Node(t.toString(), (byte)(actual.moves + 1), v);
                    toProcess.add(neighbor);
                    antecessor.put(t.toString(), actual.puzzle);
                }
            }
        }
        return -1;
    }

    public static void main(String... args) {
        TilePuzzle puzzle = new TilePuzzle();
        System.out.println(puzzle.solve());
    }
}

Answer 1

问题的

根本原因是您正在创建并存储在 toProcess 队列和 antecessor 映射中的大量 String 对象。你为什么要这么做？

看看你的算法。看看您是否真的需要在每个节点中存储超过 200 万个节点和 500 万个字符串。

调查

这很难发现，因为程序很复杂。实际上，我什至没有尝试理解所有代码。相反，我使用了 VisualVM – Java 分析器、采样器和 CPU/内存使用情况监视器。

我启动了它：

并查看了内存使用情况。我注意到的第一件事是（明显的）事实，您正在创建大量对象。

这是应用程序的屏幕截图：

如您所见，使用的内存量是巨大的。在短短 40 秒内，就消耗了 2 GB 空间并填满了整个堆。

死胡同

我最初认为问题与 Node 类有关，因为即使它实现了 Comparable，它也没有实现 equals >。所以我提供了方法：

public boolean equals( Object o ) {
    if( o instanceof Node ) {
        Node other = ( Node ) o;
        return this.value == other.value && this.moves == other.moves;
    }
    return false;
}

但这不是问题。

实际的问题原来是上面提到的问题。

解决方法

如前所述，真正的解决方案是重新考虑您的算法。与此同时，无论采取什么其他措施，都只会拖延问题的解决。

但解决方法可能很有用。一种是重用您生成的字符串。您非常频繁地使用 TilePuzzle.toString() 方法；这最终会经常创建重复的字符串。

由于您要生成字符串排列，因此您可以在几秒钟内创建许多 12345ABCD 字符串。如果它们是相同的字符串，则创建数百万个具有相同值的实例是没有意义的。

String.intern() 方法允许重用字符串。医生说：

返回字符串对象的规范表示。

字符串池最初为空，由 String 类私有维护。

当调用 intern 方法时，如果池中已经包含由 equals() 方法确定的等于此 String 对象的字符串，则返回池中的字符串。否则，将此 String 对象添加到池中，并返回对此 String 对象的引用。

对于常规应用程序，使用 String.intern() 可能不是一个好主意，因为它不允许 GC 回收实例。但在这种情况下，由于无论如何您都在映射和队列中保存引用，所以这是有道理的。

所以做出这个改变：

public String toString() {
    if (change) {
        representation = asString();
    }
    return representation.intern(); // <-- Use intern
}

几乎解决了内存问题。

这是更改后的屏幕截图：

现在，即使几分钟后，堆使用量也不会达到 100 MB。

额外备注

备注 #1

您使用异常来验证移动是否有效，这是可以的；但是当你捕获它们时，你只是忽略它们：

try {
    t.move(i);
} catch(RuntimeException e) {
    continue;
}

如果你无论如何都不使用它们，那么你可以通过不首先创建异常来节省大量计算。否则，您将创建数百万个未使用的异常。

进行此更改：

if (!areValidCoordinates(nx, ny)) {
    // REMOVE THIS LINE:
    // throw new IllegalArgumentException("(" + nx + ", " + ny + ")");

    // ADD THIS LINE:
    return;
}

并改用验证：

// REMOVE THESE LINES:
// try {
//     t.move(i);
// } catch(RuntimeException e) {
//     continue;
// }

// ADD THESE LINES:
if(t.isValidMovement(i)){
    t.move(i);
} else {
    continue;
}

备注 #2

您正在为每个新的 TilePuzzle 实例创建一个新的 Random 对象。如果整个程序只使用一个会更好。毕竟，您只使用单个线程。

备注 #3

该解决方法解决了堆内存问题，但创建了另一个涉及 PermGen 的问题。我只是增加了 PermGen 大小，如下所示：

java -Xmx1g -Xms1g -XX:MaxPermSize=1g TilePuzzle

备注 #4

输出有时是 49，有时是 50。矩阵打印如下：

1 2 3 4 
5 6 7 8 
9 A B C 
D E 0 F 

1 2 3 4 
5 6 7 8 
9 A B C 
D E F 0 

... 50 次