/*人工知能の授業で習った知識を総動員して書いた、3x3x3 のルービックキューブを解くCプログラム。
A*(エースター)探索、双方向探索、ヒューリスティック関数、ハッシュ関数の合わせ技。
人間がやるようなパターンをなぞる方法じゃなくて、常に最短手順を見つけることを保証する。*/
/*続く*/
A*(エースター)探索、双方向探索、ヒューリスティック関数、ハッシュ関数の合わせ技。
人間がやるようなパターンをなぞる方法じゃなくて、常に最短手順を見つけることを保証する。*/
#include <math.h> #include <stdio.h> #include <stdlib.h> #define D 3 /*3x3x3のルービックキューブ。ここを4にしても4x4x4が解けるわけじゃない*/ struct node{ char surface[6][D][D]; /*ルービックキューブ各面の情報*/ unsigned int cost; /*今の状態に何手で来たかを各ノードに記憶*/ unsigned int heuristic; /*このノードのヒューリスティック値*/ unsigned int expectation; /*heuristic+cost*/ long double hash; /*前に展開したノードと同じノードを展開しないためにハッシュ値を使う*/ struct node *next[15]; /*ここから展開される子ノードへのポインタ*/ struct node *reverse; /*親ノードへのポインタ。最後に解へのパスをたどるめに使う*/ struct node *nextleaf; /*現在のリーフをリスト構造でつなぐ。次のリーフへのポインタ*/ struct node *revleaf; /*前のリーフへのポインタ*/ struct node *nodelist; /*ハッシュ値を比べるために,生成したノードをすべてリニアにつなぐ。次のノードへのポインタ*/ struct node *revnode; /*一つ前のノードへのポインタ*/ char ope; /*親ノードから,どんな状態変化をされて来たのかを記憶*/ char opecolor; /*親ノードからこの状態に来るときに,どの面を回したのか記憶*/ }root, goal, *minG, leaflist, endleaf, nodeend; unsigned int min; /*heuristic+costの最小値*/ void start(void); /*rootの初期化など*/ void develop(struct node *cube); /*ノードを展開する*/ void allocate(struct node *cube); /*ノードを展開するための,メモリを確保*/ void heuristic(struct node *cube); /*ヒューリスティック関数*/ void operate(struct node *cube); /*生成したノードにの状態遷移を行う*/ void Rrot(struct node *next, struct node *original, char s); /*一面を右に90度回転*/ void Lrot(struct node *next, struct node *original, char s); /*一面を左に90度回転*/ void rot(struct node *next, struct node *original, char s); /*一面を180度回転*/ void search(void); /*heuristic+costが最小のリーフを探す*/ void output(void); /*解へのパスをたどって解法を表示*/ void exception(void); /*rootを展開するときだけちょっと特別*/ int main(void) { unsigned int depth=0; start(); /*いろんなものを初期化*/ develop(&root); /*rootを展開*/ exception(); /*rootを展開その2*/ search(); /*展開すべきリーフを探す*/ while(minG->heuristic){ /*ゴール状態でない限りループ*/ if(minG->cost>depth) printf("%dn",++depth); /*現在展開した一番深いノードの深さを表示*/ develop(minG); /*リーフを展開*/ search(); /*次に展開するリーフを探す*/ } output(); /*解法を表示*/ return 0; } void start(void) { char i,j,k; for(i=0;i<6;i++)
next[i]); /*展開した各ノードのヒューリスティック値を計算*/ } void allocate(struct node *cube) { char i,j,k,l; struct node *nextcube; nextcube=(struct node *)malloc(sizeof(struct node)*15); /*メモリ確保*/ if(!nextcube){ printf("メモリ割り当てエラーan"); exit(1); } nodeend.revnode->nodelist=&nextcube[0]; /*ノードリストにつなげる*/ cube->revleaf->nextleaf=&nextcube[0]; /*リーフリストにつなげる*/ nextcube[0].revleaf=cube->revleaf; for(i=0;i<14;i++){ /*生成したノードをリストにつなげて,親と同じ状態をコピー*/
next[i]=&nextcube[i]; nextcube[i].reverse=cube; nextcube[i].nodelist=&nextcube[i+1]; for(k=0;k<6;k++)
surface[k][j][l]; nextcube[i].cost=1+cube->cost; nextcube[i].nextleaf=&nextcube[i+1]; nextcube[i+1].revleaf=&nextcube[i]; } cube->next[14]=&nextcube[14]; nextcube[14].reverse=cube; nextcube[14].nodelist=&nodeend; nodeend.revnode=&nextcube[14]; for(k=0;k<6;k++)
surface[k][j][l]; nextcube[14].cost=cube->cost+1; nextcube[14].nextleaf=cube->nextleaf; cube->nextleaf->revleaf=&nextcube[14]; }
/*続く*/
※コメント投稿者のブログIDはブログ作成者のみに通知されます