子ノードを生成してリストを編集する

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パズルにおいて行おうとしている．
参考サイト
###現状のコード
構造体によってopenリストとcloseリストを生成した，
次にリストに要素を加える関数を実現しようとしたが，8パズルの状態を保存するstateの格納が上手くいかない．
プリグラム終了時にリストを破棄する関数を作成した．
ヒューリスティック関数h1を作成した．

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

####残っているやるべきこと
・stateのきちんとした格納．
・木の生成
・リストの要素を削除する機構

木の生成については次のセクションに参考にするコードを載せる，それを参考に作成しようとしている．

#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;
}

###参考コード，およびサイト
コードの仕組みが載っている

#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;
}

Comments

[BeatStar]

「リストボックス」タグは関係ありません。

[grape_ll]

リストと名前があるので，その関連かと思ってしまいました．
修正させていただきます．
ご指摘ありがとうございます

Answer 1

・リストに8パズルの状態を格納する方法を教えていただきたい．

やりたいのは、こういうことでしょうか。

memcpy(node->state, state, SIZE);

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

「実現したいこと」の記述内容と比較すると、子ノードがすでにopen,closeリストに含まれている場合の対処が抜けているように見えます。

あと、とりあえず動作させるだけならこちらの実装方針でかまいませんが、
速度のことを考えると、ボトルネックになりそうな処理がいくつもあるので厳しそうです。
(最小コストの探索、子ノードがすでにopen,closeリストに含まれているかどうかの判定)

Comments

[grape_ll]

memkcpyでコピーできますね，ありがとうございます．

確かに，すでに含まれていることの対処が出来ていませんでした．なにかこの実装方針を改良して最適化するものはありますでしょうか．

[actorbug]

正直なところ、単方向リストを採用している時点で、高速化は厳しいと言わざるを得ません。
実装方針から変えるぐらいしか対処方法を思いつきません。

[grape_ll]

そうなんですね，考えてくださりありがとうございます．
人まずは現在の実装方針で進んでみようと思います．
本質問の内容の本題はstateのコピーでしたので，ここでベストアンサーとさせていただきますが，本コードをもう少し進めた形のものを用いた実装するために段階的に質問させていただこうと思っているので，もしまた教えて戴変える箇所があれば，宜しくお願いいたします．