基于A_算法的八数码问题的优化实现.pdf

计 算 机 与 现 代 化 　2008年第 1期 J ISUANJ I YU X IANDA IHUA 总第 149期 文章编号 :(2008) 0 1002903 基于 A 算法的八数码问题的优化实现 卜奎昊 ,宋 　杰 ,李国斌 (安徽大学计算智能与信号处理教育部重点实验室 ,安徽 合肥 230039) 摘要 : 用人工智能领域中经典的 A 算法解决了人工智能中常见的八数码问题 。本文首先介绍了八数码问题 ,然后对 A 算法进行了解释 。针对八数码问题给出并证明了路径不存在时的条件 ,并事先作了判定 。定义了灵活的估价函数 , 分析了估价函数对程序效率的影响 ,并对 Clo sed表进行了若干优化 ,提高了有哪些信誉好的足球投注网站效率 ,取得了较好的效果 。 关键词 :八数码问题 ; A 算法 ; 逆序数 ; 估价函数 中图分类号 : TP311　　　　文献标识码 : A O ptim iza tion of E ight Puzz le Prob lem Ba sed on A A lgor ithm BU Ku ihao, SON G J ie, L I Guob in ( The Key L aboratory of Intelligence Compu ting and Signal Proce ssing, M in istry of Education, A nhu i U n iversity, H efei 230039, Ch ina) A b stract: The eigh t p uzzle p rob lem is common in the artificial in telligence dom ain. The article re so lve s th is p rob lem through the classical A algorithm. F irstly, the p ap er in troduce s the eigh t p uzzle p rob lem , and then de scribe s the A algorithm. Focu s on the eigh t puzzle s p rob lem , the article give s the condition when the p ath doe s not exist and p rove s it. The p ap er define s a flexib le eval uation function, analyze s its influence to the function efficiency and op tim ized Clo sed tab le. A ll tho se enhance s the search effi ciency and obtaine s the anticip ated effect. Key word s: eigh t puzzle p rob lem ; A algorithm ; p erm utation num ber; evaluation function ( )