編集履歴

質問編集履歴

内容の充実化

2021/06/11 00:00

投稿

grape_ll

スコア83

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -219,3 +219,497 @@
 }
 ```
+###追記
+関数の挙動が分からないものがあるとのご指摘を受けたので，
+以下にコード全体を載せます．
+```Ｃ
+#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 S 0
+#define MAX_STATE 181440
+#define MAX_MOVE 31
+#define EXIST 1
+#define NOEXIST 0
+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'};
+typedef struct List{
+    int cost;
+    char state[SIZE+1];
+    char parent_state[SIZE+1];
+    struct List* next; //次の要素のポインタ
+} List;
+/* リストを追加する為の関数*/
+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+1);
+    memcpy(node->parent_state,parent_state,SIZE+1);
+    node->next = NULL;
+    //test
+    printf("add node:%s\n",node->state);
+    /*データをリストに追加する*/
+    if(ls == NULL)
+        return node;
+    List* search = ls;
+    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;
+    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;
+char space_postion[MAX_STATE];
+char  pre_state[SIZE];
+int same_state_cost;    //olistに同じstateがあり，コストの貼り換えが必要な際に使う
+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(memcmp(node->state, state, SIZE) == 0){
+            same_state_cost = node->cost;
+            return EXIST;
+        }
+    }
+    return NOEXIST;
+}
+//char -> int
+int ctoi(char c) {
+	if (c >= '0' && c <= '9') {
+		return c - '0';
+	}
+	return -1;
+}
+//空きマス(0)の取得
+int get_space(char state[]){
+    for(int i = 0;i < 9;i++){
+        if(ctoi(state[i]) == 0){
+            printf("space:%d\n",i);
+            return  i;
+        }
+    }
+}
+void generate_node(char state[], int p_cost){
+    int space = get_space(state);
+    char work_state[SIZE+1];
+    int n;
+    memcpy(pre_state, state, SIZE+1); //親となるstateの保存
+    memcpy(work_state, state, SIZE+1);  //状態を変えるstate
+    //test
+    printf("p_node:%s\n",pre_state);    //ok
+    for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){
+      /* 移動 */
+      work_state[space] = work_state[n]; //スペースがあった場所にnにあったものを移動
+      work_state[n] = '0'; //nをスペースにする
+      //test
+      printf("after move state:%s\n",work_state);
+      if(memcmp(work_state, final_state, SIZE) == 0){
+          //成功
+          printf("succeed\n");  succeed_flag++;
+          return ;
+      }
+      printf("S(clist, state):%d\n", List_search(clist, work_state));
+      printf("S(olist, state):%d\n", List_search(olist, work_state));
+      if( List_search(clist, work_state) == NOEXIST ){
+          if( List_search(olist, work_state) == NOEXIST ){
+              //olistにもclistにも存在しないstateなら即olistに追加
+              ListAdd(olist, h1(work_state)+p_cost, work_state, pre_state);
+              int number = 0;
+              for(List* node = olist; node != NULL;node = node->next){
+                printf("(%d)state:%s\n",number, node->state);
+                number++;
+                }
+          }else{
+              //olistにのみ存在するときは，同じstateよりもコストが小さいなら追加
+              if(h1(work_state)+p_cost < same_state_cost){
+                  //同じstateのnodeを削除するためにolistを最初から見ていく
+                   for(List* node = olist; node != NULL; node = node->next){
+                        if(memcmp(node->next->state, work_state, SIZE) == 0){
+                            node->next = (node->next)->next;    //同じstateのnodeを削除
+                            ListAdd(olist, h1(state)+p_cost, work_state, pre_state);  //olistに追加
+                            int number = 0;
+                            for(List* node = olist; node != NULL;node = node->next){
+                                printf("(%d)state:%s\n",number, node->state);
+                                number++;
+                            }
+                        }
+                    }
+              }
+          }
+      }
+      memcpy(work_state, state, SIZE+1);
+    }
+}
+//ここで探索を行う．
+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;
+                //test
+                printf("min_cost:%d\n");
+            }
+        }
+        for(List* node = olist; node != NULL; node = node->next){
+            if(node->next->cost == min_cost){
+                generate_node(node->next->state, node->next->cost);
+                node->next = NULL;
+                break;
+            }
+        }
+        min_cost = MAX_STATE;   //min_costを毎回大きい値にセット
+        if(succeed_flag > 0) break;
+        count++; //無限ループを防ぐ
+        printf("count:%d\n",count);
+        int number = 0;
+        for(List* node = olist; node != NULL;node = node->next){
+            printf("(%d)state:%s\n",number, node->state);
+            number++;
+        }
+    }
+    printf("search failed\n");
+}
+int main(void){
+    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);
+    printf("Search start\n");
+    clock_t time = clock();
+    search();
+    double result = (double)(clock() - time)/CLOCKS_PER_SEC;
+    printf("%.3fsec\n", result); //探索にかかった時間を表示
+    ListAllDelete(olist);
+    ListAllDelete(clist);
+    return 0;
+}
+```

情報が足りなかった

2021/06/11 00:00

投稿

grape_ll

スコア83

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -176,4 +176,46 @@
 }
+int main(void){
+    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);
+    printf("Search start\n");
+    clock_t time = clock();
+    search();
+    double result = (double)(clock() - time)/CLOCKS_PER_SEC;
+    printf("%.3fsec\n", result); //探索にかかった時間を表示
+    ListAllDelete(olist);
+    ListAllDelete(clist);
+    return 0;
+}
 ```

内容の充実化

2021/06/10 10:34

投稿

grape_ll

スコア83

test CHANGED Viewed

File without changes

test CHANGED Viewed

@@ -5,6 +5,26 @@
 試したみたこととしては，generate_nodeの返り値の型をList*にして，引数にもList* olist, List* clist を追加させてreturn olistとしたのですが，適用されませんでした．
+8パズルを解いていて，stateには
+har 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'};
+のように格納されています．
+これは
+8|6|7
+2|5|4
+3|0|1
+のパズル状態を表し，0は空いているマスです．