編集履歴

質問編集履歴

情報が足りなかった

2021/06/08 12:55

投稿

grape_ll

スコア83

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -152,6 +152,16 @@
+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;
@@ -194,6 +204,20 @@
+    //test
+    printf("node state\n");
+    for(int i = 0; i < SIZE; i++){
+        printf("%c ",node->state[i]);
+    }
+    printf("\n");
     /*データをリストに追加する*/
     if(ls == NULL)
@@ -300,13 +324,13 @@
-int List_search(List* list, char* state){
+int List_search(List* list, char state[]){
     for(List* node = list; node != NULL; node = node->next){
-        if(node->state == state){   //ここは少し違いそう
+        if(memcmp(node->state, state, SIZE) == 0){
             same_state_cost = node->cost;
@@ -322,13 +346,31 @@
+//char -> int
+int ctoi(char c) {
+	if (c >= '0' && c <= '9') {
+		return c - '0';
+	}
+	return -1;
+}
 //空きマス(0)の取得
-int get_space(char* state){
+int get_space(char state[]){
     for(int i = 0;i < 9;i++){
-        if(state[i] == '0'){
+        if(ctoi(state[i]) == 0){
+            printf("space:%d\n",i);
             return  i;
@@ -340,27 +382,57 @@
-void generate_node(List* olist, List* clist, char* state, int p_cost){
+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をスペースにする
+      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(state == final_state){
+      if(memcmp(state, final_state, SIZE) == 0){
           printf("succeed\n");
@@ -390,7 +462,7 @@
                    for(List* node = olist; node != NULL; node = node->next){
-                        if(node->next->state == state){  //ここもすこし違いそう
+                        if(memcmp(node->next->state, state, SIZE) == 0){
                             node->next = (node->next)->next;    //同じstateのnodeを削除
@@ -402,113 +474,77 @@
               }
           }
       }
     }
-}
+}
+//ここで探索を行う．
+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;
-/* IDSのやり方
+                //test
+                printf("min_cost:%d\n");
+            }
+        }
+        for(List* node = olist; node != NULL; node = node->next){
+            if(node->cost == min_cost){
-char* generate_node(char* state){
+                generate_node(node->state, node->cost);
-    int space;
+                break;
+            }
+        }
+        //test
+        //printf("%d ",count);  しっかり回っている
-    for(int i = 0;i < 9;i++){
+        min_cost = MAX_STATE;
-        if(state[i] == '0')
+        if(succeed_flag > 0) break;
-            space = i;
+        count++; //無限ループを防ぐ
     }
-    for(int i = 0; adjacent[space][i] != -1; i++){
-        int x = adjacent[space][i];
-        int p = state[x];
-        if (move_piece[n] == p) continue;
-        move_piece[n + 1] = p;
-        state[space] = p;
-        state[x] = S;
-    }
-    return state;
-}
-*/
-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};
-//最初のノードは親ノードを持たないのでこのあり得ないNULL_stateを親とする
-char NULL_state[SIZE] = {9, 9, 9 ,9, 9, 9, 9, 9, 9};
-//ここで探索を行う．
+    //test
-void search(){
-    int count = 0;
-    while(count < MAX_STATE){
-        for(List* node = olist; node != NULL; node = node->next){
+    //for(List* node = olist; node != NULL; node = node->next)    printf("%s\n", node->state);
-            if(node->cost < min_cost){
-                min_cost = node->cost;
-            }
-        }
-        for(List* node = olist; node != NULL; node = node->next){
+    //for(List* node = clist; node != NULL; node = node->next)    printf("%s\n", node->state);
-            if(node->cost == min_cost){
-                generate_node(olist, clist, node->state, node->cost);
-                break;
-            }
-        }
-        if(succeed_flag > 0) break;
-        count++; //無限ループを防ぐ
-    }
@@ -526,6 +562,14 @@
     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);
@@ -538,6 +582,8 @@
+    printf("Search start\n");
     clock_t time = clock();
     search();
@@ -559,165 +605,3 @@
 ```
-####組みこもうとしているもの
-search関数，まだ修正しきれていません，申し訳ございません．
-```C
-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(node->state == state){   //ここは少し違いそう
-            same_state_cost = node->cost;
-            return EXIST;
-        }
-    }
-    return NOEXIST;
-}
-//空きマス(0)の取得
-int get_space(char* state){
-    for(int i = 0;i < 9;i++){
-        if(state[i] == '0'){
-            return  i;
-        }
-    }
-}
-void generate_node(List* olist, List* clist, char* state, int p_cost){
-    int space = get_space(state);
-    int n;
-    memcpy(pre_state, state, SIZE); //親となるstateの保存
-    for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){
-      /* 移動 */
-      state[space] = state[n]; //スペースがあった場所にnにあったものを移動
-      state[n] = 0; //nをスペースにする
-      if(state == final_state){
-          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(node->next->state == state){  //ここもすこし違いそう
-                            node->next = (node->next)->next;    //同じstateのnodeを削除
-                            ListAdd(olist, h1(state)+p_cost, state, pre_state);  //olistに追加
-                        }
-                    }
-              }
-          }
-      }
-    }
-}
-```

内容の充実化

2021/06/08 12:55

投稿

grape_ll

スコア83

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -168,189 +168,485 @@
-/*
-* リストを追加する為の関数
+/* リストを追加する為の関数*/
+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;
+    /*データをリストに追加する*/
+    if(ls == NULL)
+        return node;
+    List* search = ls;
+    while (search->next != NULL)
+        search = search->next;
-* 戻り値:失敗時:NULL, 成功時:リスト
+    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(node->state == state){   //ここは少し違いそう
+            same_state_cost = node->cost;
+            return EXIST;
+        }
+    }
+    return NOEXIST;
+}
+//空きマス(0)の取得
+int get_space(char* state){
+    for(int i = 0;i < 9;i++){
+        if(state[i] == '0'){
+            return  i;
+        }
+    }
+}
+void generate_node(List* olist, List* clist, char* state, int p_cost){
+    int space = get_space(state);
+    int n;
+    memcpy(pre_state, state, SIZE); //親となるstateの保存
+    for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){
+      /* 移動 */
+      state[space] = state[n]; //スペースがあった場所にnにあったものを移動
+      state[n] = 0; //nをスペースにする
+      if(state == final_state){
+          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(node->next->state == state){  //ここもすこし違いそう
+                            node->next = (node->next)->next;    //同じstateのnodeを削除
+                            ListAdd(olist, h1(state)+p_cost, state, pre_state);  //olistに追加
+                        }
+                    }
+              }
+          }
+      }
+    }
+}
+/* IDSのやり方
+char* generate_node(char* state){
+    int space;
+    for(int i = 0;i < 9;i++){
+        if(state[i] == '0')
+            space = i;
+    }
+    for(int i = 0; adjacent[space][i] != -1; i++){
+        int x = adjacent[space][i];
+        int p = state[x];
+        if (move_piece[n] == p) continue;
+        move_piece[n + 1] = p;
+        state[space] = p;
+        state[x] = S;
+    }
+    return state;
+}
 */
-List *ListAdd(List* ls, int cost, char state[], char parent_state[]){
+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};
+//最初のノードは親ノードを持たないのでこのあり得ないNULL_stateを親とする
+char NULL_state[SIZE] = {9, 9, 9 ,9, 9, 9, 9, 9, 9};
-    /*メモリの確保*/
+//ここで探索を行う．
-    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;
-    /*データをリストに追加する*/
-    if(ls == NULL)
-        return node;
-    List* search = ls;
+void search(){
-    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;
+    while(count < MAX_STATE){
+        for(List* node = olist; node != NULL; node = node->next){
+            if(node->cost < min_cost){
+                min_cost = node->cost;
+            }
+        }
+        for(List* node = olist; node != NULL; node = node->next){
+            if(node->cost == min_cost){
+                generate_node(olist, clist, node->state, node->cost);
+                break;
+            }
+        }
+        if(succeed_flag > 0) break;
+        count++; //無限ループを防ぐ
+    }
+    printf("search failed\n");
+}
+void main(){
+    min_cost = h1(init_state);
+    //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にしたいが怒られている
+    clock_t time = clock();
+    search();
+    double result = (double)(clock() - time)/CLOCKS_PER_SEC;
+    printf("%.3fsec\n", result); //探索にかかった時間を表示
+    ListAllDelete(olist);
+    ListAllDelete(clist);
+    return;
+}
+```
+####組みこもうとしているもの
+search関数，まだ修正しきれていません，申し訳ございません．
+```C
+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(node->state == state){   //ここは少し違いそう
+            same_state_cost = node->cost;
+            return EXIST;
+        }
+    }
+    return NOEXIST;
+}
+//空きマス(0)の取得
+int get_space(char* state){
     for(int i = 0;i < 9;i++){
-        if(state[i] != final_state[i]) count++;
+        if(state[i] == '0'){
-    }
-    return count;
+            return  i;
-}
-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 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(node->state == state){   //ここは少し違いそう
-            same_state_cost = node->cost;
-            return EXIST;
         }
     }
-    return NOEXIST;
 }
 void generate_node(List* olist, List* clist, char* state, int p_cost){
-    int space;
-    for(int i = 0;i < 9;i++){
-        if(state[i] == '0'){
+    int space = get_space(state);
-            space = i;
-            break;
-        }
-    }
     int n;
@@ -364,6 +660,20 @@
       state[n] = 0; //nをスペースにする
+      if(state == final_state){
+          printf("succeed\n");
+          succeed_flag++;
+          return ;
+      }
       if( List_search(clist, state) == NOEXIST ){
           if( List_search(olist, state) == NOEXIST ){
@@ -378,6 +688,8 @@
               if(h1(state)+p_cost < same_state_cost){
+                  //同じstateのnodeを削除するためにolistを最初から見ていく
                    for(List* node = olist; node != NULL; node = node->next){
                         if(node->next->state == state){  //ここもすこし違いそう
@@ -408,322 +720,4 @@
 }
-/* IDSのやり方
-char* generate_node(char* state){
-    int space;
-    for(int i = 0;i < 9;i++){
-        if(state[i] == '0')
-            space = i;
-    }
-    for(int i = 0; adjacent[space][i] != -1; i++){
-        int x = adjacent[space][i];
-        int p = state[x];
-        if (move_piece[n] == p) continue;
-        move_piece[n + 1] = p;
-        state[space] = p;
-        state[x] = S;
-    }
-    return state;
-}
-*/
-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};
-//最初のノードは親ノードを持たないのでこのあり得ないNULL_stateを親とする
-char NULL_state[SIZE] = {9, 9, 9 ,9, 9, 9, 9, 9, 9};
-//ここで探索を行う．
-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;
-            }
-        }
-        for(List* node = olist; node != NULL; node = node->next){
-            if((node->next)->cost == min_cost){
-                //子ノードの生成
-                node->next = (node->next)->next; //nodeの削除
-                //clistに削除したノードを追加
-                clist = ListAdd(clist, (node->next)->cost, (node->next)->state, node->state);
-                if(/*子のstateがcloseリストにない*/1){
-                    //子ノード->cost = h1(子ノードのstate)　+ 親のcost;
-                    if(/*子のstateがopenにある*/1){
-                        if(/*今の見てるノードのコスト < openに保存してあるコスト*/1){
-                            //ノードの貼り換え
-                        }
-                    }
-                    else if(/*子のstateがopenにない*/1){
-                        if(/*h1(子node->state) == 0*/){
-                            printf("search finished\n");
-                            goto FINISH;
-                        }
-                        else {
-                            //子ノードをopenリストに入れる．
-                            //olist = ListAdd(olist, cost, NULL_state, NULL_state);
-                        }
-                        //olist = OlistAdd(olist, h1(子のstate)+親のcost, 親);
-                    }
-                }
-            }
-        }
-        count++; //無限ループを防ぐ
-    }
-    printf("search failed\n");
-    FINISH:
-}
-void main(){
-    min_cost = h1(init_state);
-    //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にしたいが怒られている
-    clock_t time = clock();
-    search();
-    double result = (double)(clock() - time)/CLOCKS_PER_SEC;
-    printf("%.3fsec\n", result); //探索にかかった時間を表示
-    ListAllDelete(olist);
-    ListAllDelete(clist);
-    return;
-}
 ```
-####組みこもうとしているもの
-node-generateとsearch関数で同じ条件分岐がありますが，まだ修正しきれていません，申し訳ございません．
-```C
-har space_postion[MAX_STATE];
-char  pre_state[SIZE];
-int same_state_cost;
-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(node->state == state){   //ここは少し違いそう
-            same_state_cost = node->cost;
-            return EXIST;
-        }
-    }
-    return NOEXIST;
-}
-void generate_node(List* olist, List* clist, char* state, int p_cost){
-    int space;
-    for(int i = 0;i < 9;i++){
-        if(state[i] == '0'){
-            space = i;
-            break;
-        }
-    }
-    int n;
-    memcpy(pre_state, state, SIZE); //親となるstateの保存
-    for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){
-      /* 移動 */
-      state[space] = state[n]; //スペースがあった場所にnにあったものを移動
-      state[n] = 0; //nをスペースにする
-      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){
-                   for(List* node = olist; node != NULL; node = node->next){
-                        if(node->next->state == state){  //ここもすこし違いそう
-                            node->next = (node->next)->next;    //同じstateのnodeを削除
-                            ListAdd(olist, h1(state)+p_cost, state, pre_state);  //olistに追加
-                        }
-                    }
-              }
-          }
-      }
-    }
-}
-```

内容の充実化

2021/06/07 13:03

投稿

grape_ll

スコア83

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -52,6 +52,74 @@
+コードを編集いたしましたので追記にて記します．
+###質問内容
+・~~次にあげる部分を現状のコードに組み込んで子ノードを生成させたいのですが，私が考えている組み込み方の直す点を教えていただきたいです．反復深化という方法で子ノードを生成するときに用いています．~~
+[反復深化](http://www.nct9.ne.jp/m_hiroi/linux/clang23.html)
+~~説明を加えます．
+adjacentは
+0|1|2
+3|4|5
+6|7|8
+と配置したときの隣り合う数字を示しています．例えば0ならば1, 3とのみ隣り合っています．隣り合う数字がもう出尽くしたという意味で-1を用いています．~~
+~~print_answerは下位にたどり着くまでに動かした数字を格納しています~~．
+深さ優先では厳しいので幅優先にします，内容派追記にて書かせていただきます．
+####組みこもうとしているもの
+~~上のコードでのnの扱いが上手くできていません．
+これでは一パターンの子ノードしか作れない．
+と私は考えています~~．
+追記にて記します．
+`
+####残っているやるべきこと
+・子ノードの生成
+・木の生成
+##追記
+####現状のコード全体
 ```C
 #include <stdlib.h>
@@ -64,12 +132,24 @@
+#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
 typedef struct List{
@@ -196,6 +276,180 @@
+//動かした数字
+int move_piece[MAX_MOVE + 1];
+char space_postion[MAX_STATE];
+char  pre_state[SIZE];
+int same_state_cost;
+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(node->state == state){   //ここは少し違いそう
+            same_state_cost = node->cost;
+            return EXIST;
+        }
+    }
+    return NOEXIST;
+}
+void generate_node(List* olist, List* clist, char* state, int p_cost){
+    int space;
+    for(int i = 0;i < 9;i++){
+        if(state[i] == '0'){
+            space = i;
+            break;
+        }
+    }
+    int n;
+    memcpy(pre_state, state, SIZE); //親となるstateの保存
+    for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){
+      /* 移動 */
+      state[space] = state[n]; //スペースがあった場所にnにあったものを移動
+      state[n] = 0; //nをスペースにする
+      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){
+                   for(List* node = olist; node != NULL; node = node->next){
+                        if(node->next->state == state){  //ここもすこし違いそう
+                            node->next = (node->next)->next;    //同じstateのnodeを削除
+                            ListAdd(olist, h1(state)+p_cost, state, pre_state);  //olistに追加
+                        }
+                    }
+              }
+          }
+      }
+    }
+}
+/* IDSのやり方
+char* generate_node(char* state){
+    int space;
+    for(int i = 0;i < 9;i++){
+        if(state[i] == '0')
+            space = i;
+    }
+    for(int i = 0; adjacent[space][i] != -1; i++){
+        int x = adjacent[space][i];
+        int p = state[x];
+        if (move_piece[n] == p) continue;
+        move_piece[n + 1] = p;
+        state[space] = p;
+        state[x] = S;
+    }
+    return state;
+}
+*/
 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};
@@ -340,37 +594,21 @@
-###質問内容
+####組みこもうとしているもの
-・次にあげる部分を現状のコードに組み込んで子ノードを生成させたいのですが，私が考えている組み込み方の直す点を教えていただきたいです．反復深化という方法で子ノードを生成するときに用いています．
-[反復深化](http://www.nct9.ne.jp/m_hiroi/linux/clang23.html)
-説明を加えます．
-adjacentは
-0|1|2
-3|4|5
-6|7|8
-と配置したときの隣り合う数字を示しています．例えば0ならば1, 3とのみ隣り合っています．隣り合う数字がもう出尽くしたという意味で-1を用いています．
-print_answerは下位にたどり着くまでに動かした数字を格納しています．
+node-generateとsearch関数で同じ条件分岐がありますが，まだ修正しきれていません，申し訳ございません．
 ```C
+har space_postion[MAX_STATE];
-#define S 0;
+char  pre_state[SIZE];
+int same_state_cost;
-int adjacent[N][5] = {
+int adjacent[SIZE][5] = {
   {1, 3, -1},       // 0
@@ -394,130 +632,98 @@
-char board[N];
-//動かした数字
-int move_piece[MAX_MOVE + 1];
-void print_answer(int n){
-  count++;
-  printf("process %d: ",count);
-  for (int i = 1; i <= n; i++)
-    printf("%d ", move_piece[i]);
-  printf("\n");
-}
-void dfs(int n, int space, int limit, int lower, char *goal){
-  if (n == limit) {
-    if (memcmp(board, goal, N) == 0) {
-      print_answer(n);
-    }
-  } else {
-    for (int i = 0; adjacent[space][i] != -1; i++) {
-      int x = adjacent[space][i];
-      int p = board[x];
-      if (move_piece[n] == p) continue;
-      move_piece[n + 1] = p;
-      board[space] = p;
-      board[x] = S;
-      int new_lower = lower - distance[p][x] + distance[p][space];
-      if (new_lower + n <= limit)
-	    dfs(n + 1, x, limit, new_lower, goal);
-      board[x] = p;
-      board[space] = S;
-    }
-  }
+int List_search(List* list, char* state){
+    for(List* node = list; node != NULL; node = node->next){
+        if(node->state == state){   //ここは少し違いそう
+            same_state_cost = node->cost;
+            return EXIST;
+        }
+    }
+    return NOEXIST;
+}
+void generate_node(List* olist, List* clist, char* state, int p_cost){
+    int space;
+    for(int i = 0;i < 9;i++){
+        if(state[i] == '0'){
+            space = i;
+            break;
+        }
+    }
+    int n;
+    memcpy(pre_state, state, SIZE); //親となるstateの保存
+    for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){
+      /* 移動 */
+      state[space] = state[n]; //スペースがあった場所にnにあったものを移動
+      state[n] = 0; //nをスペースにする
+      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){
+                   for(List* node = olist; node != NULL; node = node->next){
+                        if(node->next->state == state){  //ここもすこし違いそう
+                            node->next = (node->next)->next;    //同じstateのnodeを削除
+                            ListAdd(olist, h1(state)+p_cost, state, pre_state);  //olistに追加
+                        }
+                    }
+              }
+          }
+      }
+    }
 }
 ```
-####組みこもうとしているもの
-上のコードでのnの扱いが上手くできていません．
-これでは一パターンの子ノードしか作れない．
-と私は考えています．
-```C
-char* generate_node(char* state){
-    int space;
-    for(int i = 0;i < 9;i++){
-        if(state[i] == '0')
-            space = i;
-    }
-    for(int i = 0; adjacent[space][i] != -1; i++){
-        int x = adjacent[space][i];
-        int p = state[x];
-        if (move_piece[n] == p) continue;
-        move_piece[n + 1] = p;
-        state[space] = p;
-        state[x] = S;
-    }
-    return state;
-}
-```
-####残っているやるべきこと
-・子ノードの生成
-・木の生成