I implemented the iterative deepening a-star search(for the 8-Puzzle problem, but can accept other problems) and ran it on an input. It ran unsuccessfully for 2 hrs. For simpler inputs that are close to goal node it works fine. Others have got it to work for this input. I am not sure whether my implementation is just inefficient or goes into an infinite loop
PuzzleSolver.java$ida
/** Accepts start node root and string identifying whihc heuristic to use
* h1 is number of misplaced tiles and h2 is Manhattan distance
*/
private Node ida(Node root, final String h) {
PriorityQueue<DNode> frontier = new PriorityQueue<DNode>(10, new Comparator<DNode>(){
@Override
public int compare(DNode n1, DNode n2) {
if(h == "h1") {
if(n1.depth + h1(n1.node) > n2.depth + h1(n2.node)) return 1;
if(n1.depth + h1(n1.node) < n2.depth + h1(n2.node)) return -1;
return 0;
}
if(h == "h2") {
if(n1.depth + h2(n1.node) > n2.depth + h2(n2.node)) return 1;
if(n1.depth + h2(n1.node) < n2.depth + h2(n2.node)) return -1;
return 0;
}
return 0;
}});
ArrayList<Node> explored = new ArrayList<Node>();
Node soln = null;
DNode start = new DNode(root, 1);
frontier.add(start);
int d = 0;
int flimit = (h == "h1" ? h1(start.node) : h2(start.node));
int min = flimit;
while(true) {
DNode dn = frontier.poll();
if(dn == null) {
frontier.add(start);
d = 0;
flimit = min;
continue;
}
d = dn.depth;
Node n = dn.node;
//n.print();
if(goalCheck(n)){
return n;
}
for(int i = 0;i < ops.length;i++) {
String op = ops[i];
if(n.applicable(op)) {
soln = n.applyOp(op);
int h_cost;
if(h == "h1") h_cost = h1(soln);
else h_cost = h2(soln);
if(!checkDup(explored,soln) && d + 1 + h_cost < flimit) {
frontier.add(new DNode(soln, d + 1));
DNode least = frontier.peek();
min = least.depth + (h == "h1" ? h1(least.node) : h2(least.node));
}
}
}
explored.add(n);
max_list_size = Math.max(max_list_size, frontier.size() + explored.size());
}
}
PuzzleSolver.java$CheckDup
private boolean checkDup(ArrayList<Node> explored, Node soln) {
boolean isDuplicate = false;
for(Node n:explored) {
boolean equal = true;
for(int i = 0;i < soln.size; i++) {
for(int j =0 ;j<soln.size;j++) {
if(soln.state.get(i).get(j) != n.state.get(i).get(j)) {
equal = false;
}
}
}
isDuplicate |= equal;
}
return isDuplicate;
}
Start state(failed):
1 2 3
8 - 4
7 6 5
Goal state:
1 3 4
8 6 2
7 - 5
(worked for 1 3 4 8 6 0 7 5 2) I have not included Node.java because I am pretty sure it works after running other search algorithms like best-first, dfs. It is difficult to provide an SCCE, so I am just asking for help spotting any obvious bugs in the ida implementation.
EDIT: Solved issue, but still trying to figure out a termination condition when the goal is not reachable. IDA* does not keep a list of explored nodes, so how can I know if I have covered the whole solution space?
There was a mistake in the way I calculated the new flimit. It did not cause a problem in the other cases because the flimit of the successor was such that it did not cause it to loop infinitely. Also the condition should f(current node) <= cutoff. and not '<' as I took.
Updated version:
private Node ida(Node root, final String h) {
PriorityQueue<DNode> frontier = new PriorityQueue<DNode>(10, new Comparator<DNode>(){
@Override
public int compare(DNode n1, DNode n2) {
if(h == "h1") {
if(n1.depth + h1(n1.node) > n2.depth + h1(n2.node)) return 1;
if(n1.depth + h1(n1.node) < n2.depth + h1(n2.node)) return -1;
return 0;
}
if(h == "h2") {
if(n1.depth + h2(n1.node) > n2.depth + h2(n2.node)) return 1;
if(n1.depth + h2(n1.node) < n2.depth + h2(n2.node)) return -1;
return 0;
}
return 0;
}});
ArrayList<Node> explored = new ArrayList<Node>();
Node soln = null;
DNode start = new DNode(root, 1);
frontier.add(start);
int d = 0;
int flimit = (h == "h1" ? h1(start.node) : h2(start.node));
int min = flimit;
while(true) {
DNode dn = frontier.poll();
if(dn == null) {
explored.clear();
frontier.add(start);
d = 0;
flimit = min;
continue;
}
d = dn.depth;
Node n = dn.node;
//n.print();
if(goalCheck(n)){
return n;
}
min = Integer.MAX_VALUE;
for(int i = 0;i < ops.length;i++) {
String op = ops[i];
if(n.applicable(op)) {
soln = n.applyOp(op);
int h_cost;
if(h == "h1") h_cost = h1(soln);
else h_cost = h2(soln);
if(!checkDup(explored,soln)) {
if(d + 1 + h_cost <= flimit) {
frontier.add(new DNode(soln, d + 1));
}
else {
if(d + 1 + h_cost < min)min = d + 1 + h_cost;
}
}
}
}
explored.add(n);
max_list_size = Math.max(max_list_size, frontier.size() + explored.size());
}
}