基于A^＊算法的八数码问题的优化实现  

Optimization of Eight Puzzle Problem Based on A^＊ Algorithm

作　　者：卜奎昊[1] 宋杰[1] 李国斌[1] 

机构地区：[1]安徽大学计算智能与信号处理教育部重点实验室,安徽合肥230039

出　　处：《计算机与现代化》2008年第1期29-31,35,共4页Computer and Modernization

摘　　要：用人工智能领域中经典的A*算法解决了人工智能中常见的八数码问题。本文首先介绍了八数码问题,然后对A*算法进行了解释。针对八数码问题给出并证明了路径不存在时的条件,并事先作了判定。定义了灵活的估价函数,分析了估价函数对程序效率的影响,并对Closed表进行了若干优化,提高了搜索效率,取得了较好的效果。The eight puzzle problem is common in the artificial intelligence domain. The article resolves this problem through the classical A ^＊ algorithm. Firstly, the paper introduces the eight puzzle problem, and then describes the A ^＊ algorithm. Focus on the eight puzzles problem, the article gives the condition when the path does not exist and proves it. The paper defines a flexible evaluation function, analyzes its influence to the function efficiency and optimized Closed table. All those enhances the search efficiency and obtaines the anticipated effect.

关 键 词：八数码问题 A^＊算法 逆序数 估价函数 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]