java 堆空间耗尽 - 15 个难题
大家好, 我尝试了发布的八个难题的解决方案 这里 由乔尔·尼利(joel Neely)研究并修改它,以便可以用于解决更高的网格[将网格的字符串表示形式更改为二维整数表示形式并修改 相应的逻辑]。然而,修改后的代码可以解决 3x3 网格,但很快就会耗尽 4x4 网格的堆空间。我想这是由所使用的算法引起的限制,我认为这是一些 分支定界的变体,而不是java的变体。如果我的假设是正确的,有人可以建议任何其他好的算法来解决这个问题吗?如果没有,请提示可以做什么来制作这个程序 适用于高阶网格。
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class EightPuzzle {
//Queue<Integer[][]> agenda = new LinkedList<Integer[][]>(); // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
//Map<Integer[][],Integer> stateDepth = new HashMap<Integer[][], Integer>(); // HashMap is used to ignore repeated nodes
//Map<Integer[][],Integer[][]> stateHistory = new HashMap<Integer[][],Integer[][]>(); // relates each position to its predecessor
Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor
Map<String,Integer> stateDepth = new HashMap<String,Integer>();
Queue<Integer[][]> agenda=new LinkedList<Integer[][]>();
final int GRIDSIZE=4;
int row=0,col=0;
public static void main(String args[]){
// Integer[][] str="087465132"; // Input the Board State as a Integer[][] with 0 as the Blank Space
Integer init[][]={{1,3,12,4},{2,9,10,7},{0,14,8,15},{5,6,13,11}};
//Integer init[][]={{0,8,7},{4,6,5},{1,3,2}};
EightPuzzle e = new EightPuzzle(); // New Instance of the EightPuzzle
e.add(init,null); // Add the Initial State
while(!e.agenda.isEmpty()){
Integer[][] currentState = e.agenda.remove();
e.up(currentState); // Move the blank space up and add new state to queue
e.down(currentState); // Move the blank space down
e.left(currentState); // Move left
e.right(currentState); // Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new Integer[][] to the Map and Queue
void add(Integer newState[][], Integer oldState[][]){
if(!stateDepth.containsKey(convertToString(newState))){
int newValue = oldState == null ? 0 : stateDepth.get(convertToString(oldState)) + 1;
stateDepth.put(convertToString(newState), newValue);
agenda.add(newState);
stateHistory.put(convertToString(newState), convertToString(oldState));
}
}
/* Each of the Methods below Takes the Current State of Board as Integer[][]. Then the operation to move the blank space is done if possible.
After that the new Integer[][] is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(row!=0){
nextState[row-1][col]=currentState[row][col];
nextState[row][col]=currentState[row-1][col];
checkCompletion(currentState, nextState);
}
}
/**
* @param currentState
*/
/**
* @param currentState
*/
void down(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(row!=GRIDSIZE-1){
nextState[row+1][col]=currentState[row][col];
nextState[row][col]=currentState[row+1][col];
checkCompletion(currentState, nextState);
}
}
void left(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(col!=0){
nextState[row][col-1]=currentState[row][col];
nextState[row][col]=currentState[row][col-1];
checkCompletion(currentState, nextState);
}
}
void right(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(col!=GRIDSIZE-1){
nextState[row][col+1]=currentState[row][col];
nextState[row][col]=currentState[row][col+1];
checkCompletion(currentState, nextState);
}
}
private void checkCompletion(Integer[][] oldState, Integer[][] newState) {
add(newState, oldState);
Integer[][] completeState={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};
//Integer[][] completeState={{1,2,3},{4,5,6},{7,8,0}};
boolean equality=true;
outer:for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
if(newState[i][j]!=completeState[i][j]){
equality=false;
break outer;
}
}
}
if(equality){
System.out.println("Solution Exists at Level "+stateDepth.get(convertToString(newState))+" of the tree");
String traceState = convertToString(newState);
while (traceState != null) {
System.out.println(traceState + " at " + stateDepth.get(traceState));
traceState = stateHistory.get(traceState);
}
System.exit(0);
}
}
String convertToString(Integer[][] a){
String str="";
if(a!=null){
for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
str+=a[i][j];
}
}
}
else{
str=null;
}
return str;
}
void getIndicesOfZero(Integer[][] currentState,Integer[][] nextState){
for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
nextState[i][j]=currentState[i][j];
}
}
outer:for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
if(currentState[i][j]==0){
row=i;
col=j;
break outer;
}
}
}
}
}
提前致谢, 保罗.
G'day all,
I tried the solution for eight puzzle problem posted here
by joel Neely and played around with it and modified it so that can be used to solve for higher grids[Changed the String representation of the grid to two dimensional integer representation and modified
the logic accordingly]. However the modified code can solve the 3x3 grids but quickly run out of heap space for 4x4 grid. I guess this is the restriction caused by the algorithm used which i think is some
variation of branch and bound and not that of java. If my assumptions are right, can someone suggest any other good algorithms for solving this problem?. If not, please hint what can be done to make this program
work for higher order grids.
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class EightPuzzle {
//Queue<Integer[][]> agenda = new LinkedList<Integer[][]>(); // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
//Map<Integer[][],Integer> stateDepth = new HashMap<Integer[][], Integer>(); // HashMap is used to ignore repeated nodes
//Map<Integer[][],Integer[][]> stateHistory = new HashMap<Integer[][],Integer[][]>(); // relates each position to its predecessor
Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor
Map<String,Integer> stateDepth = new HashMap<String,Integer>();
Queue<Integer[][]> agenda=new LinkedList<Integer[][]>();
final int GRIDSIZE=4;
int row=0,col=0;
public static void main(String args[]){
// Integer[][] str="087465132"; // Input the Board State as a Integer[][] with 0 as the Blank Space
Integer init[][]={{1,3,12,4},{2,9,10,7},{0,14,8,15},{5,6,13,11}};
//Integer init[][]={{0,8,7},{4,6,5},{1,3,2}};
EightPuzzle e = new EightPuzzle(); // New Instance of the EightPuzzle
e.add(init,null); // Add the Initial State
while(!e.agenda.isEmpty()){
Integer[][] currentState = e.agenda.remove();
e.up(currentState); // Move the blank space up and add new state to queue
e.down(currentState); // Move the blank space down
e.left(currentState); // Move left
e.right(currentState); // Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new Integer[][] to the Map and Queue
void add(Integer newState[][], Integer oldState[][]){
if(!stateDepth.containsKey(convertToString(newState))){
int newValue = oldState == null ? 0 : stateDepth.get(convertToString(oldState)) + 1;
stateDepth.put(convertToString(newState), newValue);
agenda.add(newState);
stateHistory.put(convertToString(newState), convertToString(oldState));
}
}
/* Each of the Methods below Takes the Current State of Board as Integer[][]. Then the operation to move the blank space is done if possible.
After that the new Integer[][] is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(row!=0){
nextState[row-1][col]=currentState[row][col];
nextState[row][col]=currentState[row-1][col];
checkCompletion(currentState, nextState);
}
}
/**
* @param currentState
*/
/**
* @param currentState
*/
void down(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(row!=GRIDSIZE-1){
nextState[row+1][col]=currentState[row][col];
nextState[row][col]=currentState[row+1][col];
checkCompletion(currentState, nextState);
}
}
void left(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(col!=0){
nextState[row][col-1]=currentState[row][col];
nextState[row][col]=currentState[row][col-1];
checkCompletion(currentState, nextState);
}
}
void right(Integer[][] currentState){
Integer[][] nextState=new Integer[GRIDSIZE][GRIDSIZE];
getIndicesOfZero(currentState, nextState);
if(col!=GRIDSIZE-1){
nextState[row][col+1]=currentState[row][col];
nextState[row][col]=currentState[row][col+1];
checkCompletion(currentState, nextState);
}
}
private void checkCompletion(Integer[][] oldState, Integer[][] newState) {
add(newState, oldState);
Integer[][] completeState={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,0}};
//Integer[][] completeState={{1,2,3},{4,5,6},{7,8,0}};
boolean equality=true;
outer:for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
if(newState[i][j]!=completeState[i][j]){
equality=false;
break outer;
}
}
}
if(equality){
System.out.println("Solution Exists at Level "+stateDepth.get(convertToString(newState))+" of the tree");
String traceState = convertToString(newState);
while (traceState != null) {
System.out.println(traceState + " at " + stateDepth.get(traceState));
traceState = stateHistory.get(traceState);
}
System.exit(0);
}
}
String convertToString(Integer[][] a){
String str="";
if(a!=null){
for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
str+=a[i][j];
}
}
}
else{
str=null;
}
return str;
}
void getIndicesOfZero(Integer[][] currentState,Integer[][] nextState){
for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
nextState[i][j]=currentState[i][j];
}
}
outer:for(int i=0;i<GRIDSIZE;i++){
for(int j=0;j<GRIDSIZE;j++){
if(currentState[i][j]==0){
row=i;
col=j;
break outer;
}
}
}
}
}
Thanks in advance,
paul.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(1)
您的算法缺乏启发式。换句话说,它在没有指导的情况下探索搜索空间。对于 15 个谜题,该空间相当大,接近 3**(解决方案的深度)。
如果您按照每个图块与其目的地的曼哈顿距离之和来对队列进行排序,则可能足以使其可解。在每一步中,以“错误”最少的方式扩展议程上的项目。
另外,您确定您选择的开始状态是可解的吗?如果你随机排列瓷砖,你只有 50-50 的机会。
最后,您可以从
Integer
切换到byte
以节省内存。多少取决于 java 实现,但由于 Integer 是一个类,而 byte 是一个基本类型,因此它可能很重要。已更新
Your algorithm lacks a heuristic. In other words, it's exploring the search space with no guidance. For the 15-puzzle, that space is quite large, close to 3**(depth of the solution).
If you order your queue by the sum of the Manhattan distance of each tile from its destination, it might be sufficient to make it solvable. At each step, expand the item on the agenda with the least "error".
Also, are you sure the start state you've chosen is solvable? If you randomly order the tiles, you only have a 50-50 chance.
Finally, you might switch from
Integer
tobyte
to save memory. How much depends on the java implementation, but since Integer is a class and byte a primitive type, it could be significant.Updated