単方向リストの全捜査

###実現したいこと
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関数内の次の箇所が上手くいくようにするにはどうすればよいか教えていただきたいです．

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

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

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

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

C
1#include <stdlib.h>
2#include <stdio.h>
3#include <string.h>
4#include <time.h>
5
6#define TRUE  1
7#define FALSE 0
8#define GOAL  2
9#define SIZE  9
10#define MAX_STATE 181440
11
12typedef struct Olist{
13    int cost; 
14    char state[SIZE];
15    char parent_state[SIZE];
16    struct Olist* next; //次の要素のポインタ
17} Olist;
18
19typedef struct Clist{
20    int cost; 
21    char state[SIZE];
22    char parent_state[SIZE];
23    struct Olist* next; //次の要素のポインタ
24} Clist;
25
26/*
27* リストを追加する為の関数
28* 第一引数:追加されるリストのポインタ
29* 戻り値:失敗時:NULL, 成功時:リスト
30*/
31Olist *OlistAdd(Olist* list, int cost, char state[], char parent_state[]){
32    /*メモリの確保*/
33    Olist* node = (Olist*)malloc(sizeof(Olist));
34    if(node == NULL)
35        return NULL;
36
37    /*データの追加*/
38    node->cost = cost;
39    memcpy(node->state,state, SIZE);
40    memcpy(node->parent_state,parent_state,SIZE);
41    node->next = NULL;
42
43    /*データをリストに追加する*/
44    if(list == NULL)
45        return node;
46    Olist* search = list;
47    while (search->next != NULL)
48        search = search->next;
49    search->next = node;
50    return list;
51}
52
53Clist *ClistAdd(Clist* list, int cost, char state[], char parent_state[]){
54    /*メモリの確保*/
55    Clist* node = (Clist*)malloc(sizeof(Clist));
56    if(node == NULL)
57        return NULL;
58
59    /*データの追加*/
60    node->cost = cost;
61    memcpy(node->state,state, SIZE);
62    memcpy(node->parent_state,parent_state,SIZE);
63    node->next = NULL;
64
65    /*データをリストに追加する*/
66    if(list == NULL)
67        return node;
68    Clist* search = list;
69    while (search->next != NULL)
70        search = search->next;
71    search->next = node;
72    return list;
73}
74
75/*
76* リストを削除する為の関数
77* 第一引数:削除するリストのポインタ
78* 戻り値:なし
79*/
80void OlistAllDelete(Olist* list){
81    Olist *tmp = list;
82    while (list->next != NULL){
83        tmp = list->next;
84        list->next = tmp->next;
85        free(tmp);
86    }
87    free(list);
88}
89void ClistAllDelete(Clist* list){
90    Clist *tmp = list;
91    while (list->next != NULL){
92        tmp = list->next;
93        list->next = tmp->next;
94        free(tmp);
95    }
96    free(list);
97}
98
99int h1(char state[]){
100    int count = 0;
101    for(int i = 0;i < 9;i++){
102        if(state[i] != final_state[i]) count++;
103    }
104    return count;
105}
106
107int min_cost;
108Olist*  olist = NULL;
109Clist*  clist = NULL;
110
111char init_state[SIZE] = {8, 6, 7, 2, 5, 4, 3, 0, 1};
112char final_state[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
113
114//ここで探索を行う．
115void search(){
116    int count = 0;
117    while(count < MAX_STATE){
118        while(/*リストを全部見る条件*/1){
119            if(/*今見てる状態のコスト < min_cost*/1){
120                //min_cost = (今見てるコスト)
121            }
122        }
123
124        while(/*リストを全部見る条件*/1){
125            if(/*今見てるstateのコスト == min_cost*/1){
126                //子ノードの生成
127                if(/*子のstateがcloseリストにない*/1){
128                    if(/*子のstateがopenにある*/1){
129                        if(/*今の見てるノードのコスト < openに保存してあるコスト*/1){
130                            //ノードの貼り換え
131                        }
132                    }
133                    else if(/*子のstateがopenにない*/1){
134                        if(/*h1()==0*/1){
135                            printf("search finished\n");
136                            goto FINISH;
137                        }
138                        //olist = OlistAdd(olist, h1(子のstate)+親のcost, 親);
139                    }
140                }
141            }
142        }
143
144        count++;
145    }
146
147    printf("search failed\n");
148    FINISH:
149    
150}
151
152void main(){
153
154    min_cost = h1(init_state);
155    olist = OlistAdd(olist, h1(init_state), NULL);  //最初の親はNULLにしたいが怒られている
156    search();
157
158    OlistAllDelete(olist);
159    ClistAllDelete(clist);
160    return;
161}
162
163

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

C
1#include <stdio.h>
2#include <string.h>
3#include <time.h>
4
5#define TRUE  1
6#define FALSE 0
7#define GOAL  2
8#define SIZE  9
9
10/* 状態数 (9! / 2) */
11#define MAX_STATE 181440
12
13/* 隣接リスト */
14const char adjacent[SIZE][5] = {
15  1, 3,-1,-1,-1,
16  0, 4, 2,-1,-1,
17  1, 5,-1,-1,-1,
18  0, 4, 6,-1,-1,
19  1, 3, 5, 7,-1,
20  2, 4, 8,-1,-1,
21  3, 7,-1,-1,-1,
22  4, 6, 8,-1,-1,
23  5, 7,-1,-1,-1,
24};
25
26/* キュー */
27char state[MAX_STATE + 1][SIZE];      // +1 はワーク領域 
28char space_postion[MAX_STATE];
29int  prev_state[MAX_STATE];
30
31/* 同一局面チェックテーブル */
32char check_table[MAX_STATE * 2];
33
34char init_state[SIZE] = {8, 6, 7, 2, 5, 4, 3, 0, 1};
35char final_state[SIZE] = {1, 2, 3, 4, 5, 6, 7, 8, 0};
36
37int h1(char state[]){
38    int count = 0;
39    for(int i = 0;i < 9;i++){
40        if(state[i] != final_state[i]) count++;
41    }
42    return count;
43}
44
45
46
47/* 結果を出力 */
48void print_answer(int n){
49  int i, j;
50  if( n != 0 ) print_answer( prev_state[n] ); //再帰で最初から描いていく
51  for( i = 0; i < 3; i++ ){
52    for( j = 0; j < 3; j++ ){
53      printf("%d ", state[n][i * 3 + j] );
54    }
55    printf("\n");
56  }
57  printf("\n");
58}
59
60/* 番号に変換 */
61int change_number( char *board ){
62  char work[SIZE];
63  static int fact_table[SIZE] = {40320, 5040, 720, 120, 24, 6, 2, 1, 0,};
64  int j, k, value = 0;
65  memcpy( work, board, SIZE );
66  for( j = 0; j < SIZE - 1; j++ ){
67    value += fact_table[j] * work[j];
68    for( k = j + 1; k < SIZE; k++ ){
69      if( work[j] < work[k] ) work[k]--;
70    }
71  }
72  //printf("value:%d\n",value);
73  return value;
74}
75
76/* 探索 */
77void search( void ){
78  int front = 0, rear = 1; //rearは深さを示す
79  /* 初期化 */
80  memcpy( state[0], init_state, SIZE );
81  space_postion[0] = 7;       //変更が必要
82  prev_state[0] = -1;
83  check_table[ change_number( init_state ) ] = TRUE;
84  check_table[ change_number( final_state ) ] = GOAL;
85
86  /* キューにデータがある間繰り返す */
87  while( front < rear ){
88    int s = space_postion[front];
89    int i, k, n;
90    for( i = 0; (n = adjacent[s][i]) != -1; i++ ){
91      /* 前の状態をコピー */
92      memcpy( state[rear], state[front], SIZE );
93      /* 移動 */
94      state[rear][s] = state[rear][n]; //スペースがあった場所にnにあったものを移動
95      state[rear][n] = 0; //nをスペースにする
96      space_postion[rear] = n; //スペースの位置を示す変数にnを格納
97      prev_state[rear] = front; 
98      k = change_number( state[rear] ); //状態を番号に変換
99      if( check_table[k] == GOAL ){ //goalの番号を一致したら発見
100        print_answer( rear );
101        printf("状態数 %d 個\n", rear );
102        return;
103      } else if( !check_table[k] ){ //なったことがあればすでにTRUE=1が入ってる
104	    /* キューに登録 */
105        check_table[k] = TRUE;
106	    rear++;
107      }
108    }
109
110    front++;
111  }
112}
113
114int main(){
115  /* 
116   * 静的変数が 0 に初期化される場合は不用だが
117   * 初期化することは悪いことではない。
118   */
119  memset( check_table, 0 , MAX_STATE * 2 );
120  clock_t time = clock();
121  search();
122  double result = (double)(clock() - time)/CLOCKS_PER_SEC;
123  printf("%.3fsec \n", result );
124  return 0;
125}

行動規範の内容に同意します

回答2件

C
1typedef struct Olist{
2    int cost; 
3    char state[SIZE];
4    char parent_state[SIZE];
5    struct Olist* next; //次の要素のポインタ
6} Olist;

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

C
1void apply_all(Olist* p, void (*fun)(Olist*)) {
2    while ( p != NULL ) {
3        fun(p);
4        p = p->next;
5    }
6}

costをprintしたいなら、

C
1void print_cost(Olist* p) {
2  printf("%d ", p->cost);
3}
4
5...
6
7Olist* head; // リストの先頭
8apply_all(head, &print_cost);

投稿2021/06/06 06:57

episteme

総合スコア16612

grape_ll

2021/06/06 11:22

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

行動規範の内容に同意します

ベストアンサー

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

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

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

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

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

c
1char null_state[SIZE] = {9, 9, 9, 9, 9, 9, 9, 9, 9};
2
3olist = OlistAdd(olist, h1(init_state), init_state, null_state);

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

c
1struct Clist;
2typedef struct Olist{
3    int cost; 
4    char state[SIZE];
5    struct Clist* parent_state;
6    struct Olist* next; //次の要素のポインタ
7} Olist;
8
9Olist *OlistAdd(Olist* list, int cost, char state[], Clist* parent_state){
10    // ...
11    node->parent_state = parent_state;
12    // ...
13}