A星算法简单机器⼈积⽊动作序列问题
来⾃⼈⼯智能的实验题实现（block，简单积⽊机器⼈问题，给出若⼲积⽊状态以及⽬标状态，为机器⼈给出动作序列）
（关于A星算法⽹上有⼀个经典的寻路例⼦的中⽂翻译，有兴趣可以先和
现有积⽊若⼲，积⽊可以放在桌⼦上，也可以放在另⼀块积⽊上⾯。
状态表⽰如下：
clear（x）：积⽊x上⾯没有任何积⽊。
on（x,y）：积⽊x在积⽊y上⾯。
ontable（x）：积⽊x在桌⼦上。
操作表⽰如下：
move（x,y）：把积⽊x放到积⽊y上⾯。前提是积⽊x和积⽊y上⾯都没有其他积⽊。
moveToTable（x）：把积⽊x放到桌⼦上，前提是积⽊x上⾯⽆其他积⽊，且积⽊x不在桌⼦上（即x在其他积⽊上⾯）。
举例如下：
初始状态序列：clear（a）, on（a,b）, on（b,c）, ontable（c）, clear（d）, ontable（d），
⽬标状态序列：clear（a）, on（a,c）, ontable（c）, clear（b）, on（d,b）, ontable（b），
操作⽅案序列：moveToTable（a）, moveToTable（b）, move（a,c）, move（d,b）。
请使⽤A*算法来规划此问题。INPUT为初始状态序列和⽬标状态序列，OUTPUT为操作⽅案序列。
对于A星算法，其实就是⽐我们⼀般的BFS，DFS通过评价函数来约束，使得我们的搜索更快的接近最优解
其核⼼思想就是通过定义评价函数f=g+h(其中g其实可以当作是到达当前状态已经⾛过的步数或者说是消耗代价，h则是我们定义的⼀个由当前状态到达⽬标状态的估值函数，⼀般该值⼩于真实值，所以f其实就是整个过程的估值）
其次就是我们要维护的两个表：openlist和closelist
openlist其实就是我们从开始状态搜索后续状态是衍⽣的后继状态加⼊到其中，然后每次从中取出评价函数值最⼩的状态进⾏后续搜索，我⽐较倾向于⽤存有状态的优先队列来作为我们的openlist，因为我们可以定义优先队列按评价函数值⼤⼩来排序，这样⼀来每次取得的状态点其实就是评价函数值最⼩的点。⾄于closelist为了后⾯查重需要所以可以⽤vector或者list
直接附上我的代码，⼀⼝⽓写下来的，没有考虑空间时间的问题，考虑空间问题其实可以⽤⼀维数组存的。
⽐如clear(a),on(a,d),on(d,b),ontable(b),ontable(c)就可以⽤
[ 3,-1,-1,1]
[a][b][c][d]
按a,b,c,d索引为0，1，2，3来设计，a下⾯是d，指向d的索引3，b下⾯没有，指向-1，c下⾯也没有，指向-1，d下⾯是b，指向b的索引1
我这⾥就⽤⼆维数组存，a下⾯有d，则mat[0][3]=1;d下⾯有b，则mat[3][1]=1;b在桌⾯上，则mat[1][1]=1;c在桌⾯上，则mat[2]
[2]=1；其他为0
所以如果⼀个⽊块a不在桌⾯上并且其上是clear的，则mat[0~n][0]=0
#include <iostream>
#include <cmath>
#include <string>
#include <queue>
#include <list>
#include <cstring>
using namespace std;
const int num =20; //预定义下规模
int mat_begin[num][num]; //初始状态矩阵
int mat_end[num][num];  //⽬标状态矩阵
int index1,index2; //状态的语句数，如on(a,b),ontable(b),ontable(c) 为3个
int row = -1;//可能积⽊个数没有num那么多，可以对矩阵操作时候节省时间，row=col
struct operator_string
struct operator_string
{
string str_operator; //moveToTable 或者 move
string str_A; //第⼀个操作对象
string str_B; //第⼆个操作对象
};
struct status
{
int g; //==搜索了第⼏步
int h;//估值，与⽬标的估计距离
int mat[num][num];//每⼀个状态下的矩阵
list<operator_string> array_operator;//⽤来存储操作序列
//可移动的对象
string not_ontable; //不在桌⾯上并且上⾯没有其他积⽊的⽊块
string ontable; //在桌⾯上的⽊块并且上⾯没有其他积⽊的⽊块
string sum;
friend bool operator< (status n1, status n2){
return n1.g+n1.h > n2.g+n2.h;  //">"为从⼩到⼤排列 f=g+h
}
};
list<status> li;
string deal_space(string s)  //预处理⼀下客户输⼊的字符串，因为可能出现多余空格的问题{
string temp = s;
int size = temp.size();
for( int i = 0; i < size; i ++ ){
if( temp[i] ==' '){
for ( int j = i; j < size; j ++ ) temp[j] = temp[j+1];
i--;
size--;
}
if( temp[i] == ',' && temp[i-1] == ')'){        //将‘）’后⾯的逗号处理掉
for ( int j = i; j < size; j ++ ) temp[j] = temp[j+1];
i--;
size--;
}
}
return temp;
}
void show_mat(int mat[num][num])//显⽰矩阵
{
for(int i=0;i<row;i++){
for(int j=0;j<row;j++){
cout<<mat[i][j]<<" ";
}
cout<<endl;
}
}
bool same_mat(int a[num][num],int b[num][num])//矩阵是否相同
{
int ans = 0;
for(int i=0;i<row;i++){
for(int j=0;j<row;j++){
cstring转为intif(a[i][j]!=b[i][j]){
ans = 1;
break;
}
}
}
if(ans == 0) return true;
else
return false;
return false;
}
void copy_mat(int a[num][num],int b[num][num])//拷贝矩阵
{
for( int i = 0 ; i < num ; i++ )
for ( int j = 0; j < num; j ++ ) a[i][j]=b[i][j];
}
void string_to_mat(string s,int & index,int & row,int  mat[num][num])//将字符串转为状态矩阵
{
int size = s.size();
int flag1=0,flag2=0;//flag1对应着左括号，flag2对应逗号
string temp1="",temp2="",temp3="";  //temp代表on/ontable/clear, temp2代表第⼀个操作对象，temp3代表第⼆个对象for( int i = 0; i < size; i++ ){
if( flag1 == 0 && s[i] != '(' ) temp1 += s[i];
else if( flag1 == 0 && s[i] == '(' ) flag1 = 1;
else if( flag2 == 0 && s[i] != ',' && s[i] != ')' ) temp2 += s[i];
else if( s[i] == ',' ) flag2 = 1;
else if( flag2 == 1 && s[i] != ')' ) temp3 += s[i];
else if( s[i] == ')' ){    //⼀旦遇到有括号，就开始操作
flag1 = 0,flag2 = 0;
if( temp1 == "on" ){
row = max(row,temp2[0]-'a');
row = max(row,temp3[0]-'a');//row 就是为了总共有a、b、c、d、e...多少个
mat[ temp2[0] - 'a' ][ temp3[0] - 'a' ] = 1;//设为1
}
else if( temp1 == "ontable" ){
row = max(row,temp2[0]-'a');
mat[ temp2[0] -'a' ][ temp2[0] - 'a' ] = 1;//设为1
}
else{
row = max(row,temp2[0]-'a');//clear，不⽤操作
}
temp1 = "",temp2 = "",temp3 = "";
index++;
}
else
continue;
}
row++;
}
int count_h(int a[num][num],int b[num][num]) //计算h的估值⽅法是从底部⽹上相同，相同加⼀
{
int visit[num][num];
memset(visit,0,sizeof(visit));
int ans  = 0;
for(int i = 0; i < row; i++ ){
if(a[i][i]==b[i][i]&&a[i][i]==1&&visit[i][i]==0){
visit[i][i]=1;
ans++;
int k = i;
int flag=1;
while(flag){//如果flag=0，证明该⽊块往上已经不到⽊块了，终⽌循环
flag=0;
int temp;
for(int j=0;j<row;j++){
if(a[j][k]==b[j][k]&&a[j][k]==1&&visit[j][k]==0){//该列
flag=1;
visit[j][k]=1;
ans++;
temp = j;
}
}
k=temp;
k=temp;
}
}
}
return row - ans;
}
void strategy(status & current)//计算可以做的下⼀步操作，将对象加到not_ontable 和ontable两个字符串中，以便后⾯取得下⼀步操作策略{
for( int j = 0 ; j < row ; j ++ ){
int ans1=0,ans2=0;
for( int i = 0 ; i < row ; i ++ ){
if( current.mat[i][j] == 1 ){
if( i != j) ans2++;
ans1++;
}
}
if( ans1 == 0 ) _ontable += ( j + 'a');
else
if( ans2 == 0) able += ( j + 'a');
}
current.sum = _ontable + able;
}
void copy_and_change(status & to,status from,int index)//从上个状态中继承可以继承的数据
{
to.g=from.g+1;
copy_mat(to.mat,from.mat);
list<operator_string>::iterator iter;
for(iter = from.array_operator.begin();iter!=from.d();iter++){
operator_string temp;
temp.str_operator=(*iter).str_operator;
temp.str_A=(*iter).str_A;
temp.str_B=(*iter).str_B;
to.array_operator.push_back(temp);
}
for (int j = 0 ; j < num ; j++ )  { //将对应的⾏置0
if( from.mat[index][j] == 1 ){
to.mat[index][j] = 0;
}
}
}
void add_move_operator(status & to,int index1,int index2)
{
operator_string temp_string;
temp_string.str_operator="move";
temp_string.str_A+=( index1 + 'a' );
temp_string.str_B+=( index2 + 'a' );
to.array_operator.push_back(temp_string);
to.mat[index1][index2] = 1;
}
status not_ontable_to_table( status current, int index )//将不在桌⾯的移到桌⾯
{
status temp;
int char_index = _ontable[index] - 'a';
copy_and_change(temp,current,char_index);
temp.mat[char_index][char_index] = 1;
operator_string temp_string;
temp_string.str_operator="moveToTable";
temp_string.str_A+=( char_index + 'a' );
temp.array_operator.push_back(temp_string);
temp.h = count_h(temp.mat,mat_end);
strategy(temp);
return temp;
}
}
status move_between(status current,int index1,int index2)
{
status temp;
int char_index1 = current.sum[index1] - 'a';
int char_index2 = current.sum[index2] - 'a';
copy_and_change(temp,current,char_index1);
add_move_operator(temp,char_index1,char_index2);
temp.h = count_h(temp.mat,mat_end);
strategy(temp);
return temp;
}
bool have_same(status a)//在li链表中是否相同的状态矩阵，有的话就是搜索过的
{
list<status>::iterator iter;
int ans = 0;
for(iter = li.begin();iter!=li.end();iter++){
if(same_mat((*iter).mat,a.mat)){
ans=1;break;
}
}
if(ans == 1) return true;
else
return false;
}
int main()
{
string s1,s2;
cout<<"请输⼊初始串:"<<endl;
getline(cin,s1);
cout<<"请输⼊⽬标串:"<<endl;
getline(cin,s2);
cout<<"=============================================block begin==============================================="<<endl;    string begin = deal_space(s1);
string end = deal_space(s2);
string_to_mat(begin,index1,row,mat_begin);
row=0;
string_to_mat(end,index2,row,mat_end);
cout<<"原始状态矩阵："<<endl;
show_mat(mat_begin);
cout<<"⽬标状态矩阵"<<endl;
show_mat(mat_end);
priority_queue <status> que;    //优先队列存储结点
status start;
start.g=0;
start.h=count_h(mat_begin,mat_end);
copy_mat(start.mat,mat_begin);
strategy(start);
que.push(start);
li.push_back(start);
status p;
status pp; //⽤来记录最后的结果
int ans = 0;
int count=0;//记录访问过多少个⾛步
while( que.size() )
{
if(ans == 1)
break;
p();
que.pop();
int size1 = p.not_ontable.size();
for(int i=0;i<size1;i++)//从不再桌⾯的移到桌⾯上
{
count++;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。