Necesita una solución práctica para crear una base de datos de patrones (5-5-5) para 15-Puzzle
Para la base de datos de patrones estáticos (5-5-5), veaesta(página 290 y 283) O hay una explicación a continuación. por¿Qué es el 15-puzzle?
Estoy creando una base de datos de patrones estáticos (5-5-5). Este código para completar las entradas en la primera tabla. Lo estoy haciendo a través de la función recursiva.insertInDB(). La primera entrada a la función recursiva es esta (en realidad, el rompecabezas de la entrada lo contiene en una matriz 1-D. Para una mejor comprensión, la he representado como 2-D a continuación)
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
Este es mi código:
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);
}
}
}
La funcióninsertInDB (FifteenPuzzle fp) en la clase está la función recursiva y se llama primero desde la función principal con la matriz para el argumento de quince rompecabezas (puzzle es un campo de matriz entera de la claseFifteenPuzzle) siendo -1,2,3,4,0,6,0,0,0,0,0,0,0,0,0,0(igual que la matriz mostrada arriba). Antes de explicar las otras funciones, explicaré qué es la base de datos de patrones estáticos; brevemente (Debido a los comentarios a continuación)
Las bases de datos de patrones son heurísticas utilizadas para resolver un rompecabezas de quince (puede ser cualquier rompecabezas. Pero aquí hablaré de solo 15-Puzzle). Una heurística es un número que se utiliza para determinar qué estado se expandirá a continuación. Es como el costo de cada estado. Aquí el estado es unpermutación del 15-puzzle. Para rompecabezas simples como 8-Puzzle, la heurística puede serdistancia de manhattan. Da el número mínimo de movimientos, para que cada ficha fuera de lugar, alcancesus posición de la meta. Luego, las distancias de manhattan para todas las fichas se suman para dar el costo de esa ficha. La distancia de Manhattan proporciona el límite inferior a la estimación del número de movimientos necesarios para alcanzar el estado objetivo, es decir, no se puede alcanzar el estado objetivo con movimientos, menos que la distancia de Manhattan.PERO La distancia de Manhattan no es una buena heurística, aunque admisible, porque no considera otras baldosas cercanas. Si hay que mover una ficha a su posición de objetivo, las fichas cercanas también deben moverse y el número de movimientos aumenta. Entonces, claramente para estos rompecabezas, el costo real es mayor que el de Manhattan.
Asuperar Esto (distancia de Manhattan) y teniendo en cuenta los otros mosaicos, se introdujeron bases de datos de patrones. Una base de datos de patrones estáticos mantiene las heurísticas para problemas secundarios o para que un grupo de fichas alcance su estado objetivo. Como está calculando la cantidad de movimientos para hacer que estos grupos de cuadros alcancen su estado objetivo, los otros cuadros de ese grupo se tendrán en cuenta cuando se mueva un cuadro. Entonces, esta es una mejor heurística y en su mayoría siempre será mayor que la distancia de Manhattan.
5-5-5 el patrón estático es solo una forma de base de datos de patrones estáticos donde el número de grupos es 3, dos de ellos con 5 mosaicos cada uno y el tercero contiene 6 (el 6º es el azulejo en blanco).
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
Estoy calculando las heurísticas / número_de_movimientos para que todas las permutaciones de este grupo alcancen la configuración anterior yinsertándolos en mi base de datos.
El número total de combinaciones (también el número de filas en db) posible es
16!/(16-5)! = 524160
Ahora, las otras funciones -updateIfNecessary(FifteenPuzzle) - esta función comprueba si la matriz del objeto FifteenPuzzle pasado ya está presente en la base de datos. Si ya está presente en la base de datos, comprueba si el costo del objeto actual es menor que el costo en DB. Si es así, lo reemplaza con el costo actual, de lo contrario no hace nada. La función -insert(FifteenPuzzle) Inserta una nueva permutaion con el costo.
NOTA : fifteenuzzle.g_n Es el costo del rompecabezas. Para el rompecabezas inicial que representa la matriz anterior, el costo es0 y por cada movimiento el costo esincremented by1.
He establecido el tamaño de pila a -Xss128m(1024, 512 y 256 dieron un error fatal) para el tamaño de pila en las configuraciones de ejecución.
Actualmente el número de recursión o la profundidad es7,500,000 y contando(valor deSystem.out.println(k++);).
El número total de combinaciones posibles es
16!/(16-5)! = 524160
Pero la profundidad ya ha alcanzado los 7.500.000. Esto se debe a la generación de estados duplicados. Actualmente el número de entradas en la base de datos es513423. Podrías pensar que solo hay 10,000 entradas para llenar ahora. Pero ahora la velocidad a la que se hacen las entradas ha disminuido drásticamente sobre1 entrada cada 30 min.. Esto nunca superará entonces.
Necesito una solución que sea práctica.con o sin recursion. ¿Es posible?