Q&A
提示のソースに無い部分はどうなってるでしょうか?
ListAdd(), h1(), init_state, pre_state, 他には?
また、work_stateは、関数を抜けたところで、内容が保証されません。ここも気になる。
というより、まず、関数ListAdd()がどんな処理してるか?
再現できるコードを
以下に示すような内容のコードでgenerate_node関数でolistに要素を加えているのですが，search関数でolistの中身を見ると追加した内容が反映されていないのですが，グローバル変数なのに関数内のみでしか変化が適用されていないのはおかしいと思います．
どのようにすれば変更を関数外にも適用できますでしょうか．
試したみたこととしては，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は空いているマスです．
C
1typedef struct List{ 2 int cost; 3 char state[SIZE+1]; 4 char parent_state[SIZE+1]; 5 struct List* next; //次の要素のポインタ 6 7} List; 8 9int min_cost; 10List* olist = NULL; 11List* clist = NULL; 12 13int ctoi(char c) { 14 if (c >= '0' && c <= '9') { 15 return c - '0'; 16 } 17 return -1; 18} 19 20//空きマス(0)の取得 21int get_space(char state[]){ 22 for(int i = 0;i < 9;i++){ 23 if(ctoi(state[i]) == 0) return i; 24 } 25} 26void generate_node(char state[], int p_cost){ 27 int space = get_space(state); 28 char work_state[SIZE+1]; 29 int n; 30 memcpy(pre_state, state, SIZE+1); //親となるstateの保存 31 memcpy(work_state, state, SIZE+1); //状態を変えるstate 32 33 //test 34 printf("p_node:%s\n",pre_state); //ok 35 36 for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){ 37 /* 移動 */ 38 work_state[space] = work_state[n]; //スペースがあった場所にnにあったものを移動 39 work_state[n] = '0'; //nをスペースにする 40 ListAdd(olist, h1(work_state)+p_cost, work_state, pre_state); 41 memcpy(work_state, state, SIZE+1); 42 } 43} 44 45void search(){ 46 int count = 0; 47 while(count < MAX_STATE){ 48 for(List* node = olist; node != NULL; node = node->next){ 49 if(node->cost < min_cost){ 50 min_cost = node->cost; 51 } 52 } 53 54 for(List* node = olist; node != NULL; node = node->next){ 55 if(node->next->cost == min_cost){ 56 generate_node(node->next->state, node->next->cost); 57 node->next = NULL; 58 break; 59 } 60 } 61 62 min_cost = MAX_STATE; //min_costを毎回大きい値にセット 63 if(succeed_flag > 0) break; 64 count++; //無限ループを防ぐ 65 int number = 0; 66 for(List* node = olist; node != NULL;node = node->next){ 67 printf("(%d)state:%s\n",number, node->state); 68 number++; 69 } 70 } 71 printf("search failed\n"); 72 73} 74 75int main(void){ 76 77 min_cost = h1(init_state); 78 79 //headを入れる 80 olist = ListAdd(olist, MAX_STATE, NULL_state, NULL_state); 81 clist = ListAdd(clist, MAX_STATE, NULL_state, NULL_state); 82 83 olist = ListAdd(olist, h1(init_state), init_state, NULL_state); 84 85 printf("Search start\n"); 86 clock_t time = clock(); 87 search(); 88 double result = (double)(clock() - time)/CLOCKS_PER_SEC; 89 printf("%.3fsec\n", result); //探索にかかった時間を表示 90 91 ListAllDelete(olist); 92 ListAllDelete(clist); 93 return 0; 94}
###追記
関数の挙動が分からないものがあるとのご指摘を受けたので，
以下にコード全体を載せます．
#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; }
コードが大変複雑なので，機能的な部分だけ伐採しようとしたのですが，うまくできていないようです，申し訳ございません．
追記にコード全体を貼らせていただきます．
回答3件
0
グローバル変数なのに関数内のみでしか変化が適用されていないのはおかしいと思います．
グローバル変数は、どの関数から見ても同じ値です。
なので、それ以外の部分であなたのプログラムが間違っていると言うことです。
・リストの作成が意図通りに出来ていない
・リストの表示が意図通りに出来ていない
など。
投稿2021/06/10 07:39
総合スコア85901
0
ベストアンサー
他の方がおっしゃっている通りで、グローバル変数はきちんと書き換わっているのに、
プログラムに間違いがあるから、書き換わっていないように見えているだけです。
// <-こことコメントを付けたところで何が行われているかを考えてみてください。
C
1void search(){ 2 int count = 0; 3 while(count < MAX_STATE){ 4 for(List* node = olist; node != NULL; node = node->next){ 5 if(node->cost < min_cost){ 6 min_cost = node->cost; 7 } 8 } 9 10 for(List* node = olist; node != NULL; node = node->next){ 11 if(node->next->cost == min_cost){ 12 generate_node(node->next->state, node->next->cost); 13 node->next = NULL; // <-ここ 14 break; 15 } 16 } 17 18 min_cost = MAX_STATE; //min_costを毎回大きい値にセット 19 if(succeed_flag > 0) break; 20 count++; //無限ループを防ぐ 21 int number = 0; 22 for(List* node = olist; node != NULL;node = node->next){ 23 printf("(%d)state:%s\n",number, node->state); 24 number++; 25 } 26 } 27 printf("search failed\n"); 28 29}
あと、何らかのデバッガを導入して、どこがおかしいかを自分で見つけられるようにしてください。
投稿2021/06/10 11:36
総合スコア2429
探索した相曽はopenlistから削除したいのでnode->nextをNULLにすることで削除しているのですが，これではgenerate_nodeでの追加はされないのでしょうか．
親ノードを削除する意味でこの文を入れているのですが．
「単方向リスト 削除」あたりでググりましょう。
明らかに異なる手順で削除しているのが分かると思います。
void ListDelete(List* head, int index){
List* pre_node = head;
List* now_node;
for(int i = 0; i < index; i++){
if(pre_node == NULL){
printf("指定位置にnodeがない");
return ;
}
pre_node = pre_node->next;
}
now_node = pre_node->next;
if(now_node == NULL){
printf("指定位置にノードがない");
return ;
}
pre_node->next = now_node->next;
free(now_node);
return;
}
これにすることでうまく反映されるようになりました．
ありがとうございます．
今までインデックスを使っていなかったのに、いきなりインデックスによる削除のソースを出されると、
正直きちんと理解できているのか疑わざるを得ません。(理解できていれば3行で終わるはずの処理)
内容を理解せずにコピペするだけだと、いつまでたっても自力で問題を解決できるようになりませんよ。
なお、いまの初期状態・終了状態だとステップ数が多すぎて厳しいので、
以下の簡単な問題から取り組むのがよいかもしれません。
char init_state[SIZE] = { '1', '3', '4', '0', '2', '5', '8', '7', '6' };
char final_state[SIZE] = { '1', '2', '3', '8', '0', '4', '7', '6', '5' };
なお、この問題の最短手は7手で、A*アルゴリズムが正常に実装されていれば
search内のループ7回(無駄な探索なし)で回答にたどり着きます。
返信が遅れてしまい申し訳ありません，
28手で終了となる解についても適切に処理することが出来たので問題ありませんでした．
なるべく，調べたものを読み解いてから使うようにはしています．
この削除関数を用いる前もindexをちゅおくせつ用いてはいませんでしたが，親ノードからのリンクを切り離すことをやろうとしていたので問題ないと判断いたしました．
色々手助けしていただきありがとうございました．
あなたの回答
tips
プレビュー
