A星算法求解八数码技术报告

《A星算法求解八数码技术报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、A*算法求解八数码问题lopen表、closed表数据结构的选择：1)把s放入open表，记f=h，令closed为空表。2)重复下列过程，直到找到目标节点为止。若open表为空表，则宣告失败。3)选取open表中未设置过的具有最小f值的节点为最佳节点bestnode，并把它放入closed表。4)若bestnode为一目标节点，则成功求得一解。5)若bestnode不是目标节点，则扩展之，产生后继节点succssor。6)对每个succssor进行下列过称：a)对每个succssor返回bestnode的指针。b)计算g（suc）=g（bes）+k（bes，suc

2、）。c)如果succssoreopen，称此节点为old，并填到bestnode的后继节点表中。d)比较新旧路劲代价。如果g（suc）

3、)计算f值j)Goloopl节点的数据结构：staticinttarget[9]={1,2,3,8,0,4,7,6,5};全局静态变量，表示目标状态classeight_num{private:intnum[9];定义八数码的初始状态intnot_in_position_num;定义不在正确位置八数码的个数intdeapth;定义了搜索的深度inteva_function;评价函数的值，每次选取最小的进行扩展public:eight_num*parent;指向节点的父节点eight_num*leaf_next;指向open表的下一个节点eight_num*leaf_

4、pre;指向open表的前一个节点初始状态的构造函数eight_num(intinit_num[9]);eight_num(intnum1,intnum2,intnum3,intnum4,intnum5,intnum6,intnum7,intnum8,intnum9){}eight_num(void){}计算启发函数g(n)的值voideight_num::cul_para(void){}显示当前节点的状态voideight_num::show(){}复制当前节点状态到一个另数组中voideight_num::get_numbers_to(intother_num[

5、9]){}设置当前节点状态(欲设置的状态记录的other数组中)voideight_num::set_num(intother_num[9]){}eight_num&eight_num::operator=(eight_num&another_8num){}eight_num&eight_num::operator=(intother_num[9]){}inteight_num::operator==(eight_num&another_8num){}inteight_num::operator==(intother_num[9]){}空格向上移intmove_up

6、(intnum[9]){}空格向下移intmove_down(intnum[9]){}空格向左移intmove_left(intnum[9]){}空格向右移intmove_right(intnum[9]){}判断可否解出inticansolve(intnum[9],inttarget[9]){}判断有无重复intexisted(intnum[9],eight_num*where){}寻找估价函数最小的叶子节点eight_num*find_OK_leaf(eight_num*start){}}lA*算法求解框图：把m放入open表，记f=h开始Open=nil？选取o

7、pen表上未设置过的具有最小f值的节点bestnode，放入closed表是失败Bestnode是目标节点？成功是扩展bestnode，产生其后继节点successor否否建立从successor返回bestnode的指针计算g（suc）=g（bes）+k（bes，suc）Suc属于open？Suc属于closed？Suc=old，把它添加到bestnode的后继节点表中g(suc)