常連

###実現したいこと
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パズルにおいて行おうとしている．
[参考サイト](https://www.ii.ist.i.kyoto-u.ac.jp/?page_id=4910)
###現状のコード
構造体によってopenリストとcloseリストを生成した，
次にリストに要素を加える関数を実現しようとしたが，8パズルの状態を保存するstateの格納が上手くいかない．
プリグラム終了時にリストを破棄する関数を作成した．
ヒューリスティック関数h1を作成した．

###質問内容
・リストに8パズルの状態を格納する方法を教えていただきたい．
．リストの要素を削除するのはリンクを張り替えればよいので，方法としては
　子ノードを生成したときにコストを計算し，openリストを一周して最小コストをグローバル関数min_costで取っていく，
　その後，もう一度openリストを初めから見ていき，最小コストと一致する状態から子ノードを展開し，
　その展開を行ったノードに貼っているリンクを子ノードにつなぎなおす．代わりにcloseリストにそのノードを入れる．
　h1()が0となるまでこれを繰り返す．
　というように行えばよいのでしょうか．

####残っているやるべきこと
・stateのきちんとした格納．
・木の生成
・リストの要素を削除する機構

木の生成については次のセクションに参考にするコードを載せる，それを参考に作成しようとしている．


```C
#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 MAX_STATE 181440

typedef struct Olist{
    int cost; 
    char state[SIZE];
    char parent_state[SIZE];
    struct Olist* next; //次の要素のポインタ
} Olist;

typedef struct Clist{
    int cost; 
    char state[SIZE];
    char parent_state[SIZE];
    struct Olist* next; //次の要素のポインタ
} Clist;

/*
* リストを追加する為の関数
* 第一引数:追加されるリストのポインタ
* 戻り値:失敗時:NULL, 成功時:リスト
*/
Olist *OlistAdd(Olist* list, int cost, char state[]){
    /*メモリの確保*/
    Olist* node = (Olist*)malloc(sizeof(Olist));
    if(node == NULL)
        return NULL;

    /*データの追加*/
    node->cost = cost;
    node->state[SIZE] = state[SIZE];
    node->next = NULL;

    /*データをリストに追加する*/
    if(list == NULL)
        return node;
    Olist* search = list;
    while (search->next != NULL)
        search = search->next;
    search->next = node;
    return list;
}

Clist *ClistAdd(Clist* list, int cost, char* state, char* parent_state){
    /*メモリの確保*/
    Clist* node = (Clist*)malloc(sizeof(Clist));
    if(node == NULL)
        return NULL;

    /*データの追加*/
    node->cost = cost;
    node->state = state;
    node->parent_state = parent_state
    node->next = NULL;

    /*データをリストに追加する*/
    if(list == NULL)
        return node;
    Clist* search = list;
    while (search->next != NULL)
        search = search->next;
    search->next = node;
    return list;
}

/*
* リストを削除する為の関数
* 第一引数:削除するリストのポインタ
* 戻り値:なし
*/
void OlistAllDelete(Olist* list){
    Olist *tmp = list;
    while (list->next != NULL){
        tmp = list->next;
        list->next = tmp->next;
        free(tmp);
    }
    free(list);
}
void ClistAllDelete(Clist* list){
    Clist *tmp = list;
    while (list->next != NULL){
        tmp = list->next;
        list->next = tmp->next;
        free(tmp);
    }
    free(list);
}

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;

char init_state[SIZE] = {8, 6, 7, 2, 5, 4, 3, 0, 1};
char final_state[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 0};

void search(){

}

void main(){
    Olist*  olist = NULL;
    Clist*  clist = NULL;

    min_cost = h1(init_state);
    olist = listAdd(olist, h1(init_state), init_state);
    search();
 
    OlistAllDelete(olist);
    ClistAllDelete(clist);
    return;
}

```

###参考コード，およびサイト
[コードの仕組みが載っている](http://www.nct9.ne.jp/m_hiroi/puzzle/eight.html)
```C
#include <stdio.h>
#include <string.h>
#include <time.h>

#define TRUE  1
#define FALSE 0
#define GOAL  2
#define SIZE  9

/* 状態数 (9! / 2) */
#define MAX_STATE 181440

/* 隣接リスト */
const char adjacent[SIZE][5] = {
  1, 3,-1,-1,-1,
  0, 4, 2,-1,-1,
  1, 5,-1,-1,-1,
  0, 4, 6,-1,-1,
  1, 3, 5, 7,-1,
  2, 4, 8,-1,-1,
  3, 7,-1,-1,-1,
  4, 6, 8,-1,-1,
  5, 7,-1,-1,-1,
};

/* キュー */
char state[MAX_STATE + 1][SIZE];      // +1 はワーク領域 
char space_postion[MAX_STATE];
int  prev_state[MAX_STATE];

/* 同一局面チェックテーブル */
char check_table[MAX_STATE * 2];

char init_state[SIZE] = {8, 6, 7, 2, 5, 4, 3, 0, 1};
char final_state[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 0};

int h1(char state[]){
    int count = 0;
    for(int i = 0;i < 9;i++){
        if(state[i] != final_state[i]) count++;
    }
    return count;
}



/* 結果を出力 */
void print_answer(int n){
  int i, j;
  if( n != 0 ) print_answer( prev_state[n] ); //再帰で最初から描いていく
  for( i = 0; i < 3; i++ ){
    for( j = 0; j < 3; j++ ){
      printf("%d ", state[n][i * 3 + j] );
    }
    printf("\n");
  }
  printf("\n");
}

/* 番号に変換 */
int change_number( char *board ){
  char work[SIZE];
  static int fact_table[SIZE] = {40320, 5040, 720, 120, 24, 6, 2, 1, 0,};
  int j, k, value = 0;
  memcpy( work, board, SIZE );
  for( j = 0; j < SIZE - 1; j++ ){
    value += fact_table[j] * work[j];
    for( k = j + 1; k < SIZE; k++ ){
      if( work[j] < work[k] ) work[k]--;
    }
  }
  //printf("value:%d\n",value);
  return value;
}

/* 探索 */
void search( void ){
  int front = 0, rear = 1; //rearは深さを示す
  /* 初期化 */
  memcpy( state[0], init_state, SIZE );
  space_postion[0] = 7;       //変更が必要
  prev_state[0] = -1;
  check_table[ change_number( init_state ) ] = TRUE;
  check_table[ change_number( final_state ) ] = GOAL;

  /* キューにデータがある間繰り返す */
  while( front < rear ){
    int s = space_postion[front];
    int i, k, n;
    for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
      /* 前の状態をコピー */
      memcpy( state[rear], state[front], SIZE );
      /* 移動 */
      state[rear][s] = state[rear][n]; //スペースがあった場所にnにあったものを移動
      state[rear][n] = 0; //nをスペースにする
      space_postion[rear] = n; //スペースの位置を示す変数にnを格納
      prev_state[rear] = front; 
      k = change_number( state[rear] ); //状態を番号に変換
      if( check_table[k] == GOAL ){ //goalの番号を一致したら発見
        print_answer( rear );
        printf("状態数 %d 個\n", rear );
        return;
      } else if( !check_table[k] ){ //なったことがあればすでにTRUE=1が入ってる
	    /* キューに登録 */
        check_table[k] = TRUE;
	    rear++;
      }
    }

    front++;
  }
}

int main(){
  /* 
   * 静的変数が 0 に初期化される場合は不用だが
   * 初期化することは悪いことではない。
   */
  memset( check_table, 0 , MAX_STATE * 2 );
  clock_t time = clock();
  search();
  double result = (double)(clock() - time)/CLOCKS_PER_SEC;
  printf("%.3fsec \n", result );
  return 0;
}
```

質問編集履歴