有没有一种方法可以优化此代码以免耗尽内存？
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());
}
}
最佳答案
问题
根本原因是您正在创建并存储在 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()方法允许重复使用字符串。医生说:
Returns a canonical representation for the string object.
A pool of strings, initially empty, is maintained privately by the class String.
When the intern method is invoked, if the pool already contains a string equal to this String object as determined by the equals() method, then the string from the pool is returned. Otherwise, this String object is added to the pool and a reference to this String object is returned.
对于常规应用程序，使用 String.intern() 可能不是一个好主意，因为它不允许 GC 回收实例。但在这种情况下，由于您无论如何都在 Map 和 Queue 中保存引用，所以这是有道理的。
因此进行此更改:
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 次
关于java - 我试图解决 '15 puzzle' ，但我得到 'OutOfMemoryError'，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/3094925/