Potrzebujesz praktycznego rozwiązania do tworzenia bazy wzorców (5-5-5) dla 15-Puzzle
Aby zobaczyć statyczną bazę danych wzorów (5-5-5), zobaczto(strona 290 i 283) LUB istnieje wyjaśnienie poniżej. DlaCo to jest 15-puzzle?
Tworzę statyczną bazę danych Tupot (5-5-5). Ten kod służy do wypełniania wpisów w pierwszej tabeli. Robię to za pomocą funkcji rekurencyjnejinsertInDB(). Pierwszym wejściem do funkcji rekurencyjnej jest to (faktycznie układanka wejściowa zawiera ją w tablicy 1-D. Dla lepszego zrozumienia przedstawiłem ją jako 2-D poniżej)
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
To jest mój kod:
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);
}
}
}
FunkcjainsertInDB (FifteenPuzzle fp) w klasie jest funkcja rekurencyjna i jest nazywana najpierw z funkcji głównej z tablicą dla piętnastu argumentów układanki (puzzle jest polem tablicy z liczbą całkowitąFifteenPuzzle) będąc -1,2,3,4,0,6,0,0,0,0,0,0,0,0,0,0(tak samo jak matryca pokazana powyżej). Zanim wyjaśnię inne funkcje, wyjaśnię, czym jest statyczna baza danych wzorów; krótko (z powodu komentarzy poniżej)
Bazy danych wzorców są heurystykami używanymi do rozwiązania piętnastu zagadek (może to być dowolna łamigłówka. Ale tutaj będę mówił tylko o 15 układankach). Heurystyka to liczba używana do określenia, który stan należy rozwinąć w następnej kolejności. Jestem jak koszt każdego państwa. Tutaj jest stanpermutacja 15-Puzzle. W przypadku prostych łamigłówek, takich jak 8-Puzzle, heurystyka może byćodległość manhattan. Daje minimalną liczbę ruchów, do osiągnięcia każdej zagubionej płytkijego pozycja bramkowa. Następnie odległości manhattan dla wszystkich płytek są sumowane, aby dać koszt tej płytki. Odległość na Manhattanie daje dolną granicę oszacowania liczby ruchów wymaganych do osiągnięcia stanu bramkowego, tj. Nie można osiągnąć stanu bramkowego z ruchami, mniejszymi niż odległość na Manhattanie.ALE odległość na Manhattanie nie jest bardzo dobrą heurystyką, choć dopuszczalna, ponieważ nie uwzględnia innych kafelków w pobliżu. Jeśli płytka musi zostać przesunięta na swoją pozycję celu, bliskie kafelki również muszą zostać przesunięte, a liczba ruchów wzrasta. Tak więc, wyraźnie dla tych zagadek, rzeczywisty koszt jest znacznie większy niż odległość na Manhattanie.
Doprzezwyciężać to (odległość na Manhattanie) i uwzględnij inne płytki, wprowadzono wzorcowe bazy danych. Baza danych statycznych zawiera heurystyki dla podproblemów lub dla grupy płytek, aby osiągnąć ich stan celu. Ponieważ obliczasz liczbę ruchów, aby te grupy płytek osiągnęły swój stan celu, pozostałe płytki z tej grupy będą brane pod uwagę przy przesuwaniu płytek. Jest to więc lepsza heurystyka i zazwyczaj zawsze będzie większa niż odległość na Manhattanie.
Statyczny wzorzec 5-5-5 jest tylko formą statycznej bazy danych wzorów, w której liczba grup wynosi 3, dwie z nich zawierają po 5 płytek, a trzecia zawiera 6 (6 jest pustą płytką).
1 2 3 4
0 6 0 0
0 0 0 0
0 0 0 0
Obliczam heurystyki / liczba_przesuwów dla wszystkich permutacji tej grupy, aby osiągnąć powyższą konfigurację iwstawienie ich do mojej bazy danych.
Całkowita liczba kombinacji (również liczba wierszy w db) jest możliwa
16!/(16-5)! = 524160
Teraz inne funkcje -updateIfNecessary(FifteenPuzzle) - ta funkcja sprawdza, czy tablica przekazanego obiektu FifteenPuzzle jest już obecna w bazie danych. Jeśli jest już obecny w bazie danych, sprawdza, czy koszt bieżącego obiektu jest mniejszy niż koszt w DB. Jeśli tak, zastępuje go bieżącym kosztem, inaczej nic nie robi. Funkcja -insert(FifteenPuzzle) wstawia nową zgodę z kosztem.
UWAGA : fifteenuzzle.g_n to koszt układanki. Dla początkowej układanki, która reprezentuje powyższą macierz, koszt wynosi0 i dla każdego ruchu koszt jestincremented by1.
Ustawiłem rozmiar stosu na -Xss128m(1024, 512 i 256 dawały błąd krytyczny) dla rozmiaru stosu w konfiguracjach run.
Obecnie liczba rekursji lub głębokość jest7,500,000 i liczenie(wartośćSystem.out.println(k++);).
Całkowita liczba możliwych kombinacji jest
16!/(16-5)! = 524160
Ale głębokość osiągnęła już 7 500 000. Wynika to z generowania zduplikowanych stanów. Obecnie liczba wpisów w bazie danych wynosi513423. Możesz pomyśleć, że do wypełnienia jest teraz tylko 10 000 wpisów. Ale teraz tempo wprowadzania wpisów zmalało drastycznie1 wpis co 30 minut. To nigdy się nie skończy.
Potrzebuję praktycznego rozwiązania -z rekursją lub bez. Czy to możliwe?