Perjia/connectk — pull request #3 by darlliu (2013-03-06 20:19:56+00:00)
Title: New fixes

Hi Afshin:

I did a few fixes the other day and forgot to tell you. Basically the problem I was trying to address is how to preserve the order to begin search with each deepening search n=1,2,3....

This would be easy if we can traverse the priority queue and reorder it at will, unfortunately both are impossible in C++ context so what I did was I have to reallocate the queue and then make a copy in the form of a vector to traverse. This does not impact speed significantly because we are only able to search to depth 4 in 6 seconds.

Another issue is when the search is terminated we have to call update_frontier again before popping the queue, this is because the queue only updates order on push/pop so we have to rebuild it to get a whole new ordering.

Also, I think the way we should continue is this:

I have a virtual function addheuristics (called during search), which report the final weighted value of a end node. Better node should have bigger values and values should be int (can be changed to float).

What we can do is simply to inherit this class, not touch it and override addheuristics which can then call multiple heuristic functions. Each function should be static in that it only evaluates NewStates which is updated as the search goes downward. So as long as we just read from NewStates (Col*Row 2d array) and return a static value then we don't need to do anything at all to the base class. it will be called automatically and should be updated with pruning and everything.

Let's hurry up and try to implement at least one heuristic this week, then I'll finish up the testing during the weekend and we can move on.