In the peg puzzle, this is not the case: although there are duplicate states, no move will ever lead to itself again and so there is not risk of falling into loops. Regarding completeness, naive DFS in most search spaces can easily end up getting trapped in loops around the same states. Upon more careful inspection this is due to the fact that the heuristics that are being used are extremely poor predictors of performance.Īpplying DFS to the peg puzzle is especially effective due to the fact the nature of the puzzle solves most of the ‘problems’ that typically emerge in dealing with DFS: namely completeness and optimality. In actuality though, the opposite it true: A* found a solution only marginally faster than BFS, and was several factors of magnitude slower than uninformed DFS. It occurred to me that the heuristics that we were testing with were not ideal, but I had presumed that they would manage to find a solution at least as quickly as DFS. What I had not anticipated was how poorly A* and IDA* performed.
I had anticipated that it would perform far better than breadth first search (BFS): all the available solutions occur at depth 13, and they are fairly numerous. Of all the search strategies, depth first search (DFS) performed the best by far. Written using Python3.4 with numpy 1.9.2 Analysis of Search Strategies
0 kommentar(er)
