对于静态模式数据库（5-5-5），请参阅此（第 290 和 283 页）或下面有说明。什么是 15 拼图？
我正在创建一个静态模式数据库（5-5-5）。此代码用于将条目填充到第一个表中。我是通过递归函数来做的insertInDB()。递归函数的第一个输入是这个（实际上输入拼图包含在一维数组中。为了更好地理解，我在下面将它表示为二维）
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
这是我的代码：
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)是递归函数，首先从主函数调用，其中十五个谜题参数的数组（puzzle是 Class 的整数数组字段FifteenPuzzle）为 - 1,2,3,4,0,6,0,0,0,0,0,0,0,0,0,0（与上面显示的矩阵相同） . 在解释其他功能之前，我将解释什么是静态模式数据库；简要地（因为下面的评论）
什么是 15-Puzzle 的 (5-5-5) 静态模式数据库？
模式数据库是用于解决 15 个谜题的启发式算法（可以是任何谜题。但这里我只讨论 15 个谜题）。启发式是用于确定接下来要扩展哪个状态的数字。我就像每个州的成本。这里的状态是 15-Puzzle 的排列。对于像 8-Puzzle 这样的简单谜题，启发式可以是manhattan distance。它为每个错放的瓷砖提供了最少的移动次数，以达到其目标位置。然后将所有瓷砖的曼哈顿距离相加，得出该瓷砖的成本。曼哈顿距离给出了到达目标状态所需移动次数的估计下限，即您无法通过移动达到目标状态，小于曼哈顿距离。但曼哈顿距离不是一个很好的启发式算法，虽然可以接受，因为它不考虑附近的其他瓷砖。如果必须将瓷砖移动到它的目标位置，则附近的瓷砖也必须移动，并且移动次数会增加。因此，显然对于这些谜题，实际成本大多远大于曼哈顿距离。克服
_这（曼哈顿距离）并考虑到其他瓷砖，引入了模式数据库。静态模式数据库保存子问题或一组图块的启发式方法，以达到其目标状态。由于您正在计算使这些图块组达到其目标状态的移动次数，因此在移动图块时将考虑该组中的其他图块。因此，这是一种更好的启发式方法，并且通常总是大于曼哈顿距离。
5-5-5静态模式只是静态模式数据库的一种形式，组数为3，其中两个包含5个tile，第三个包含6个（第6个是空白tile）。
其中一组是这个矩阵：
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
我正在计算该组的所有排列的启发式/number_of_moves 以达到上述配置并将它们插入到我的数据库中。
可能的组合总数（也是db中的行数）是
16!/(16-5)! = 524160
现在，其他函数——updateIfNecessary(FifteenPuzzle)这个函数检查传递的FifteenPuzzle 对象的数组是否已经存在于数据库中。如果数据库中已经存在，它会检查当前对象的成本是否小于数据库中的成本。如果是，它将用当前成本替换它，否则什么也不做。该函数 -insert(FifteenPuzzle)插入一个带有成本的新排列。
注意： fifteenuzzle.g_n是拼图的成本。对于表示上述矩阵的初始拼图，成本为0，每一步的成本为incremented by1。
对于运行配置中的堆栈大小，我已将堆栈大小设置为 - Xss128m（1024、512 和 256 给出了致命错误）。
目前递归数或深度是7,500,000和计数（的值System.out.println(k++);）。
可能的组合总数是
16!/(16-5)! = 524160
但深度已经达到了七百五十万。这是因为产生了重复状态。目前数据库中的条目数为513423。您可能认为现在只有 10,000 个条目需要填写。但是现在进入的速度已经急剧下降，大约每 30 分钟就有 1 次进入。这永远不会过去。
我需要一个实用的解决方案——有或没有递归。是否可以？