8パズルの子ノードの作成

Question

###実現したいこと
Step1: 出発のノードnに対し(n null c) をOpenリストに追加する。ただし初めなのでc = h(n) = f(n)
Step2: Openリストからcが最⼩の要素(n p c) を⼀つ選択。nがゴールであれば成功として終了。Openリストが空集合なら失敗として終了。
Step3: ノードnを展開し、⼦ノードの集合を作る。nをCLOSEDリストに追加する。
Step4: ⼦ノードの集合からCLOSEDリストに含まれないノードn’ に対して、(n’ n c’ )をOpenリストに追加する(なお、c’= f(n’) = h(n’) + g(n) + c(n n’),c(n n’) はnからn’へのコストである) である。このときすでに(n’ m c’’ )がOpenリストに⼊っており、c’<c’’ なら新しいものに置き換え、そうでなければOpenリストには追加しない。さらに、CLOSEDリストに含まれるn’ に対して、そのときに探索した(n’ m c’’ ) について、c’ < c’’ならn’をCLOSEDリストから削除し、(n’ n c’ ) をオープンリストに加える。
Step5: Step2へ。

次に具体的な目標が記載されているサイトを記す．
3.ヒューリステック関数の仕様という部分を同じく8パズルにおいて行おうとしている．
参考サイト

###実装方針
リストの要素を削除するのはリンクを張り替えればよいので，方法としては
子ノードを生成したときに，すでにそのstateがcloseリストに無いとき，コストを計算し，openリストにもないもしくは同一のstateでも今回の方がコストが小さい場合，openリストに格納し，openリストを一周して最小コストをグローバル関数min_costで取っていく，
その後，もう一度openリストを初めから見ていき，最小コストと一致する状態から子ノードを展開し，
その展開を行ったノードに貼っているリンクを子ノードにつなぎなおす．代わりにcloseリストにそのノードを入れる．
h1()が0となるまでこれを繰り返す．

###現状のコード
・構造体によってopenリストとcloseリストを生成した，
・探索を行うsearch関数の条件の構造までは記述した．
・searchにおいて，openリスト中のmin_costを見つけるものを作成．
・min_costをもつnodeをopenリストから削除できるようにした．
・プログラム終了時にリストを破棄する関数を作成した．
・ヒューリスティック関数h1を作成した．
・探索にかかった時間を出力する．

コードを編集いたしましたので追記にて記します．

###質問内容
・次にあげる部分を現状のコードに組み込んで子ノードを生成させたいのですが，私が考えている組み込み方の直す点を教えていただきたいです．反復深化という方法で子ノードを生成するときに用いています．
反復深化
説明を加えます．
adjacentは
0|1|2
3|4|5
6|7|8
と配置したときの隣り合う数字を示しています．例えば0ならば1, 3とのみ隣り合っています．隣り合う数字がもう出尽くしたという意味で-1を用いています．

print_answerは下位にたどり着くまでに動かした数字を格納しています．
深さ優先では厳しいので幅優先にします，内容派追記にて書かせていただきます．

####組みこもうとしているもの
上のコードでのnの扱いが上手くできていません．
これでは一パターンの子ノードしか作れない．
と私は考えています．
追記にて記します．
`

####残っているやるべきこと
・子ノードの生成
・木の生成

##追記
####現状のコード全体

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <time.h>

#define TRUE  1
#define FALSE 0
#define GOAL  2
#define SIZE  9
#define S 0
#define MAX_STATE 181440
#define MAX_MOVE 31
#define EXIST 1
#define NOEXIST 0

char init_state[SIZE1] = {'8', '6', '7', '2', '5', '4', '3', '0', '1'};
char final_state[SIZE] = {'1', '2', '3', '4', '5', '6', '7', '8', '0'};
//最初のノードは親ノードを持たないのでこのあり得ないNULL_stateを親とする
char NULL_state[SIZE] = {'9', '9', '9' ,'9', '9', '9', '9', '9', '9'};

typedef struct List{
    int cost; 
    char state[SIZE];
    char parent_state[SIZE];
    struct List* next; //次の要素のポインタ
    
} List;

/* リストを追加する為の関数*/
List *ListAdd(List* ls, int cost, char state[], char parent_state[]){
    /*メモリの確保*/
    List* node = (List*)malloc(sizeof(List));
    if(node == NULL)
        return NULL;

    /*データの追加*/
    node->cost = cost;
    memcpy(node->state,state, SIZE);
    memcpy(node->parent_state,parent_state,SIZE);
    node->next = NULL;

    //test
    printf("node state\n");
    for(int i = 0; i < SIZE; i++){
        printf("%c ",node->state[i]);
    }
    printf("\n");

    /*データをリストに追加する*/
    if(ls == NULL)
        return node;
    List* search = ls;
    while (search->next != NULL)
        search = search->next;
    search->next = node;
    return ls;
}

/* リストを削除する為の関数*/
void ListAllDelete(List* ls){
    List *tmp = ls;
    while (ls->next != NULL){
        tmp = ls->next;
        ls->next = tmp->next;
        free(tmp);
    }
    free(ls);
}

int h1(char state[]){
    int count = 0;
    for(int i = 0;i < 9;i++){
        if(state[i] != final_state[i]) count++;
    }
    return count;
}

int min_cost;
List*  olist = NULL;
List*  clist = NULL;

//動かした数字
//int move_piece[MAX_MOVE + 1];

char space_postion[MAX_STATE];
char  pre_state[SIZE];
int same_state_cost;
int succeed_flag = 0;

int adjacent[SIZE][5] = {
  {1, 3, -1},       // 0
  {0, 2, 4, -1},    // 1
  {1, 5, -1},       // 2
  {0, 4, 6, -1},    // 3
  {1, 3, 5, 7, -1}, // 4
  {2, 4, 8, -1},    // 5
  {3, 7, -1},       // 6
  {4, 6, 8, -1},    // 7
  {5, 7, -1}        // 8
};

int List_search(List* list, char state[]){

    for(List* node = list; node != NULL; node = node->next){
        if(memcmp(node->state, state, SIZE) == 0){   
            same_state_cost = node->cost;
            return EXIST;
        }
    }
    return NOEXIST;
}

//char -> int
int ctoi(char c) {
	if (c >= '0' && c <= '9') {
		return c - '0';
	}
	return -1;
}

//空きマス(0)の取得
int get_space(char state[]){
    for(int i = 0;i < 9;i++){
        if(ctoi(state[i]) == 0){
            printf("space:%d\n",i);
            return  i;     
        }
    }
}

void generate_node(char state[], int p_cost){
    int space = get_space(state);

    //test
    printf("(g_n)space:%d\n",space);
    
    int n;
    memcpy(pre_state, state, SIZE); //親となるstateの保存

    //test
    printf("p_node:%s\n",pre_state);    //ok

    for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){
        //test
        printf("n:%d\n",n); //OK

      /* 移動 */
      state[space] = state[n]; //スペースがあった場所にnにあったものを移動
      state[n] = '0'; //nをスペースにする

      //test
      printf("state[space]:%c\n", state[space]);
      printf("state[n]:%c\n", state[n]);
      printf("after move state:%s\n",state);

      if(memcmp(state, final_state, SIZE) == 0){
          printf("succeed\n");
          succeed_flag++;
          return ;
      }

      if( List_search(clist, state) == NOEXIST ){
          if( List_search(olist, state) == NOEXIST ){
              //olistにもclistにも存在しないstateなら即olistに追加
              ListAdd(olist, h1(state)+p_cost, state, pre_state);
          }else{
              //olistにのみ存在するときは，同じstateよりもコストが小さいなら追加
              if(h1(state)+p_cost < same_state_cost){
                  //同じstateのnodeを削除するためにolistを最初から見ていく
                   for(List* node = olist; node != NULL; node = node->next){
                        if(memcmp(node->next->state, state, SIZE) == 0){  
                            node->next = (node->next)->next;    //同じstateのnodeを削除
                            ListAdd(olist, h1(state)+p_cost, state, pre_state);  //olistに追加
                        }
                    }
              }
          }
      }
    }
}


//ここで探索を行う．
void search(){
    int count = 0;
    while(count < MAX_STATE){
        for(List* node = olist; node != NULL; node = node->next){
            if(node->cost < min_cost){
                min_cost = node->cost;

                //test
                printf("min_cost:%d\n");
            }
        }

        for(List* node = olist; node != NULL; node = node->next){
            if(node->cost == min_cost){
                generate_node(node->state, node->cost);
                break;
            }
        }

        //test
        //printf("%d ",count);  しっかり回っている
        min_cost = MAX_STATE;
        if(succeed_flag > 0) break;
        count++; //無限ループを防ぐ
    }

    //test
    //for(List* node = olist; node != NULL; node = node->next)    printf("%s\n", node->state);
    //for(List* node = clist; node != NULL; node = node->next)    printf("%s\n", node->state);        

    printf("search failed\n");
    
}

void main(){

    min_cost = h1(init_state);

    //test
    //printf("init min_cost:%d\n",min_cost);    OK

    //headを入れる
    olist = ListAdd(olist, MAX_STATE, NULL_state, NULL_state);
    clist = ListAdd(clist, MAX_STATE, NULL_state, NULL_state);

    olist = ListAdd(olist, h1(init_state), init_state, NULL_state);  //最初の親はNULLにしたいが怒られている
    
    printf("Search start\n");
    clock_t time = clock();
    search();
    double result = (double)(clock() - time)/CLOCKS_PER_SEC;
    printf("%.3fsec\n", result); //探索にかかった時間を表示

    ListAllDelete(olist);
    ListAllDelete(clist);
    return;
}

Answer 1

深さ優先探索とAアルゴリズムとでは情報の持ち方が全く異なるので、コードをそのまま流用するのは無理があります。
(深さ優先は一度に1つのルートしかたどらないのでmove_piece配列一つで経路を保持できるが、Aだと無理)
素直に幅優先探索のコードから流用しましょう。

それと、子ノードの生成をgenerate_nodeのように関数化しようとしていますが、
関数から複数の値を返すのは大変なので、直接search内にコピペして組み込むほうが楽でしょう。

Comments

[grape_ll]

ご指摘ありがとうございます．
私も考えていて深さ優先では無理だと思い，幅優先の方で書くことにしました，
追記にて制作途中のものを載せさせていただきますので，もしよろしければ改善点などを教えていただきたいです．

[actorbug]

「ここは少し違いそう」はこうでしょうね。
if (memcmp(node->state, state, SIZE) == 0) {
コストが小さい場合の処理は、削除して追加しなおすのではなく、costとparent_stateを書き換えるだけで十分でしょう。
List_searchの戻り値を見つけたノードへのポインタ(見つからない場合はNULL)にしておけば、再検索せずにcostなどを書き換えられるでしょう。

[grape_ll]

memcmpで条件は行けてそうです，ありがとうございます．
コストが小さい場合の処理の最適化方法，ありがとうございます．ひとまず動く形にしたあとに，教えていただいた方法で最適化してみようと思います．

一旦ここまででどのように動くのか見たいので，うごかしてみたところ，いくつか様相外の挙動をしていたのでそれを直す手助けをしていただけると嬉しいです．
まず，main関数内でiniti_stateのコストを求めることは問題なくできました．
次にリストにきちんとダミーヘッドを入れられているかを確認したところ，
for(int i = 0; i < SIZE; i++){
printf("%c ",node->state[i]);
}
と記述すれば一番下に載せたようにきちんとダミーが入っていると分かるのですが，

printf("%s ",node->state);

とすると

node state
999999999999999999ｹ
node state
999999999999999999e

のようになってしまいます．これが悪さをしているのではないかと思っているのですが，何が原因dなと考えられますでしょうか
追記の現状のコードを修正しておきました．
次に実行結果の最初の方を載せておきます

./A_star_h1
node state
9 9 9 9 9 9 9 9 9
node state
9 9 9 9 9 9 9 9 9
node state
8 6 7 2 5 4 3 0 1
Search start
space:7
(g_n)space:7
p_node:867254301
n:4
state[space]:5
state[n]:0
after move state:867204351999999999NO
n:6
state[space]:3
state[n]:0
after move state:867204031999999999NO
n:8
state[space]:1
state[n]:0
after move state:867204010999999999NO
min_cost:8
space:4
(g_n)space:4
p_node:867204010
n:1
state[space]:6
state[n]:0
after move state:807264010999999999NO
n:3
state[space]:2
state[n]:0
after move state:807024010999999999NO

[actorbug]

さすがにこれは質問とは呼べない単なるデバッグ依頼なので、自分で何とかしてください。
いきなりすべてを作ろうとせず、1ステップずつ実装と動作確認を繰り返すことをお勧めしておきます。
(まず最小値を見つけるだけ、次に見つけた最小値をclosedに入れる、次に最小値をopenから削除、など)

[grape_ll]

了解いたしました．頑張って一つずつ確かめていきます．