A*アルゴリズムの簡単な実現(八数コード問題)
9088 ワード
第一部:A*アルゴリズムの概要
プログラム環境:
実行環境:Windows xp
使用ツール:Vc++6.0
イニシアチブ検索の概要:
啓発的検索とは,ステータス空間における検索が各検索の位置を評価し,最適な位置を得て,この位置からターゲットまで検索することである.これにより,大量の無意味な探索経路を省略でき,効率が向上する.啓発的検索では,位置の評価が重要である.異なる評価を採用すると、異なる効果が得られます.
ノードに到達する散逸g(n)とそのノードからターゲットノードへの消費h(n)を組み合わせてノードを評価する:f(n)=g(n)+h(n)
A*アルゴリズムの概要:
A*アルゴリズムは,評価関数にいくつかの制限を加えた啓発的探索アルゴリズムである.
検索プロセスは次のように記述されます.
(1)初期ノードS 0をOpenテーブルに入れ、f(S 0)=g(S 0)+h(S 0);
(2)Openテーブルが空の場合、問題は解けず、失敗して終了する.
(3)Openテーブルの最初のノードを取り出してClosedテーブルに入れ、そのノードをnとする.
(4)ノードnがターゲットノードであるかどうかを考察する.もし、問題の解が見つかったら、成功して退出します.
(5)ノードnが拡張できない場合は(2)ステップに進む.
(6)拡張ノードnは、サブノードni(i=1,2,…)を生成し、各サブノードの評価値f(ni)(i=1,2,…)を計算し、各サブノードに親ノードへのポインタを設定し、これらのサブノードをOpenテーブルに入れる.
(7)各ノードの評価関数値に基づいて、Openテーブルのすべてのノードを小さい順から大きい順に並べ替える.
(8)ステップ(2)に進みます.
第2部:A*アルゴリズムの簡単な実現(八数コード問題)
図解:
コード:
コードに問題があるか、より深刻なエラーがある場合は、ご教示ください.
実行結果:
最終変更日:2012-12-31
プログラム環境:
実行環境:Windows xp
使用ツール:Vc++6.0
イニシアチブ検索の概要:
啓発的検索とは,ステータス空間における検索が各検索の位置を評価し,最適な位置を得て,この位置からターゲットまで検索することである.これにより,大量の無意味な探索経路を省略でき,効率が向上する.啓発的検索では,位置の評価が重要である.異なる評価を採用すると、異なる効果が得られます.
ノードに到達する散逸g(n)とそのノードからターゲットノードへの消費h(n)を組み合わせてノードを評価する:f(n)=g(n)+h(n)
A*アルゴリズムの概要:
A*アルゴリズムは,評価関数にいくつかの制限を加えた啓発的探索アルゴリズムである.
検索プロセスは次のように記述されます.
(1)初期ノードS 0をOpenテーブルに入れ、f(S 0)=g(S 0)+h(S 0);
(2)Openテーブルが空の場合、問題は解けず、失敗して終了する.
(3)Openテーブルの最初のノードを取り出してClosedテーブルに入れ、そのノードをnとする.
(4)ノードnがターゲットノードであるかどうかを考察する.もし、問題の解が見つかったら、成功して退出します.
(5)ノードnが拡張できない場合は(2)ステップに進む.
(6)拡張ノードnは、サブノードni(i=1,2,…)を生成し、各サブノードの評価値f(ni)(i=1,2,…)を計算し、各サブノードに親ノードへのポインタを設定し、これらのサブノードをOpenテーブルに入れる.
(7)各ノードの評価関数値に基づいて、Openテーブルのすべてのノードを小さい順から大きい順に並べ替える.
(8)ステップ(2)に進みます.
第2部:A*アルゴリズムの簡単な実現(八数コード問題)
図解:
コード:
コードに問題があるか、より深刻なエラーがある場合は、ご教示ください.
// （ ）、 ？？？
/*==============================================================================
？
OPEN
， （ 9！ ）， -_-！（ ）
==============================================================================*/
#include
#include
#include
#define MAX_NODESIZE 362880 //9 9!=362880
typedef struct node{ //
int a[3][3];//
//
int i_0;
int j_0;
//
int d; //
int w; //
int f; //
struct node *father; //
}node,*p_node;
typedef struct list //
{
p_node a[MAX_NODESIZE];
long length;
}list,*p_list;
//static int s0[3][3]={8,2,3,1,0,4,7,6,5}; //
static int s0[3][3]={2,8,3,1,0,4,7,6,5}; //
/*
2 8 3
1 0 4
7 6 5
*/
static int sg[3][3]={1,2,3,8,0,4,7,6,5}; //
/*
1 2 3
8 0 4
7 6 5
*/
p_node s_0=(p_node) malloc(sizeof(node)); //
p_node s_g=(p_node) malloc(sizeof(node)); //
p_list OPEN =(p_list) malloc (sizeof(list)); //OPEN
p_list CLOSED=(p_list) malloc (sizeof(list)); //CLOSE
int w(p_node s); //
int f(p_node s); //
void init_node(); //
void out_node(p_node s); //
void list_reverse(p_node &p); //
void out_list(p_list &l); // OPEN
bool search_list(p_list &l,p_node s); // ， true
void sort_list(p_list &l); // OPEN （ f ）
void add_list(p_list &l,p_node s); // OPEN CLOSE
void copy_node(p_node s1,p_node &s2); // （ s2 s1）
void delete_list(p_list &l); // OPEN CLOSE
bool is_equal(p_node s1,p_node s2); //
bool up_mov(p_node &s); //
bool down_mov(p_node &s); //
bool left_mov(p_node &s); //
bool right_mov(p_node &s); //
void move(p_node s); // （ ）
int main()
{
init_node();
printf("
：
");
printf("=========================================================
");
while(OPEN->length!=0 && CLOSED->length<=1000) // 1000
{
p_node n=OPEN->a[0]; //--------------- Open Closed ， n
delete_list(OPEN);
if(is_equal(n,s_g)) // n 。 ， ， ； if(w(n)==0){...}
{
list_reverse(n);
list_reverse(n);
list_reverse(n);
while(n)
{
printf(" %d ：
",n->d+1);
out_node(n);
n=n->father;
}
break;
}
add_list(CLOSED,n);
move(n);// n
sort_list(OPEN);
// out_list(OPEN);
}
if(OPEN->length==0 || CLOSED->length>1000)
{
printf("
！
");
}
return 0;
}
int f(p_node s) //
{
return (s->d+s->w);
}
void out_node(p_node s) //
{
printf("-------------------");
printf(" x=%d,y=%d
",s->i_0,s->j_0);
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
printf("%5d",s->a[i][j]);
}
printf("
");
}
printf("-------------------");
printf(" d=%d,w=%d; f=%d
",s->d,s->w,s->f);
}
void out_list(p_list &l) // OPEN
{
printf("****************************************************************
");
for(int i=0;ilength;i++)
{
out_node(l->a[i]);
}
printf("****************************************************************
");
}
int w(p_node s) //
{
int w=0;
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
if (s->a[i][j]!=sg[i][j])
{
w++;
}
}
}
if (s->a[1][1]==sg[1][1])
{
w+=1;
}
return w-1;
}
bool left_mov(p_node &s) //
{
int x=s->i_0,y=s->j_0;
if (y==0)
{
return false;
}
int t;
t=s->a[x][y];
s->a[x][y]=s->a[x][y-1];
s->a[x][y-1]=t;
--s->j_0;
return true;
}
bool right_mov(p_node &s) //
{
int x=s->i_0,y=s->j_0;
if (y==2)
{
return false;
}
int t;
t=s->a[x][y];
s->a[x][y]=s->a[x][y+1];
s->a[x][y+1]=t;
++s->j_0;
return true;
}
bool up_mov(p_node &s) //
{
int x=s->i_0,y=s->j_0;
if (x==0)
{
return false;
}
int t;
t=s->a[x][y];
s->a[x][y]=s->a[x-1][y];
s->a[x-1][y]=t;
--s->i_0;
return true;
}
bool down_mov(p_node &s) //
{
int x=s->i_0,y=s->j_0;
if (x==2)
{
return false;
}
int t;
t=s->a[x][y];
s->a[x][y]=s->a[x+1][y];
s->a[x+1][y]=t;
++s->i_0;
return true;
}
bool is_equal(p_node s1,p_node s2) //
{
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
if (s1->a[i][j]!=s2->a[i][j])
{
return false;
}
}
}
return true;
}
void copy_node(p_node s1,p_node &s2) // （ s2 s1）
{
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
s1->a[i][j]=s2->a[i][j];
}
}
s1->i_0=s2->i_0;
s1->j_0=s2->j_0;
s1->d=s2->d;
s1->w=s2->w;
s1->f=s2->f;
s1->father=s2->father;
}
void add_list(p_list &l,p_node s) // OPEN CLOSE
{
l->a[l->length++]=s;
}
void delete_list(p_list &l) // OPEN CLOSE
{
for (int i=0;ilength;i++)
{
l->a[i]=l->a[i+1];
}
l->length--;
}
bool search_list(p_list &l,p_node s)// ， true
{
for(int i=0;ilength;i++)
{
if(is_equal(l->a[i],s))
return true;
}
return false;
}
void move(p_node s)// （ ）
{
p_node p1=(p_node) malloc(sizeof(node));
p_node p2=(p_node) malloc(sizeof(node));
p_node p3=(p_node) malloc(sizeof(node));
p_node p4=(p_node) malloc(sizeof(node));
copy_node(p1,s);
copy_node(p2,s);
copy_node(p3,s);
copy_node(p4,s);
p1->father=s;
p2->father=s;
p3->father=s;
p4->father=s;
// CLOSED ， OPEN
if(left_mov(p1) && !is_equal(p1,p1->father) && !search_list(CLOSED,p1) && !search_list(OPEN,p1))
{
add_list(OPEN,p1);
p1->d+=1;
p1->w=w(p1);
p1->f=f(p1);
}
else
{
free(p1);
}
if(right_mov(p2) && !is_equal(p2,p2->father) && !search_list(CLOSED,p2) && !search_list(OPEN,p2))
{
add_list(OPEN,p2);
p2->d+=1;
p2->w=w(p2);
p2->f=f(p2);
}
else
{
free(p2);
}
if(up_mov(p3) && !is_equal(p3,p3->father) && !search_list(CLOSED,p3) && !search_list(OPEN,p3))
{
add_list(OPEN,p3);
p3->d+=1;
p3->w=w(p3);
p3->f=f(p3);
}
else
{
free(p3);
}
if(down_mov(p4) && !is_equal(p4,p4->father) && !search_list(CLOSED,p4) && !search_list(OPEN,p4))
{
add_list(OPEN,p4);
p4->d+=1;
p4->w=w(p4);
p4->f=f(p4);
}
else
{
free(p4);
}
}
void sort_list(p_list &l) // OPEN ， （ f ）
{
p_node t=(p_node) malloc (sizeof(node));
for(int i=1;ilength;i++)
{
if(l->a[i]->f < l->a[i-1]->f)
{
copy_node(t,l->a[i]);
for(int j=i;j>0;j--)
{
copy_node(l->a[j],l->a[j-1]);
}
copy_node(l->a[j],t);
}
}
}
void list_reverse(p_node &p) //
{
p_node p_pre,p_suc;
p_pre=NULL;
p_suc=p->father;
while(p)
{
p->father=p_pre;
p_pre=p;
if(p_suc == NULL)
{
break;
}
p=p_suc;
p_suc=p_suc->father;
}
}
void init_node() //
{
//---------------------------------------
for (int i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
s_0->a[i][j]=s0[i][j];
if(s_0->a[i][j] == 0)
{
s_0->i_0=i;
s_0->j_0=j;
}
}
}
s_0->d=0;
s_0->father=NULL;
s_0->w=w(s_0);
s_0->f=f(s_0);
//---------------------------------------
for (i=0;i<3;i++)
{
for (int j=0;j<3;j++)
{
s_g->a[i][j]=sg[i][j];
if(s_0->a[i][j] == 0)
{
s_g->i_0=i;
s_g->j_0=j;
}
}
}
s_g->d=0;
s_g->w=w(s_g);
s_g->f=f(s_g);
OPEN->length=0;
CLOSED->length=0;
add_list(OPEN,s_0); // OPEN
printf(" ：
");
out_node(s_0);
printf(" ：
");
out_node(s_g);
}
実行結果:
最終変更日:2012-12-31