loathwine
commented
9 years ago Progress report: I did some experiments and I noticed one odd thing, when I increased the limiting depth of the search tree, a solution would be found (which was quite long e.g. 27 steps instead of 7). While brushing my teeth I had a little eureka moment which I will now write down before I forget it. The problem has to do with some of the assumptions we do (which are not necessary wrong). In my explanation, let's assume (for simplicity purposes) there is only one solution A using X pursuers which is shorter than the limiting depth of the search tree. A solution should be found if we search the tree using BFS, right? I think so, but we use DFS and then strange things happen. We mark each visited state (or node in the tree) as visited when examining them AND a state can exist in several different parts of the tree (after all, in most cases we can reach a state in many different ways). Let the tree depth limit be 10 and the length of A be 7. The peculiar situation which can occur is that we explore some part of the tree using DFS and say that in depth 8 we visit the first state in the solution A, this search is sadly aborted before reaching the end of A because 8+7 > 10 (depth limit). Then our solver backtracks as expected and any potential way of reaching the solution A earlier on will fail because the first state in A is marked as visited (thus we assume that we have no business exploring that part of the tree). This situation should not be possible if doing BFS on the search tree, which is easier said than done in our case. We could also remove the limiting depth XOR removing the "visited states" feature. Both of these solutions greatly reduces performance. I think a reasonable solution is to implement a separate method using BFS for the exhaustive search case. I will try to do this when I have time.
There is a bug which we noticed a few months ago where we put our solver in "bruteforce mode" and still did not find a solution for a number of pursuers where we knew a solution existed. I have decided to investigate this bug a bit further since it bothered me. I noticed that for "trigridh4.txt", the solver will find a solution using four pursuers if using the greedy heuristic with BRUTEFORCE mode. It will, however, not find a solution using four pursuers if using the simple selector instead of the greedy one (which we imagine being an exhaustive search). I think this is the smallest example where we have spotted this bug.