A* 八数码
一、open表用vector加
建立堆
make_heap(nums.begin(), nums.end());
//或
make_heap(nums.begin(), nums.end(), compare);//compare是自己写的函数，最大堆用less，最小堆用greater添加元素push_heap()用法是，vector先push_back()，后push_heap()
nums.push_back(a);
push_heap(nums.begin(), nums.end(), compare);pop_heap()用法是，先pop_heap()，vector后pop_back()。pop_heap会把最前面的放到最后面
pop_heap(nums.begin(), nums.end(), compare);
nums.pop_back();二、closed表一开始选择数据结构set，但是因为是struct，总是complie error，主要是需要重载<运算符，而且是在结构体外重载...后来感觉没必要就用的list
三、中间出现问题的一个地方是，检查子节点是不是在closed表中并依据情况更新时候，用了前面说得push_heap()，但实际上不应该用的。。否则出不来结果
四、g（x）用的步数，h（x）用的到目标结点的距离之和
伪代码：
算起点的估价值，将起点放入OPEN表。
while(OPEN!=NULL){
从OPEN表中取估价值f最小的节点n;
if(n节点==目标节点)
{break;}
for(当前节点n 的每个子节点X){
算X的估价值;
if(X in OPEN) {
if( X的估价值小于OPEN表的估价值 )
{把n设置为X的父亲;
更新OPEN表中的估价值; }}
if(X inCLOSE) {
if( X的估价值小于CLOSE表的估价值 ){
把n设置为X的父亲;
更新CLOSE表中的估价值;
把X节点放入OPEN }}
if(X not inboth){
把n设置为X的父亲;
求X的估价值;
并将X插入OPEN表中; }}
将n节点插入CLOSE表中;
按照估价值将OPEN表中的节点排序; }
代码：
#include
#include
#include
#include
#include
#include
#include
using namespace std;
struct item{int state=0;int g=0;int h=0;int empty;int pre=-1;
};
bool operator==(const item& a,const item& b){return b.state==a.state;}
bool compare(item a,item b){return a.g+a.h>b.g+b.h;
}
vector- open;
list
- closed;void path(item a){cout<<"--------------"<
r;r.push(a.state);a.state=a.pre;list- ::iterator re2;while(a.state!=-1){r.push(a.state);//cout<
pre;}int temp,b[9],count=0;while(!r.empty()){count++;cout<<"step"<=0;--i){b[i]=temp%10;temp/=10;}for(int i=0;i<9;++i){cout<=0;--i){b=a%10;a=a/10;if(b!=0)count+=abs(b-i-1);}return count;
}
int getNixuNum(int state) //求节点的逆序对数,不可与结果同为奇数或者同为偶数
{ int sum=0; int result[9]; memset(result,0,sizeof(result)); char buf[10]; itoa(state,buf,10); int k=0; while(buf[k]!='\0'){ result[9-k-1]=buf[k]-'0'; k++; } for(int i=0;i<9;i++ ){ for(int j=i+1;j<9;j++ ){ if(result[i]&&result[j]&&result[i]>result[j] ){ sum++; } } } return sum;
}
void insert(item a){vector- ::iterator re1=find(open.begin(), open.end(),a); //查找a在open表中 if (re1!=open.end()&&re1->g+re1->h>a.g+a.h){re1->g=a.g;re1->h=a.h;re1->pre=a.pre;// cout<<"open表中替换"<
::iterator re2=find(closed.begin(),closed.end(),a);if(re2!=closed.end()&&re2->g+re2->h>a.g+a.h){closed.erase(re2);closed.push_back(a);// cout<<"closed表中替换"<=0;--i){x[i]=now%10;now/=10;}item next;next.pre=open[0].state;next.g=open[0].g+1;if(em%3!=0){//向左移 next.state=0; for(int i=0;i<9;++i){if(i==em-1)next.state=next.state*10+x[em];else if(i==em)next.state=next.state*10+x[em-1];elsenext.state=next.state*10+x[i];}// cout<<"左移结点值"<=3){//向上移next.state=0; for(int i=0;i<9;++i){if(i==em-3)next.state=next.state*10+x[em];else if(i==em)next.state=next.state*10+x[em-3];elsenext.state=next.state*10+x[i];}//cout<<"上移结点值"<>in;if(in==0)start.empty=i;start.state=start.state*10+in;}if(getNixuNum(start.state)%2!=0)cout<<"无解";else{start.h=calculateH(start.state);open.push_back(start);Astar();}
// cout<=0;--i){
// a.h=i;
// a.g=0;
// a.state=i;
// open.push_back(a);
// }
// for(int i = 0; i <9; i++)
// cout<
本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！