単方向リストの全捜査

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リストを一周して最小コストをグローバル関数min_costで取っていく，
その後，もう一度openリストを初めから見ていき，最小コストと一致する状態から子ノードを展開し，
その展開を行ったノードに貼っているリンクを子ノードにつなぎなおす．代わりにcloseリストにそのノードを入れる．
h1()が0となるまでこれを繰り返す．

###現状のコード
構造体によってopenリストとcloseリストを生成した，
探索を行うsearch関数の条件の構造までは記述した．
プリグラム終了時にリストを破棄する関数を作成した．
ヒューリスティック関数h1を作成した．

###質問内容
・リストの扱いが慣れておらず，調べてみてもあまり理解できなかったので，こんかいのようなopenリストですべての要素を見ることが出来るようなループの条件を教えていただきたいです．
．main関数内の次の箇所が上手くいくようにするにはどうすればよいか教えていただきたいです．

olist = OlistAdd(olist, h1(init_state), NULL);  //最初の親はNULLにしたいが怒られている

　というように行えばよいのでしょうか．

####残っているやるべきこと
・子ノードの生成
・木の生成
・リストの要素を削除する機構

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

#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[], char parent_state[]){
    /*メモリの確保*/
    Olist* node = (Olist*)malloc(sizeof(Olist));
    if(node == NULL)
        return NULL;

    /*データの追加*/
    node->cost = cost;
    memcpy(node->state,state, SIZE);
    memcpy(node->parent_state,parent_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;
    memcpy(node->state,state, SIZE);
    memcpy(node->parent_state,parent_state,SIZE);
    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;
Olist*  olist = NULL;
Clist*  clist = NULL;

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(){
    int count = 0;
    while(count < MAX_STATE){
        while(/*リストを全部見る条件*/1){
            if(/*今見てる状態のコスト < min_cost*/1){
                //min_cost = (今見てるコスト)
            }
        }

        while(/*リストを全部見る条件*/1){
            if(/*今見てるstateのコスト == min_cost*/1){
                //子ノードの生成
                if(/*子のstateがcloseリストにない*/1){
                    if(/*子のstateがopenにある*/1){
                        if(/*今の見てるノードのコスト < openに保存してあるコスト*/1){
                            //ノードの貼り換え
                        }
                    }
                    else if(/*子のstateがopenにない*/1){
                        if(/*h1()==0*/1){
                            printf("search finished\n");
                            goto FINISH;
                        }
                        //olist = OlistAdd(olist, h1(子のstate)+親のcost, 親);
                    }
                }
            }
        }

        count++;
    }

    printf("search failed\n");
    FINISH:
    
}

void main(){

    min_cost = h1(init_state);
    olist = OlistAdd(olist, h1(init_state), NULL);  //最初の親はNULLにしたいが怒られている
    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;
}

Answer 1

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

単方向リストの各要素に対してなにかしたいなら、たとえば

void apply_all(Olist* p, void (*fun)(Olist*)) {
    while ( p != NULL ) {
        fun(p);
        p = p->next;
    }
}

costをprintしたいなら、

void print_cost(Olist* p) {
  printf("%d ", p->cost);
}

...

Olist* head; // リストの先頭
apply_all(head, &print_cost);

Comments

[grape_ll]

リストを取ってきて，それをNULLが出るまでnextで見ていけば全部見れるのですね．
printの方法もありがとうございます．

Answer 2

・リストの扱いが慣れておらず，調べてみてもあまり理解できなかったので，こんかいのようなopenリストですべての要素を見ることが出来るようなループの条件を教えていただきたいです．

これはできれば自力で正解にたどり着いてほしかったです。

for (Olist* node = olist; node != NULL; node = node->next) {
    // ...
}

．main関数内の次の箇所が上手くいくようにするにはどうすればよいか教えていただきたいです．

配列にNULLは入れられないので、他と被らない適当なダミー値を入れるぐらいでしょうか。

char null_state[SIZE] = {9, 9, 9, 9, 9, 9, 9, 9, 9};

olist = OlistAdd(olist, h1(init_state), init_state, null_state);

parent_stateの型をClist*に変えてしまう方法もありますが、理解が大変なうえに、
closedリストからopenリストに戻る可能性がある(=A*の条件を満たさない)場合は使えません。

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

Olist *OlistAdd(Olist* list, int cost, char state[], Clist* parent_state){
    // ...
    node->parent_state = parent_state;
    // ...
}

Comments

[grape_ll]

リストの探索，と寄り切りになってしまい，申し訳ございません．
Olist* node = olist
のようにすれば自然にリストの先頭になってくれるのですね．
複雑化を防ぐために，NULLの対処はNULL_stateを用いようと思います．応用の話まで含んでいただきありがとうございます．