需要一个实用的解决方案来为15个拼图创建模式数据库(5-5-5) [英] Need a practical solution for creating pattern database(5-5-5) for 15-Puzzle
问题描述
对于静态模式数据库(5-5-5)，请参见此(第290和283页)，或者下面有一个解释.对于什么是15拼图?
我正在创建一个静态模式数据库(5-5-5).此代码将条目填充到第一个表中.我正在通过递归函数insertInDB()来执行此操作.递归函数的第一个输入是这个(实际上输入谜题将其包含在1-D数组中.为了更好地理解，我在下面将其表示为2-D)
For static pattern database(5-5-5), see this(page 290 and 283) OR there is an explanation below. For What is 15-puzzle?
I am creating a static patter database(5-5-5). This code to to fill entries into the first table. I am doing it via the recursive function insertInDB(). The first input to the recursive function is this (actually the input puzzle contains it in 1-D array. For better understanding I have represented it as 2-D below)
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
这是我的代码:
This is my code :
class DBClass
{
public Connection connection;
public ResultSet rs;
public PreparedStatement ps1;
public PreparedStatement ps2;
public int k;
String read_statement,insert_statement;
public DBClass()
{
try {
Class.forName("com.mysql.jdbc.Driver");
} catch (ClassNotFoundException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
try {
connection = DriverManager
.getConnection("jdbc:mysql://localhost/feedback?"
+ "user=ashwin&password=ashwin&autoReconnect=true&useUnicode=true&characterEncoding=utf8&validationQuery=Select 1");
insert_statement="insert into staticpdb1(hash,permutation,cost) values(?,?,?)";
read_statement="select SQL_NO_CACHE * from staticpdb1 where hash=? and permutation= ? LIMIT 1";
ps1=connection.prepareStatement(read_statement, ResultSet.TYPE_SCROLL_SENSITIVE,
ResultSet.CONCUR_UPDATABLE);
ps2=connection.prepareStatement(insert_statement);
k=0;
} catch (SQLException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
public int updateIfNecessary(FifteenPuzzle sub)
{
String str=sub.toDBString();
try
{
ps1.setInt(1, sub.hashcode());
ps1.setString(2,str);
rs=ps1.executeQuery();
if(rs.next())
{
//if a row exists, check if the cost is greater than sub's
int cost=rs.getInt(3);
if(sub.g_n<cost) //if the cost of sub is less than db row's cost
{
//replace the cost
rs.updateInt(3, sub.g_n);
rs.updateRow();
return 1; //only examine - do not insert
}
else
return 0; //dont examine - return
}
else
return 2; //insert and examine
}
catch(SQLException e)
{
System.out.println("here1"+e);
System.err.println("reported recursion level was "+e.getStackTrace().length);
return 0;
}
finally{
try{
rs.close();}
catch(final Exception e1)
{
System.out.println("here2"+e1);
}
}
}
public void insert(FifteenPuzzle sub)
{
try{
String str=sub.toDBString();
ps2.setInt(1,sub.hashcode());
ps2.setString(2, str);
ps2.setInt(3,sub.g_n);
ps2.executeUpdate();
ps2.clearParameters();
}catch(SQLException e)
{
System.out.println("here3"+e);
}
}
public void InsertInDB(FifteenPuzzle sub) throws SQLException
{
System.out.println(k++);
int i;
int p=updateIfNecessary(sub);
if(p==0)
{
System.out.println("returning");
return;
}
if(p==2)
{
insert(sub);
System.out.println("inserted");
}
//FifteenPuzzle temp=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n);
for(i=0;i<sub.puzzle.length;i++)
{
if(sub.puzzle[i]!=0)
{
//check the positions it can be moved to
if(i%4!=0 && sub.puzzle[i-1]==0) //left
{
//create another clone and increment the moves
FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
//exchange positions
int t=temp_inner.puzzle[i];
temp_inner.puzzle[i]=temp_inner.puzzle[i-1];
temp_inner.puzzle[i-1]=t;
InsertInDB(temp_inner);
}
if(i%4!=3 && sub.puzzle[i+1]==0) //right
{
//create another clone and increment the moves
FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
//exchange positions
int t=temp_inner.puzzle[i];
temp_inner.puzzle[i]=temp_inner.puzzle[i+1];
temp_inner.puzzle[i+1]=t;
InsertInDB(temp_inner);
}
if(i/4!=0 && sub.puzzle[i-4]==0) //up
{
//create another clone and increment the moves
FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
//exchange positions
int t=temp_inner.puzzle[i];
temp_inner.puzzle[i]=temp_inner.puzzle[i-4];
temp_inner.puzzle[i-4]=t;
InsertInDB(temp_inner);
}
if(i/4!=3 && sub.puzzle[i+4]==0) //down
{
//create another clone and increment the moves
FifteenPuzzle temp_inner=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n+1);
//exchange positions
int t=temp_inner.puzzle[i];
temp_inner.puzzle[i]=temp_inner.puzzle[i+4];
temp_inner.puzzle[i+4]=t;
InsertInDB(temp_inner);
}
}
}
类中的函数 insertInDB(FifteenPuzzle fp)是递归函数，并且首先从具有15个拼图参数数组的主函数中调用(puzzle是Class <的整数数组字段FifteenPuzzle)为-1,2,3,4,0,6,0,0,0,0,0,0,0,0,0,0(与上述矩阵相同).在解释其他功能之前，我将解释什么是静态模式数据库.简短(由于下面的评论)
The function insertInDB(FifteenPuzzle fp) in the class is the recursive function and is called first from the main function with the array for the fifteen puzzle argument(puzzle is an integer array field of the Class FifteenPuzzle) being - 1,2,3,4,0,6,0,0,0,0,0,0,0,0,0,0(same as the matrix shown above). Before explaining the other functions I will explain what static pattern database is; briefly(Because of the comments below)
模式数据库是用于解决15个难题的启发式方法(可以是任何难题.但是在这里，我仅讨论15个难题).启发式是用于确定接下来要扩展哪个状态的数字.我就像每个州的成本.这里的状态是15拼图的置换.对于8-Puzzle之类的简单难题，启发式可以是曼哈顿距离.对于每个未放置的图块，它给出了达到它的目标位置的最少移动次数.然后将所有图块的曼哈顿距离相加，得出该图块的成本.曼哈顿距离为达到目标状态所需的移动次数估算值提供了下限，即您无法通过移动达到小于曼哈顿距离的目标状态来达到目标状态.尽管可以接受，但 BUT 曼哈顿距离并不是很好的启发式方法，因为它不考虑附近的其他区域.如果必须将图块移动到其目标位置，则也必须移动附近的图块，并且移动次数增加.因此，对于这些难题，显然，实际成本要大得多，
曼哈顿距离.
为了克服这个(曼哈顿距离)并考虑其他图块，引入了模式数据库.
静态模式数据库包含子问题或一组图块达到其目标状态的启发式方法.由于您正在计算使这些图块组达到其目标状态的移动次数，因此在移动图块时将考虑该组中的其他图块.因此，这是一种更好的启发式方法，并且通常总是大于曼哈顿距离.
5-5-5静态模式只是静态模式数据库的一种形式，其中组的数量为3，其中两个组每个包含5个图块，而第三个组则包含6(第6个为空白图块).
Pattern databases are heuristics used to solve a fifteen puzzle(can be any puzzle. But here I will talk about only 15-Puzzle). A heuristic is a number used to determine which state to be expanded next. I is like cost of each state. Here state is a permutation of the 15-Puzzle. For simple puzzles like 8-Puzzle, the heuristic can be manhattan distance. It gives the minimum number of moves, for each misplaced tile, to reach it's goal position. Then manhattan distances for all the tiles are added up to give the cost for that tile. Manhattan distance gives the lower bound to the estimate of the number of moves required to reach the goal state i.e you cannot reach the goal state with moves, less than the manhattan distance. BUT manhattan distance is not a very good heuristic, though admissible, because it does not consider other tiles near by it. If a tile has to be moved to it's goal position, the near by tiles also have to be moved and the number of moves increase. So, clearly for these puzzles, the actual cost is mostly much greater that
the manhattan distance.
To overcome this(manhattan distance) and take into account the other tiles, pattern databases were introduced.
A static patter database holds the heuristics for sub-problems or for a group of tiles to reach for their goal state. Since, you are calculating the number of moves to make these group of tiles reach their goal state, the other tiles in that group will be taken into account when a tiles is being moved. So, this is a better heuristic and mostly will always is greater than manhattan distance.
5-5-5 static pattern is just a form of static pattern database where the number of groups are 3, two of them containing 5 tiles each and the third one contains 6(6th isthe blank tile).
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
我正在计算该组所有排列的试探法/移动次数，以达到上述配置，并将其插入我的数据库.
可能的组合总数(也是db中的行数)是
I am calculating the heuristics/number_of_moves for all permutations of this group to reach the above configuration and inserting them into my database.
The total number of combinations(also the no of rows in db) possible is
16!/(16-5)! = 524160
现在，其他函数-updateIfNecessary(FifteenPuzzle)-此函数检查数据库中是否已存在传递的FifteenPuzzle对象的数组.如果数据库中已存在该对象，则它将检查当前对象的成本是否小于DB中的成本.如果是，则将其替换为当前成本，否则不执行任何操作.函数-insert(FifteenPuzzle)插入具有成本的新置换.
注意::fifteenuzzle.g_n是解决难题的费用.对于表示上面矩阵的初始难题，成本为0，对于每一步，成本为incremented by1.
Now, the other functions - updateIfNecessary(FifteenPuzzle) - this function checks if the array of the passed FifteenPuzzle object is already present in the database. If already present in the database, it checks if the current object's cost is less than the cost in DB. If yes, it replaces it with the current cost else does nothing. The function -insert(FifteenPuzzle) inserts a new permutaion with the cost.
NOTE : fifteenuzzle.g_n is the cost for the puzzle. For the initial puzzle that represents the matrix above, the cost is 0 and for each move the cost is incremented by1.
对于运行配置中的堆栈大小，我已将堆栈大小设置为-Xss128m(1024、512和256给出了致命错误).
当前，递归数或深度为 7,500,000并计数(System.out.println(k++);的值).
可能的组合总数为
I have set the stack size to -Xss128m(1024, 512 and 256 were giving a fatal error) for stack size in run configurations.
Currently the recursion number or the depth is 7,500,000 and counting(value of System.out.println(k++);).
The total number of combinations possible is
16!/(16-5)! = 524160
但是深度已经达到了750万.这是由于生成重复状态.当前，数据库中的条目数为 513423 .您可能会认为现在只有10,000个条目可以填写.但是现在，录入的速率已大大降低，大约每30分钟 1个录入.那永远不会克服.
我需要一个实用的解决方案-有或没有递归.有可能吗?
But the depth has already reached 7,500,000. This is because of generation of duplicate states. Currently the number of entries in the database is 513423. You might think that there only 10,000 entries to fill up now. But now the rate at which entries are made has decreased drastically about 1 entry every 30 min. This will never get over then.
I need a solution that is practical - with or without recursion. Is it possible?
推荐答案
似乎您正在移动块以获取所有排列.然后，检查要存在于数据库中的每个排列；如果是，则在必要时更新步数.
It seems that you are moving the blocks to get all the permutations. Then, checking each permutation to be present in DB; if yes then updating the number of moves if necessary.
它将生成一棵树.您正在以DFS样式(通过递归调用)生成它.如果您以BFS风格进行操作，那么您将始终获得最少的移动次数.稍后生成的重复状态将始终需要更大的移动.因此，您不必在数据库中进行比较.
It would generate a tree. You are generating it in DFS style (by recursive calls). If you do it in BFS style, then you will always get the smallest number of moves. The duplicate states generated later would always have larger moves required. So, you don't have to compare it in the DB.
在以下示例中，我们将移动6，然后查看移动数量.
In the following examples, we will shift 6 and then we see the number of moves.
Priority: Left, Right, Up, Down (as you gave)
DFS样式
1 2 3 4 1 2 3 4
0 6 0 0 6 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
(0) (1)
达到最高职位.现在，检查以将其移至正确位置(从其来源).该位置已经在数据库中了，所以继续. 而且，它甚至无法上升.所以下去.
Left most position reached. Now, check to move to it right (from where it came from). That position is already there in the DB, so carry on. Moreover, it can't even go up. So going down.
1 2 3 4 1 2 3 4
0 0 0 0 0 0 0 0
6 0 0 0 0 0 0 0
0 0 0 0 6 0 0 0
(2) (3)
现在，向右走
State-1 State-2 State-3
1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
6 0 0 0 0 6 0 0 0 0 6 0 0 0 0 6
(3) (4) (5) (6)
在这里您可以看到，只需2次(而不是4次)移动即可达到State-1.但这将在以后显示，我们将不得不更新数据库.因此，显然这是在浪费精力.
Here you can see that, State-1 can be reached in just 2 (not 4) moves. But that will be revealed later and we'd have to update the DB. So, clearly its a waste of effort.
BFS样式
1 2 3 4 1 2 3 4
0 6 0 0 6 0 0 0
0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0
(0) (1)
到达最左边的位置，现在向右走
Leftmost position reached, now go right
1 2 3 4 1 2 3 4
0 0 6 0 0 0 0 0
0 0 0 0 0 6 0 0
0 0 0 0 0 0 0 0
(1) (1)
您可以将其视为6均匀分布在所有侧面.
同样，在这里，我们将有重复的状态，但是与数据库的第一个条目相比，这些状态需要的最小移动次数更大.
You can consider this as 6 spreading all the sides equally.
Here also, we would have duplicate states but those would have larger min moves required than the first entry of the DB.
您可以使用一个简单的队列来实现此目的.
You can use a simple queue to implement this.
伪代码:
Initialize no_of_moves by 0
enqueue(startingPosition)
insertIntoDB(startingPattern, no_of_moves)
while((currentPattern = dequeue()) is not null)
if(currentPattern is not already traversed)
insertIntoDB(currentPattern);
list<Pattern> allPatterns = patterns which can be reached from currentPattern in just 1 move
no_of_moves++
enqueue(allPatterns, no_of_moves)
end if
end while
除了从数据库中检查状态外，还有许多方法可以检查状态是否已经遍历.我当时在考虑散列，但无法进行.
There can be many ways to check if a state has already been traversed besides checking it from the DB. I was thinking of hashing but not able to come up.
您可以维护从模式字符串映射的布尔列表(例如traversed["1234060000000000"] = true or false).我认为在主存储器中存储524160条目不会造成任何问题.
You can maintain a boolean list mapped from the pattern string (say traversed["1234060000000000"] = true or false). I don't think storing 524160 entries in the main memory would create any problem.
这篇关于需要一个实用的解决方案来为15个拼图创建模式数据库(5-5-5)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
