基于Trie树的BFS搜索算法求解“华容道”游戏最优解

BFS Algorithm for Solving Optimal Solution of Huarongdao Game Based on the Trie Tree Data Structure

"华容道"是中国古代传统单人玩的拼板类游戏。求解游戏最优解是人工智能搜索的一个典型问题,国内外学者提出了许多算法。针对华容道游戏特点,提出了基于Trie树的BFS搜索算法求解游戏最优走法,并对算法进行了复杂性分析。实验证明这种算法求解速度快,是求解华容道问题最优解的有效方法。

Huarongdao is a very famous puzzled of China. Optimal solution of the game is a classical problem in artificial intelligence. For solving this problem, many algorithms have been proposed by scholars. BFS algorithm based on the Trie tree data structure was put forward to solve optimal solution of Huaronddao game, the complexity of which was analyzed as well. It was demonstrate that the algorithm proposed in this paper can obtain the optimal result fast. So this algorithm was rather efficient for solving optimal solution of Huarrongdao game problem.