静的パターン データベース (5-5-5) については、こちら(290 ページと 283 ページ) を参照してください。または、以下に説明があります。15パズルとは？
静的パターン データベースを作成しています(5-5-5)。このコードは、最初のテーブルにエントリを入力します。私は再帰関数を介してそれをやっていますinsertInDB()。再帰関数への最初の入力はこれです (実際には、入力パズルには 1 次元配列で含まれています。理解を深めるために、以下では 2 次元として表しています)
1 2 3 4
0 6 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)は再帰関数であり、メイン関数から最初に呼び出され、15 個のパズル引数の配列 (puzzleは Class の整数配列フィールドFifteenPuzzle) が - 1,2,3,4,0,6,0,0,0,0,0,0,0,0,0,0(上記の行列と同じ) です。 . 他の機能を説明する前に、静的パターン データベースとは何かを説明します。簡単に（以下のコメントのため）
15パズルの(5-5-5)静的パターンデータベースとは?
パターン データベースは、15 のパズル (どんなパズルでもかまいません。ただし、ここでは 15 のパズルについてのみ説明します) を解くために使用されるヒューリスティックです。ヒューリスティックとは、次に展開する状態を決定するために使用される数値です。私は各状態のコストのようなものです。こちらの状態は15パズルの順列です。8-Puzzle のような単純なパズルの場合、ヒューリスティックはマンハッタン距離になります。見当違いのタイルごとに、目標位置に到達するための最小移動数を示します。次に、すべてのタイルのマンハッタン距離を合計して、そのタイルのコストを算出します。マンハッタン距離は、目標状態に到達するために必要な移動数の推定値の下限を示します。つまり、マンハッタン距離未満の移動では目標状態に到達できません。しかしマンハッタン距離は、近くにある他のタイルを考慮していないため、許容できますが、あまり良いヒューリスティックではありません。タイルをゴール位置に移動する必要がある場合、近くのタイルも移動する必要があり、移動回数が増加します。したがって、明らかにこれらのパズルの実際のコストは、マンハッタンの距離よりもはるかに大きくなります。
克服するこれ（マンハッタン距離）と他のタイルを考慮して、パターン データベースが導入されました。静的パターン データベースには、サブ問題またはタイルのグループが目標状態に到達するためのヒューリスティックが保持されます。これらのタイルのグループが目標状態に到達するための移動数を計算しているため、タイルが移動されている場合、そのグループ内の他のタイルが考慮されます。したがって、これはより優れたヒューリスティックであり、ほとんどの場合、常にマンハッタン距離よりも大きくなります。
5-5-5 静的パターンは、グループの数が 3 である静的パターン データベースの形式であり、そのうちの 2 つはそれぞれ 5 つのタイルを含み、3 つ目は 6 つを含みます (6 つ目は空白のタイル)。
グループの 1 つがこのマトリックスです。
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0
このグループのすべての順列のヒューリスティック/number_of_moves を計算して、上記の構成に到達し、それらをデータベースに挿入しています。
可能な組み合わせの総数（dbの行数も）は
16!/(16-5)! = 524160
さて、他の関数 - updateIfNecessary(FifteenPuzzle)- この関数は、渡された FifteenPuzzle オブジェクトの配列がデータベースに既に存在するかどうかをチェックします。データベースに既に存在する場合は、現在のオブジェクトのコストが DB のコストよりも小さいかどうかを確認します。はいの場合、それを現在のコストに置き換えます。そうでない場合は何もしません。関数 -insert(FifteenPuzzle)コストで新しい順列を挿入します。
注 : fifteenuzzle.g_nはパズルの費用です。上記のマトリックスを表す最初のパズルの場合、コストは0であり、各移動のコストはincremented by1です。
実行構成のスタック サイズのスタック サイズを - Xss128m(1024、512、および 256 で致命的なエラーが発生しました) に設定しました。
現在、再帰数または深さは7,500,000であり、カウント( の値System.out.println(k++);) です。
可能な組み合わせの総数は
16!/(16-5)! = 524160
しかし、深さはすでに7,500,000に達しています。これは、重複した状態が生成されるためです。現在、データベースのエントリ数は513423です。現在、10,000 エントリしか入力されていないと思われるかもしれません。しかし、現在、エントリが作成される速度は、30 分ごとに 1 エントリ程度大幅に減少しています。これでは絶対に治りません。再帰の有無にかかわらず、
実用的なソリューションが必要です。出来ますか？