質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.50%
C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

Q&A

解決済

1回答

1255閲覧

8パズルの子ノードの作成

grape_ll

総合スコア83

C

C言語は、1972年にAT&Tベル研究所の、デニス・リッチーが主体となって作成したプログラミング言語です。 B言語の後継言語として開発されたことからC言語と命名。そのため、表記法などはB言語やALGOLに近いとされています。 Cの拡張版であるC++言語とともに、現在世界中でもっとも普及されているプログラミング言語です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

コードレビュー

コードレビューは、ソフトウェア開発の一工程で、 ソースコードの検査を行い、開発工程で見過ごされた誤りを検出する事で、 ソフトウェア品質を高めるためのものです。

0グッド

0クリップ

投稿2021/06/06 12:55

編集2021/06/08 12:55

###実現したいこと
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パズルにおいて行おうとしている.
参考サイト

###実装方針
リストの要素を削除するのはリンクを張り替えればよいので,方法としては
子ノードを生成したときに,すでにそのstateがcloseリストに無いとき,コストを計算し,openリストにもないもしくは同一のstateでも今回の方がコストが小さい場合,openリストに格納し,openリストを一周して最小コストをグローバル関数min_costで取っていく,
その後,もう一度openリストを初めから見ていき,最小コストと一致する状態から子ノードを展開し,
その展開を行ったノードに貼っているリンクを子ノードにつなぎなおす.代わりにcloseリストにそのノードを入れる.
h1()が0となるまでこれを繰り返す.

###現状のコード
・構造体によってopenリストとcloseリストを生成した,
・探索を行うsearch関数の条件の構造までは記述した.
・searchにおいて,openリスト中のmin_costを見つけるものを作成.
・min_costをもつnodeをopenリストから削除できるようにした.
・プログラム終了時にリストを破棄する関数を作成した.
・ヒューリスティック関数h1を作成した.
・探索にかかった時間を出力する.

コードを編集いたしましたので追記にて記します.

###質問内容
次にあげる部分を現状のコードに組み込んで子ノードを生成させたいのですが,私が考えている組み込み方の直す点を教えていただきたいです.反復深化という方法で子ノードを生成するときに用いています.
反復深化
説明を加えます.
adjacentは
0|1|2
3|4|5
6|7|8
と配置したときの隣り合う数字を示しています.例えば0ならば1, 3とのみ隣り合っています.隣り合う数字がもう出尽くしたという意味で-1を用いています.

print_answerは下位にたどり着くまでに動かした数字を格納しています
深さ優先では厳しいので幅優先にします,内容派追記にて書かせていただきます.

####組みこもうとしているもの
上のコードでのnの扱いが上手くできていません.
これでは一パターンの子ノードしか作れない.
と私は考えています

追記にて記します.
`

####残っているやるべきこと
・子ノードの生成
・木の生成

##追記
####現状のコード全体

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 S 0 11#define MAX_STATE 181440 12#define MAX_MOVE 31 13#define EXIST 1 14#define NOEXIST 0 15 16char init_state[SIZE1] = {'8', '6', '7', '2', '5', '4', '3', '0', '1'}; 17char final_state[SIZE] = {'1', '2', '3', '4', '5', '6', '7', '8', '0'}; 18//最初のノードは親ノードを持たないのでこのあり得ないNULL_stateを親とする 19char NULL_state[SIZE] = {'9', '9', '9' ,'9', '9', '9', '9', '9', '9'}; 20 21typedef struct List{ 22 int cost; 23 char state[SIZE]; 24 char parent_state[SIZE]; 25 struct List* next; //次の要素のポインタ 26 27} List; 28 29/* リストを追加する為の関数*/ 30List *ListAdd(List* ls, int cost, char state[], char parent_state[]){ 31 /*メモリの確保*/ 32 List* node = (List*)malloc(sizeof(List)); 33 if(node == NULL) 34 return NULL; 35 36 /*データの追加*/ 37 node->cost = cost; 38 memcpy(node->state,state, SIZE); 39 memcpy(node->parent_state,parent_state,SIZE); 40 node->next = NULL; 41 42 //test 43 printf("node state\n"); 44 for(int i = 0; i < SIZE; i++){ 45 printf("%c ",node->state[i]); 46 } 47 printf("\n"); 48 49 /*データをリストに追加する*/ 50 if(ls == NULL) 51 return node; 52 List* search = ls; 53 while (search->next != NULL) 54 search = search->next; 55 search->next = node; 56 return ls; 57} 58 59/* リストを削除する為の関数*/ 60void ListAllDelete(List* ls){ 61 List *tmp = ls; 62 while (ls->next != NULL){ 63 tmp = ls->next; 64 ls->next = tmp->next; 65 free(tmp); 66 } 67 free(ls); 68} 69 70int h1(char state[]){ 71 int count = 0; 72 for(int i = 0;i < 9;i++){ 73 if(state[i] != final_state[i]) count++; 74 } 75 return count; 76} 77 78int min_cost; 79List* olist = NULL; 80List* clist = NULL; 81 82//動かした数字 83//int move_piece[MAX_MOVE + 1]; 84 85char space_postion[MAX_STATE]; 86char pre_state[SIZE]; 87int same_state_cost; 88int succeed_flag = 0; 89 90int adjacent[SIZE][5] = { 91 {1, 3, -1}, // 0 92 {0, 2, 4, -1}, // 1 93 {1, 5, -1}, // 2 94 {0, 4, 6, -1}, // 3 95 {1, 3, 5, 7, -1}, // 4 96 {2, 4, 8, -1}, // 5 97 {3, 7, -1}, // 6 98 {4, 6, 8, -1}, // 7 99 {5, 7, -1} // 8 100}; 101 102int List_search(List* list, char state[]){ 103 104 for(List* node = list; node != NULL; node = node->next){ 105 if(memcmp(node->state, state, SIZE) == 0){ 106 same_state_cost = node->cost; 107 return EXIST; 108 } 109 } 110 return NOEXIST; 111} 112 113//char -> int 114int ctoi(char c) { 115 if (c >= '0' && c <= '9') { 116 return c - '0'; 117 } 118 return -1; 119} 120 121//空きマス(0)の取得 122int get_space(char state[]){ 123 for(int i = 0;i < 9;i++){ 124 if(ctoi(state[i]) == 0){ 125 printf("space:%d\n",i); 126 return i; 127 } 128 } 129} 130 131void generate_node(char state[], int p_cost){ 132 int space = get_space(state); 133 134 //test 135 printf("(g_n)space:%d\n",space); 136 137 int n; 138 memcpy(pre_state, state, SIZE); //親となるstateの保存 139 140 //test 141 printf("p_node:%s\n",pre_state); //ok 142 143 for(int i = 0; (n = adjacent[space][i]) != -1; i++ ){ 144 //test 145 printf("n:%d\n",n); //OK 146 147 /* 移動 */ 148 state[space] = state[n]; //スペースがあった場所にnにあったものを移動 149 state[n] = '0'; //nをスペースにする 150 151 //test 152 printf("state[space]:%c\n", state[space]); 153 printf("state[n]:%c\n", state[n]); 154 printf("after move state:%s\n",state); 155 156 if(memcmp(state, final_state, SIZE) == 0){ 157 printf("succeed\n"); 158 succeed_flag++; 159 return ; 160 } 161 162 if( List_search(clist, state) == NOEXIST ){ 163 if( List_search(olist, state) == NOEXIST ){ 164 //olistにもclistにも存在しないstateなら即olistに追加 165 ListAdd(olist, h1(state)+p_cost, state, pre_state); 166 }else{ 167 //olistにのみ存在するときは,同じstateよりもコストが小さいなら追加 168 if(h1(state)+p_cost < same_state_cost){ 169 //同じstateのnodeを削除するためにolistを最初から見ていく 170 for(List* node = olist; node != NULL; node = node->next){ 171 if(memcmp(node->next->state, state, SIZE) == 0){ 172 node->next = (node->next)->next; //同じstateのnodeを削除 173 ListAdd(olist, h1(state)+p_cost, state, pre_state); //olistに追加 174 } 175 } 176 } 177 } 178 } 179 } 180} 181 182 183//ここで探索を行う. 184void search(){ 185 int count = 0; 186 while(count < MAX_STATE){ 187 for(List* node = olist; node != NULL; node = node->next){ 188 if(node->cost < min_cost){ 189 min_cost = node->cost; 190 191 //test 192 printf("min_cost:%d\n"); 193 } 194 } 195 196 for(List* node = olist; node != NULL; node = node->next){ 197 if(node->cost == min_cost){ 198 generate_node(node->state, node->cost); 199 break; 200 } 201 } 202 203 //test 204 //printf("%d ",count); しっかり回っている 205 min_cost = MAX_STATE; 206 if(succeed_flag > 0) break; 207 count++; //無限ループを防ぐ 208 } 209 210 //test 211 //for(List* node = olist; node != NULL; node = node->next) printf("%s\n", node->state); 212 //for(List* node = clist; node != NULL; node = node->next) printf("%s\n", node->state); 213 214 printf("search failed\n"); 215 216} 217 218void main(){ 219 220 min_cost = h1(init_state); 221 222 //test 223 //printf("init min_cost:%d\n",min_cost); OK 224 225 //headを入れる 226 olist = ListAdd(olist, MAX_STATE, NULL_state, NULL_state); 227 clist = ListAdd(clist, MAX_STATE, NULL_state, NULL_state); 228 229 olist = ListAdd(olist, h1(init_state), init_state, NULL_state); //最初の親はNULLにしたいが怒られている 230 231 printf("Search start\n"); 232 clock_t time = clock(); 233 search(); 234 double result = (double)(clock() - time)/CLOCKS_PER_SEC; 235 printf("%.3fsec\n", result); //探索にかかった時間を表示 236 237 ListAllDelete(olist); 238 ListAllDelete(clist); 239 return; 240} 241

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答1

0

ベストアンサー

深さ優先探索とAアルゴリズムとでは情報の持ち方が全く異なるので、コードをそのまま流用するのは無理があります。
(深さ優先は一度に1つのルートしかたどらないのでmove_piece配列一つで経路を保持できるが、A
だと無理)
素直に幅優先探索のコードから流用しましょう。

それと、子ノードの生成をgenerate_nodeのように関数化しようとしていますが、
関数から複数の値を返すのは大変なので、直接search内にコピペして組み込むほうが楽でしょう。

投稿2021/06/07 11:52

actorbug

総合スコア2212

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

grape_ll

2021/06/07 12:39

ご指摘ありがとうございます. 私も考えていて深さ優先では無理だと思い,幅優先の方で書くことにしました, 追記にて制作途中のものを載せさせていただきますので,もしよろしければ改善点などを教えていただきたいです.
actorbug

2021/06/07 13:26

「ここは少し違いそう」はこうでしょうね。 if (memcmp(node->state, state, SIZE) == 0) { コストが小さい場合の処理は、削除して追加しなおすのではなく、costとparent_stateを書き換えるだけで十分でしょう。 List_searchの戻り値を見つけたノードへのポインタ(見つからない場合はNULL)にしておけば、再検索せずにcostなどを書き換えられるでしょう。
grape_ll

2021/06/09 01:41 編集

memcmpで条件は行けてそうです,ありがとうございます. コストが小さい場合の処理の最適化方法,ありがとうございます.ひとまず動く形にしたあとに,教えていただいた方法で最適化してみようと思います. 一旦ここまででどのように動くのか見たいので,うごかしてみたところ,いくつか様相外の挙動をしていたのでそれを直す手助けをしていただけると嬉しいです. まず,main関数内でiniti_stateのコストを求めることは問題なくできました. 次にリストにきちんとダミーヘッドを入れられているかを確認したところ, for(int i = 0; i < SIZE; i++){ printf("%c ",node->state[i]); } と記述すれば一番下に載せたようにきちんとダミーが入っていると分かるのですが, printf("%s ",node->state); とすると node state 999999999999999999ケ node state 999999999999999999e のようになってしまいます.これが悪さをしているのではないかと思っているのですが,何が原因dなと考えられますでしょうか 追記の現状のコードを修正しておきました. 次に実行結果の最初の方を載せておきます ./A_star_h1 node state 9 9 9 9 9 9 9 9 9 node state 9 9 9 9 9 9 9 9 9 node state 8 6 7 2 5 4 3 0 1 Search start space:7 (g_n)space:7 p_node:867254301 n:4 state[space]:5 state[n]:0 after move state:867204351999999999NO n:6 state[space]:3 state[n]:0 after move state:867204031999999999NO n:8 state[space]:1 state[n]:0 after move state:867204010999999999NO min_cost:8 space:4 (g_n)space:4 p_node:867204010 n:1 state[space]:6 state[n]:0 after move state:807264010999999999NO n:3 state[space]:2 state[n]:0 after move state:807024010999999999NO
actorbug

2021/06/08 14:43 編集

さすがにこれは質問とは呼べない単なるデバッグ依頼なので、自分で何とかしてください。 いきなりすべてを作ろうとせず、1ステップずつ実装と動作確認を繰り返すことをお勧めしておきます。 (まず最小値を見つけるだけ、次に見つけた最小値をclosedに入れる、次に最小値をopenから削除、など)
grape_ll

2021/06/09 01:40

了解いたしました.頑張って一つずつ確かめていきます.
guest

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.50%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

関連した質問