基于遗传算法的八数码问题的设计及实现

Design and Implementation of Eight Puzzle Problem Based on Genetic Algorithms

介绍了遗传算法(GA)在八数码问题中的应用。首先介绍了八数码问题及遗传算法的相关知识,分析了求解八数码问题的传统解决方案;然后给出了八数码问题的遗传算法模型,并对此模型进行了算法的设计,即确定编码的表示、选择算子、交叉算子、变异算子及适应度函数;最后把此算法运用到基于八数码问题的拼图游戏求解过程的动态演示上。文中对此算法进行了多角度试验,试验表明采用遗传算法解决八数码问题是有效的、稳定的,具有较高的搜索效率。

Introduces the application of genetic algorithms in the eight puzzle problem. Firsdy depicted the knowledge about the eight puzzle problem and the CA, analyzed the classical solutions. Then presented a model based on GA and designed the algorithm based on the model. Lastly implemented a game which can demonstrate the process of motion dynamically. This algorithm was tested with several aspects, it is proved that the algorithm is available and efficient, with the higher search efficiency.