I chose this heuristic because it favored board configurations that were more clumped together (the average distance being smaller) and punished boards that were too spread out or left too many isolated pegs, either of which could indicate a dead-end. Extra Credit Manhattan Distanceįor my extra credit, I implemented a manhattan distance function that calculated the manhattan distance from every peg to every other peg on the board, and then divided that score by the number of pegs on the board times two. Regarding optimality, the peg puzzle does not really have an ‘optimal’ solution, in that all solutions will always occur after the same number of moves and therefore all paths are in fact optimal. 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)
