Need a practical solution for creating pattern dat

问题:

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

---

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);

                  }
             }   
       }

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)

What is a (5-5-5) static pattern database for 15-Puzzle?

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).

One of the groups is this matrix :

1  2  3  4
0  6  0  0
0  0  0  0
0  0  0  0

---

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

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.

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

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?

回答1:

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.

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.

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 Style

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)

Now, go right

           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)

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 Style

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)

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.

Pseudocode:

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.

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.

回答2:

The important part is the first line: java.lang.StackOverflowError. Recursion is stack-demanding.

Try doing only the algorithm part recursively, while putting the DB access in an extra method.

回答3:

You should not call recursive. Doing so will put another address on the stack in your memory and if this happens too often you run out of memory, which happens in your case: StackOverflowError
Try to make a mothod that lets you input data once and then call that method in a loop until all data is saved in your database.

回答4:

You are creating new PreparedStatement objects in each method call, which is here a recursive method. ex. ps=connection.prepareStatement(read_statement); and ps=connection.prepareStatement(insert_statement);. Create two seperate PreparedStatement object for both and move them out of the method and call ps.clearParameters(); at the start of the method (for both the objects). With that you have to deal with only two objects where as here you are creating thousands of objects. And then take care of closing resources when no longer needed. (ie., before FifteenPuzzle temp=new FifteenPuzzle(sub.puzzle.clone(),2,sub.g_n); )

回答5:

I would guess that your problem has to do with resource mis-management rather than recursion itself. Also, you're trying to complicate your implementation more than you need to. I would suggest the following:

• Create a method that would insert/update data to your database. Manage your resources over here. This need not be recursive.
• From your recursive method, call this method to insert/update data to your database.

This is cleaner because you know that the database specific method would close all the resources before it gets back to your recursion. However, I would suggest that you should reuse your connection object while calling this method.

Also, make sure to close your statements, resultset or even your connection as part of finally block. One issue that I can see, for starters is this:

• You're trying to close your preparedstatement in a try-block or a if-block. What if you don't hit the if-block and you hit an exception before you get a chance to close the resources? Your PreparedStatement and other resources will never be closed.