I am using manhattan distance + moves since the initial board for priority. It often happens that more possible next boards have same priority, how does the priority queue know which one to choose? When I first tried making solver it always chose wrong board. I found code on github and it used same logic as mine but that code always chose right one, he didn't have anything different in compareTo function what would do tie break. Now I started again and I've done something similar to github code and now it works and I don't know why. Does anyone have any idea what could have made difference?
This is basis of algorithm
minSearchNode = pq.delMin();
for(Board neighbour : minSearchNode.board.neighbors()){
if(minSearchNode.moves == 0){
pq.insert(new SearchNode(neighbour, minSearchNode.moves + 1, minSearchNode));
}
else if(!neighbour.equals(minSearchNode.previous.board)){
pq.insert(new SearchNode(neighbour, minSearchNode.moves + 1, minSearchNode));
}
}
I've read somewhere that it doesn't matter if A* does one wrong choice because it is heuristic and it will find the right solution later. Well it wouldn't program would just try millions of combinations and always choose wrong next board in tie break
I don't know what you were doing wrong at first, so I can't guess what changed to make the result correct. But what you read is right.
First, how a priority queue breaks ties is very much implementation dependent. The usual implementation is a heap. But there are advantages to using a DEQ instead. Either way you're only guaranteed that the next minimum is a minimum, but not which ones.
As for the "pick wrong", the search will switch what it is focused on as soon as you have to do anything that looks like a backtrack to something that is worse for the heuristic. Then it will try something else with a backtrack. If the heuristic is useful, this means that it keeps finding promising things to track until it finds a good route. If the heuristic does not prove useful, it can indeed face an exponential explosion.
Second, most A* implementations will keep track of the places it has reached. It is common to find multiple routes to the same node, but only the best one can wind up being best. Refusing to revisit nodes controls the search space and makes it easier to find the best route. But for searching a very large graph it may be prohibitive.
Third, I sometimes find it useful to have the priority NOT be a simple number. Instead make it a pair like (cost + heuristic, -cost). (This can be done in various ways.) What this does is prioritize by our estimate of how good the route is, and then prioritize by how far we've explored. This means that if there are multiple equally good paths, we'll explore whichever one we try first to the end before switching to the others. This can make a significant difference in how much of the space you explore.