So I have implemented 2 different solvers for the game Sokoban.
The solvers is simple, given a starting state(position), if initial state is the goal state then return result. Else generate child states and store them into whatever data structure correspond to the algorithm. (Queue for BFS and a priority queue for A*) It then pops the first child state from the data structure to check if it's goal state else generate child state and store into structure, repeats this process until a goal state is found.
At the moment, the A* algorithm is indeed better than the BFS so that less nodes was generated before it finds the result. However, my problem is that the A* algorithm takes longer to compute. For example in one of the levels, the BFS algorithm generated 26000 nodes whereas the A* only generated 3488, yet the A* took a second longer than the BFS to complete.
From using time profiler I have concluded that the Priority queue data structure that was used to store the nodes is responsible for this slow down. Because every time a node is inserted into the queue the priority queue has to run the heuristic function algorithm to determine if the new state should be the closest state to the goal state (So it places that node in the first thing in the queue).
Now my question is, do you guys think it's a problem with my implementation or this is normal due to the overhead caused in calculating the heuristic function.
Another hypothesis to look into (hypotheses is the best we can do without having your code available to look at): maybe you're re-computing your heuristic score (which I assume is a relatively expensive thing to compute in your case) unnecessarily often.
Where in your code do you compute the heuristic score? Do you
Node object such that you can instantly retrieve it when you need it?Comparator function/functor/etc. is used by your Priority Queue to determine ordering of nodes?In the second case, you'll very frequently re-compute the heuristic score for nodes for which you've already done so before. For example, suppose you have 100 nodes currently in the Priority Queue, and you try to insert a new node. In the second case, inserting that new node will likely require comparisons with a bunch out of those 100 existing nodes before you've figured out where the new one belongs, and may therefore require a bunch of additional heuristic score computations.
If you went with the first option (which is what I'd recommend), those 100 existing nodes and the new node to add will all already have their heuristic score computed (precisely once), and stored in memory as a member variable. Performing a bunch of comparisons with a bunch of existing nodes will be very cheap, it will only require fetching the already-computed heuristic scores and not require re-computing them.
Actually, based on the text in your question, I suspect you're indeed currently using the (inefficient) second implementation. Otherwise your Priority Queue wouldn't be calling the heuristic function at all.
If, with the more efficient first implementation described above, you're still struggling with an overly-costly heuristic function, you could try investigating if it's possible to write a more efficient incremental implementation during the generation of successor states. Whether or not this is possible depends very much on exactly what your heuristic function is doing. But, I can imagine that in some cases, if you already have
sh(s)s'you may be able to derive an efficient, incremental algorithm that computes, based on what move was made, how h(s) can be incrementally modified to determine h(s') (and then you can store it immediately in the node for s')