Databases
StackOverflow2013
Postsdbo
POIterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POIterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java
    primarykey
    data
    text
    <p>I've implemented a program able to solve the <a href="http://en.wikipedia.org/wiki/Fifteen_puzzle" rel="nofollow">n-puzzle problem</a> with A*. Since the space of the states is too big I cannot precompile it and I have to calculate the possible states at runtime. In this way A* works fine for a 3-puzzle, but for a 4-puzzle can take too long. Using Manhattan distance adjusted with linear conflicts, if the optimal solution requires around 25 moves is still fast, around 35 takes 10 seconds, for 40 takes 180 seconds. I haven't tried more yet.<br> I think that's because I must keep all visited states, since I'm using functions admissible but (I think) not consistent (i tried also with Hamming and Gaschnig distances and a few more). Since the space of the solution is a graph the heuristic must also be consistent, otherwise the algorithm can loop or be not optimal. That's why I keep all visited nodes (it's also written in the book "AI: A modern approach"). But anyway, this storage does not slow at all. What slows is keeping the queue of nodes to be visited ordered.<br> So I decided to try IDA* that, as I saw, does not require this storage (but still I have to keep all visited states to avoid loops). It's faster for solutions that require 35 or less moves, but for 40 it's much slower.<br> Here is my code. Am I doing something wrong?</p> <pre><code>public static State solveIDAStar(State initialState) { int limit = initialState.getManhattanDistance() + 2 * initialState.getLinearConflicts(); State result = null; while(result == null) { visitedStates.add(initialState); // It's a global variable result = limitedSearch(initialState, limit); limit = newLimit; visitedStates.clear(); } return result; } public static State limitedSearch(State current, int limit) { for(State s : current.findNext()) { if(s.equals(GOAL)) { s.setParent(current); return s; } if(!visitedStates.contains(s)) { s.setPathCost(current.getPathCost() + 1); s.setParent(current); int currentCost = s.getManhattanDistance() + 2 * s.getLinearConflicts() + s.getPathCost(); if(currentCost &lt;= limit) { visitedStates.add(s); State solution = limitedSearch(s, limit); if(solution != null) return solution; } else { if(currentCost &lt; newLimit) newLimit = currentCost; } } } return null; } </code></pre>
    singulars
    1. PO
      singulars
      1. PTAnswer
    1. This table or related slice is empty.
    1. PTQuestion
    1. USSimon
    1. USSimon
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    2. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POIterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POIterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java
      1. USpratikch
      1. VTFavorite
    3. VO
      singulars
      1. POIterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java
      1. This table or related slice is empty.
      1. VTUpMod
    1. COWhere do you modify `current`? As I see it - the algorithm will return an answer only if there is a direct edge between source to target - but I am probably missing something here. Could you clarify this point?
      singulars
      1. POIterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java
      1. USamit
    2. CO@amit I don't modify the object itself, but I call the function recursively giving each time a current's successor. It's a normal recursive DFS, with a depth-limit (chosen using a heuristic).
      singulars
      1. POIterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java
      1. USSimon
    3. COYes, I missed the recursive call for some reason. Thanks for clarifying.
      singulars
      1. POIterative Deepening A Star (IDA*) to solve n-puzzle (sliding puzzle) in Java
      1. USamit
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload