. 1 Fig Fig 3 : 4 : 5 : 7 : 15 パズル 14 2 9 7 8 1 13 4 10 5 12 . 2 1 5 9 13 14 2 9 2 6 10 14 3 7 11 15 初期盤面 ( 一例 ) 15 パズルに現れる堂々巡り 最終盤面 7 8 1 13 4 3 10 4 8 12 15 12 5 14 2 9 14 2 9 7 8 1 13 4 10 5 12 4 手で移動できる 【局面 A 】 4 手で移動できる 【局面 B 】 4 手で移動できる 7 8 1 13 4 15 3 5 12 10 【局面 C 】 幅優先探索の基本形 List 1 1 : breath ゴ irst-search() 6 : 8 : 9 : 局面の集合 : 空 : 局面の集合に初期状態を追加 : ⅶⅱ e ( 解が見つかっていない ) { 局面 A : 局面の集合からひとっ取りだす : f 0 r ( 局面 X = 局面 A から 1 手で移れる各局面 ) { if ( 局面 X は解の条件を満たす ) 解を表示する i f ( X は局面の集合に属なさい ) 局面の集合に局面 X を追加 ( A ) ( B ) 実践アルゴリズ解法のニック のすべての局面を記憶しておき , すてに調 になります。これを避けるためには , 過去 うような堂々巡りに入りこむと , 無限再帰 場合てすと , Fig. 2 の局面 A → B → C → A とい ラックて、はうまく解けません。 15 パズルの この堂々巡りがあると , 単純なバックト りが存在することになります。 この三つの局面を移っていくだけの堂々巡 相互に 4 手て、移ることがて、きます。つまり , 面の例を表しています。局面から局面へは , から , 右下の三つのコマだけを動かした局 見てください。この図は , Fig. 1 の 15 パズル とがあります。例をあげましよう。 Fig. 2 を ているうちに以前の局面に戻ってしまうこ りますが , このパズルては , コマを動かし 実際に 15 パズルを手て解いてみるとわか ありません。 理由のひとって、すが , 理由はこれだけては を記憶することは問題によっては非常に大 処が必要になります。過去のすべての局面 をしない ( だまってリターンする ) などの対 べた局面にぶつかったら , それ以上の探索 実践アルゴリズム戦略 69 じ局面が何度も現れる可能性があります。 上記の手順て局面を生成していくと , 同 ら終わりてす。 解を得るか , すべての局面を調べっくした 同様にして 3 手目以降を調べていき , 目的の 到達てきる局面を調べて記憶します。以下 いま求めたばかりの局面を使って , 2 手目て るすべての局面を調べて記憶します。次に のて、す。まず , 初期状態から 1 手て到達てき の基本的な考え方は , 非常にシンプルなも 冒頭ても少し述べたように , 幅優先探索 幅優先探索の考え方 優先探索の考え方と実装法について解説し る程度解決てきます。次の節ては , この幅 上記の問題は「幅優先探索」を使うと , あ クの利点が生かせません。 きな記憶領域が必要てあり , バックトラッ
実践アルゴリズ解法のテクニック Fig. 3 幅優先探索の様子 Fig. 4 n ー 2 手目以前のチェックを省略できることの証明 下の図は , n 手目の局面 A から , n 十 1 手目の局面 B を生成したところである。 重複チェックを行っているから , 局面 A は n ー 1 手目以前には存在しない。 局面 A → 局面 B n 手目 n 十 1 手目 上の図で , 局面 B は n ー 2 手目以前には存在しないはずである。仮に n ー 2 手目に 局面 B があったとすると , 局面 A と局面 B は相互に 1 手で往来できるから , 局面 B 局面 A n ー 2 手目 n ー 1 手目 局面 A が n ー 1 手目に存在することになる。これは , 局面 A が n 手目に ( 初めて ) 現れることに矛盾する。局面 B が n ー 2 手目より前に存在する場合も同様である。 したがって , 局面 B は n ー 2 手目以前には存在しないことから , n ー 1 手目以降の みを検査すれば足りる。 合 , 重複チェックのために保存する局面の g. 4 を見ていただければ , 明らかなことの積 の方法と比べると記憶容量を半分に節約て、 数を大幅に減らすことがて、きることが知ら み重ねて、あることがおわかりいただけると ことになります。 れています。 田います。この証明のなかて、とくに重要な部 この手の圧縮技法は , 計算速度という観 じ、 15 パズルを例に取って説明しましよう。 分が , 「局面 A と局面 B は相互に 1 手て、往来て、 点から見ると微妙な問題を含んて、います。 今 n 手目の局面から n 十 1 手目の局面を生成し きる」というところて、す。この条件が成り立 データを圧縮したり戻したりするためには , ている最中だとします。この場合の重複チ たないと証明が成立しませんが , 15 パズル 明らかに余分な計算時間が掛かります。 ェックは , n— 1 手目 , n 手目 , n 十 1 手目の 3 の場合にはコマを逆に動かすだけのことて、 れはマイナス要素て、すが , 一方て、はプラス 種類だけて、よいことが証明されています。 すから , 先の条件は成立しています。 要素もあります。 n— 1 手目の局面と比較しなければならない 局面の数が多いと上記による効果は絶大 データを圧縮してコンパクトにしたおか ことは明らかて、す。 て、す。ぜひ記憶しておいていただきたい手 げて、 , データ転送に要する時間は減少しま これは 15 パズルの場合 , n 手目て、右に動か すし , 同一局面のチェックを行ううえても , 法といえます。 したコマを , n 十 1 手目て、左に戻すという ( ム 次に②について説明します。これは一種 データ量が少ないほうがより高速に行える ダな ) 着手を意味しています。また , n 手目 のデータ圧縮て、すが , パズルのプログラミ はずて、す。さらに , キャシュメモリや仮想 や n 十 1 手目の ( ほかの ) 局面とチェックしな ングに慣れた方にはお馴染みの方法て、しょ 己憶を備えた計算機の場合は , 使用メモリ ければならないこともほば明らかて、しよう。 量を減らすだけて、キャッシュなどの効果が 問題は , n ー 2 手目以前の局面をチェックし たとえば 15 パズルを例に取ると , 盤に置 増えるのて、 , 高速化がはかれる場合があり なくてもよい理由て、す。直観的にはわかり けるコマは 1 ~ 15 の 15 通りて、 , 空いたマス目 にくいかもしれませんが , この理由は背理 を 0 て、表現することにすると , 0 ~ 15 の 16 通 データ量を半分にすることは , キャッシ 法て、証明することがて、きます。この証明を りの可能性になります。これは 4 ビットて、表 ュの容量を倍にすることとほば同じだと考 Fig. 4 に示します。 現て、きますから , 1 バイトの変数に 2 マス分 えれば , 上記は納得しやすいて、しよう。 背理法などというと難しそうて、すが , Fi のデータを押し込むことがて、きます。通常 これらの理由から , データを圧縮するこ との得失は , 上に説明したような種々の要 Fig. 5 プログラミングの秘訣 ( 「プログラム書法」から「規則集」の引用 ) 素をにらみながらよく検討しなければなり ません。このため , 以下のように段階的な ・速くする前に正しくしよう 開発をお勧めします。つまり , 圧縮なして ・速くする前にわかりやすくしよう ・速くしたかったら単純さを保とう もメモリ容量が足りるなら , 取りあえず圧 ・速くしようとしてプログラムをひねくりまわすのはやめて , 縮なしの単純なプログラムを作ってしまう もっとよいアルゴリズムをみつけよう のて、す。この時点て演算時間の計測を行い , 3 手目 ぐーここまでは検討した 3 手目 《一次に検討すべき局面 (P) 3 手目 3 手目 4 手目 4 手目 4 手目 4 手目 今までに生成した 4 手目の局面 ぐ一次に生成した局面はこ に入る ( 0 ) 一三ロ 実践アルゴリズム戦略 71
これは再帰の苦手な人には朗報といえる ら , 1 手進めて次の局面 ( 図て、は 4 手目の局面 ) 同じ局面が現れるのは , 先に説明した「堂々 かもしれませんが , バックトラックに話を を生成します。生成したそれぞれの局面に 巡り」の場合がそうて、すし , 将棋などて、は , 限れば , スタックを明示的に使って非再帰 ついて , 終了判定を行います。もし , 最終 異なる手順をたどっても結果として同じ局 て、記述するよりも再帰呼び出しを使ったほ 局面に到達していたら , 解を表示して終了 面にたどり着く場合があり得ます。 うが簡潔な記述になり , また直観的に理解 て、す。最終局面に到達していない場合は , 同一局面を何度も調べると , 効率がよく 局面の集合に未登録て、あることを確認した しやすいプログラムになるのが普通て、す。 ことは我慢するとしても , 無限ループ 話がそれました。幅優先探索にせよ , 深 後 , この局面を集合に追加します。これは , の可能性があります。したがって , 生成し さ優先探索にせよ , 総当たり探索の手法て Fig. 3 て、は , ポインタ Q に示す位置に局面を た局面は記憶しておき , 同一局面が生成さ あるこという点て、一致しています。そして , 挿入して , ポインタ Q をひとつ進めることを れた場合は解の検索対象からは取り除くよ 総当たりを行うためには , n 手目を求めた後 意味します。 うにします。もちろん , 問題の性質上同一 て、 n 十 1 手目を求めるということを繰り返さ 上記の「集合」の操作は , 集合に挿入した 局面が現れないことがわかっている場合は , なければなりません。この求め方を FIFO て、 順番に取り出していることになります。 このチェックは必要ありません。 行うか , LIFO て、行うかて、 , 幅優先と深さ優 のような操作を FIFO(First-In-First-Out, こて , 今まて、説明したことを元に , 幅 先入れ先出し ) と呼び , FIFO の性質を持っ 先とに区別されるのて、す。このように系統 優先探索の概略アルゴリズムを疑似コード データ構造を「待ち行列」 ( queue , キュー ) と 的に整理すると , 理解や記憶がしやすくな として List 1 に示します。 List 1 に出てくる 呼びます。待ち行列は , その名のとおり , ります。 内容は今まて、説明してきたことばかりて、す 銀行の窓口などて , ( 原則的には ) 到着した しかしながら , 原理的によく似ていると から , 意味を理解することは難しくないと 順に呼び出されることから生まれた呼び方 いっても現実には少なからぬ違いが生じま 思いますが , 実装上工夫を要する部分があ す。というのは , 幅優先探索の場合 , 前述 て、す。 ります。それは , リスト上て、「局面の集合」 一方 , 待ち行列と対になるデータ構造は のように重複局面のチェックをしなければ と表現した部分て、す。幅優先探索の処理の ならないからて、す。このチェックのために 「スタック」て、す。スタックの操作は , 最後 大部分が , この「局面の集合」に対する処理 幅優先探索を行うには過去に検討した局面 に追加されたデータが最初に取り出される てすから , この部分の効率いかんて、 , アル のて、 , LIFO (Last-In-First-Out, 後入れ先 をすべて記憶しておかなければならない ゴリズム全体の効率が左右されることにな 出いと呼ばれます。このスタックは計算機 とから , 記憶容量と演算時間の両方を大量 ります。以下 , 「局面の集合」の実現に適し たデータ構造について検討することにしま やプログラムて、は非常に多用されるデータ に消費します。このため , 幅優先探索て、は , 構造て、す。 これらコンヒ。ュータ資源の消費を極力少な 例をあげましよう。 C 言語の関数は仕事が くする工夫が重要になります。 局面の集合に適した 終わると呼び出し元に帰りますが , この戻 テータ構造 り先は「最後に関数をコールした命令の次の 番地」て、すから , スタックにより戻り先を保 前述のように , 幅優先探索の要点は , n 手 この節て、は , 重複局面のチェックに要す 管しておくことがて、きます。 目まて、の局面をすべて調べたうえて、 , これ 待ち行列とスタックが対をなすデータ構 る記憶容量を極力少なくするための工夫に を元に n 十 1 手目の局面を生成するという部 造て、あることは , 直観的にも理解て、きると ついて解説します。 分にあります。 Fig. 3 にこのようすを図示し 思いますが , これをさらに裏づける事実が 記憶容量を節約するための手法としては , ました。この図は , 3 手目の局面を元に 4 手 以下のふたつの方法が知られています。 あります 0List 1 て、は待ち行列が使われてい 目の局面を生成しているようすを示してい ①記憶する項目の数を減らす ますが , これをスタックに置き換えたとし ます。この図を元に , 幅優先探索の 1 ステッ ます。すると , 「幅優先探索」のアルゴリズ ②一項目に要するメモリサイズを圧縮する プあたりの処理を説明しましよう。 まず①について説明しましよう。 ムが一転して「深さ優先探索」になるのて、す。 まず , List 1 て、 ( A ) とマークした部分 , す 15 パズルなどのゲームて、は , 任意の局面 いままて、深さ優先探索 ( バックトラック ) は なわち「局面の集合からひとっ取り出す」と 再帰的なアルゴリズムとして示してきまし から , それまて、の手順を逆にたどることに 書いた部分の処理は , Fig. 3 の P て、示す局面 たが ,List 1 て、スタックを用いると , 再帰を よって , スタートの状態まて、戻ることがて、 を取り出し , ポイッタ P をひとつ進めること きます。このような性質を持つパズルの場 使わないて、記述て、きます。 に相当します。次に , 今取り出した局面か 約 節 の 量 容 70 C MAGAZINE 1 3 4
List 2 146 : 147 : 148 : 149 : 150 : 151 : 152 : 153 : } 1 5 4 : 156 : 157 : 158 : { 159 : 160 : 161 : 162 : 16 3 : 164 : 166 : 168 : 169 : 170 : 171 : 172 : 173 : 174 : 175 : 1 7 6 : 177 : 178 : 179 : 180 : 181 : 182 : 183 : 1 8 4 : 185 : 1 6 5 : / * して探索していくのて , 手順を求めること 先探索の場合は , 1 手目 , 2 手目・・・・・と並行 のて , 手順の表示は容易て、す。一方 , 幅優 ク ) の場合は解の手順に添って探索を進める 表示方法て、す。深さ優先探索 ( バックトラッ 次に考えなければならないのは , 手順の ラムを作ることにしました。 て , まずはデータ圧縮なしの単純なプログ す。先に紹介した Kernighan らの勧めに従っ 点からは , データ圧縮の必要はなさそうて、 以下て、済む計算になります。メモリ容量の イトの配列て表現したとしても , 5K バイト マス目ひとつに 1 バイトをあてて盤面を 8 バ き方の総数は少ないて、すね。したがって , ては 3 * 6 ! / 4 = 540 通りになります。意外に置 並べる方法は , 6 ! / 4 通りて、すから , トータル 個のヒ。ース ( 空白もピースとして数える ) を ヒ。ースの置き方は 3 通りて、す。そのほかの 6 は横方向にしか移動てきませんから , この なければなりません。上段に置かれた電燈 総数を調べてメモリ所要量の見積もりをし ちてす。このため , まずビースの並べ方の 幅優先探索はとにかくメモリを消費しが / * 最初に戻る * / こに来るのはアルゴリズム上ありえない * / cannot happen (position). Yn") ; fprintf(stderr, exit(l); 1 5 5 : / * ハッシュ表への格納 * / board_t *insert(board-t *P, char *board, BOARD_SIZE) ; memCPY()- 〉 board. board. p->POS-space = SPos; return p; prev; p->prev int SPOS, board-t *prev) / * 盤面をコピーする * / / * 空白の位置をコピー * / / * 直前の局面をコピー * / パズルの解法本体 167 : / * ハッシュ表に登録するとともに、必要であればキューにも格納する * / board-t *insert_and_enqueue(char *board, int spos, board-t *p; ー position(board) : if (empty(*p)) { insert(), board, SPOS, prev) : enQueue(p) : } se i f (p ー f i n i sh-P0 i n t ) { return p; d i spl ay (p) ; prev : p->prev void init-board(void) board_t *prev) / * 盤面の初期化 * / / * ハッシュ表上の位置を返す * / / * 表示する * / / * 前の盤のポインタをセットして * / / * 最終状態か ? * / / * キューにも登録する * / / * 空なら表に登録して * / / * ハッシュ表上の位置を得る * / がやっかいて、す。 にまとめています。具体的には , 重複チェ 終局面に到達したことのチェックをひとつ このプログラムて、は , 重複チェックと最 り気にならないようてす。 はあまり依存しないのて、 , 速度低下はあま ハッシュ表の検索時間は , 表の大きさに てサーチしています。 クニックは用いずに , すべての局面を含め にしたのて , 前節て、紹介した検索省略のテ このように , すべての局面を記憶すること 出しにより正順に戻して表示しています。 られます。このプログラムて、は , 再帰呼び どっていくと , 正解に至る手順が逆順に得 タを入れておくことにしました。これをた す構造体の中に「直前の局面」を示すポイン ておくことがて、きます。そこて、 , 局面を示 数が少ないため , 途中経過をすべて記憶し たまたまビースチェンジの場合は局面の 186 : 187 . 188 : 1 8 9 : 190 : 191 : 192 : 193 : 1 9 4 : 1 9 5 : 1 9 6 : 1 9 7 : 199 : 200 : 201 : 202 : 203 : 204 : 2 ℃ 5 : 206 : } 207 : 208 : 209 : 210 : 211 : 2 1 2 : 213 : 214 : 215 : 2 1 6 : 2 18 : 219 : static char start[BOARD_SIZE] = {LIGHT_L, LIGHT_R, LETT_N, LETT_O, LETT_O, LETT_F, LETT_F, SPACE} : static char finishCBOARD_SIZE] = {LIGHT_L, LIGHT_R, LETT_O, LETT_N, LETT_O, LETT_F, LETT_F, SPACE} ; / * 初期状態をハッシュ表とキューに格納する * / insert(position(finish), finish, 7 , NULL); finish-point / * 最終状態をハッシュ表に格納し、その位置を憶えておく * / insert-and-enqueue(start, 7 , NULL) : 19 8 : / * 長いピース ( 電燈 ) かどうかの判定 : マクロ * / #define is_long_piece(piece) ((piece) VOid swap-pieces(char *board, int spos, int ppos) = boardCsPos] : ニ boardCpPos] : temp; char temp board[sPos] board [PPOS] void moveUp(board-t *aBoard) char boardCBOARD-SIZE] ; int sPos; SPOS aBoard->pos_space; if (sPos 〉 : BOARD_WIDTH) return; = LIGHT_L Ⅱ (piece) = LIGHT_R) / * ピースの入れ替え * / / * ピースを上に動かしてみる * / / * ピースを上に動かせない * / / * スペースが下段だと if (is-long-piece(aBoard->board[sPos + BOARD_WIDTH])) / * 横長だと上に動かせない * / return, svap-pieces(board, sPOS, sPos + BOARD-WIDTH) : / * ピースと空白を入れ替え * / / * 盤面をコピーしてから * / memcpy(board, aBoard->board, BOARD-SIZE) : 74 C M AGAZIN E 1 3 4
実践アルゴリズ解法のテクニック List 2 220 : 221 : 222 : 223 : 224 : { 225 : 226 : 227 : 228 : 229 : 230 : 2 31 : 232 : 233 : 234 : 235 : 236 : 237 : 238 : 239 : 240 : 241 : 242 : 243 : 244 : 245 : 246. 247 : 248 : 249 : s Pos + 2 ) : / * 長いピースは 250 : 2 5 1 . 252 : 253 : 254 : 255 : 256 : 258 : 259 : 260 : 261 : 262 : 263 : 264 : 265 : 266 : 267 : 268 : 269 : 270 : 2 71 : 272 : } 273 : 274 : 275 : 276 : 277 : 278 : 279 : 280 : 2 8 1 : 282 : 283 : 284 : } 285 : 286 : 288 : 289 : 290 : 2 9 1 : 292 : 293 : きれいに解くことがて、きます。 insert-and-enqueue(board, SPOS 十 BOARD-WIDTH, aBoard) ; void moveDovn(board-t *aBoard) return, if (sPos く BOARD-WIDTH) aBoard->pos-space; SPOS int sPos; char boardCBOARD_SIZE] : / * ピースを下に動かしてみる * / / * 横長だと下に動かせない * / / * ピースを下に動かせない * / / * スペースが上段だと if (is-Iong-piece(aBoard- 〉 boardCsPos - BOARD_WIDTH])) return; insert-and_enqueue(board, SPOS ー BOARD_WIDTH, aBoard) : swap-pieces(board, SPOS, SPOS ー BOARD-WIDTH) ; memcpy(board, aBoard- 〉 board, BOARD-SIZE) : void moveLeft(board_t *aBoard) aBoard- 〉 pos_space; SPOS int sPos; char boardCBOARD_SIZE] : / * ピースを左に動かしてみる * / if (sPos % BOARD_WIDTH = BOARD_WIDTH ー 1 ) return; memcpy(board, aBoard->board, BOARD-SIZE) : swap-pieces(board, sPOS, SPOS + 1 ) ; if (board[sPOS] : LIGHT_L) { swap—pieces(board, SPOS 十 1 , sPos + ニ 2 ; } se SPOS 十十 : insert_and_enqueue(board, SPOS, return; i f (sPos % BOARD-WIDTH = SPOS : aBoard—>pos_space; int sPos; char board[BOARD_SIZE] : VO id moveRight(board-t *aBoard) / * スペースが右端だと / * ピースを左に動かせない * / / * 2 升同時に動かす * / aBoard) : / * ピースを右に動かしてみる * / / * ピースを右に動かせない * / / * スペースが左端だと memcpy(board, aBoard->board, BOARD_SIZE) : - 1 , swap_pieces(board, spos = LIGHT_R) { if (boardCsPos] swap-pieces(board, SPOS, spos SPOS } se insert and_enqueue(board, sPos— void main-loop(void) return 0 : main-lo 叩 (): init-board(); init-table(); init-queue(); i n t ma i n ( vo i d ) moveRight(aBoard) : moveLeft(aBoard) ; moveDown(aBoard) ; moveUp(aBoard) : aBoard : deQueue() ; vhile (!queue_is-empty()) board-t *aBoard; aBoard) : { / * キューが空でない間、 SPOS SPOS, / * 幅優先探索の実行 * / / * 盤面の初期化 * / / * ハッシュ表の初期化 * / / * キューの初期化 * / / * 上下左右に動かして次の局面を得る * / / * キューから盤面の状態を取りだし * / ック用のハッシュ表に最終局面をあらかじ め登録しておき , まとめて検索します。最 終局面なのか , 局面の重複なのかは , 表の インデックスにより区別て、きます。一般に 極端に技巧的なプログラムは感心しません が , この程度は常用のテクニックとして許 容範囲といえるて、しよう。テープルサーチ のときによく用いる「番兵」と通じる技法て す。 まとめ ック法ては解きにくい問題があります。「 15 く優れた手法て、すが , それて、もバックトラ バックトラック法は非常に応用範囲が広 これらは幅優先探索によって パズル」や「ヒ。ースチェンジ」などはその典 型例て、すが , Kernighan and Plauger 著 , 木村泉訳 , 「プ 岩波書店 , 1989 年 石畑清著 , 「アルゴリズムとデータ構造」 , [ 参考文献 ] してもよいて、しよう。 の演算部分て 0.1 秒を切ることにチャレンジ 味てすが , 練習の目的てあれば , 表示以外 ます。「実用」上はこれ以上の高速化は無意 ているのて , 十分な処理速度が得られてい が , 処理速度を得るためのポイントは押え 装の部分て、はけっこう手抜きをしています る部分は 0.2 ~ 0.3 秒てす。 List 2 は細かい実 も 1 秒くらいて、 , そのうちパズルを解いてい シンに属する 98 ノート ( 80386SX / 16MHz ) て List 2 の実行時間は , 今となっては低速マ ださい のある方は練習間題として挑戦してみてく らの技法を使うまて、もありませんが , 余裕 して用いたビースチェンジの場合は , これ めの技法をいくつか解説しました。例題と とて、す。このため , メモリ消費を減らすた 幅優先探索の欠点はメモリ消費が多い ログラム書法」 , 共立出版 , 1982 年 実践アルゴリズム戦略 75
List 2 74 : 76 : 77 : / * 78 : 79 : 80 : { 81 : 82 : 83 : 85 : 86 : 88 : 89 : 91 : 92 : 94 : 95 : 96 : 98 : 99 : 100 : 101 . 102 : 103 : 104 : { 106 : 107 : 109 : 1 10 : 1 12 : / * 1 14 : 1 15 : 116 : 1 17 : 1 1 9 : 120 : 121 : 122 : } 1 23 : 12 5 : 12 6 : 12 7 : 128 : 129 : 130 : 131 : 1 32 : 133 : 134 : 135 : } 136 : 137 : 138 : { 1 39 : 140 : 1 41 : 1 4 2 : 143 : 1 4 4 : 1 4 5 : 4 : i く 8 : i + + ) return queue[q-top 十十 ] : 表示表関係のモジュール void display-board(board-t *p, int n) %4dYn ” printf(" dispIayTabIe[p printf("%s ” 0 ; i く 4 ; i + + ) for (i static char *displayTable[] i n t i : / * 盤 1 枚の表示 * / int display-l (board-t *p) for (i printf("%s" printf("YnYn ” ): i nt n : = NULL) return 0 : = display-l(p->prev) : n displ ay-board (P. return n 十 1 : dispIayTableCp init-queue() : 108 : #endif printf("%n%n"); display-l(p); 105 : #ifndef NO_DISPLAY VOid display(board-t *p) / * 手順表示 ( 下請、再帰 ) * / / * 呼出側が、何手目かを帰す * / / * 空なら黙って戻る * / / * 呼出側は 0 手目 * / / * まず自分より前を表示してから * / / * キューを空にして戻る * / / * 表示モード * / / * 手順の表示 * / / * 呼出元の手数を教える / * 自分自身を表示する 実践アルゴリズ路解法のテクニック への応用 「ピースチェンジ」 はプログラムリスト (List 2 ) のコメントを参 グラムの解説は簡略にとどめます。詳しく 誌面が残り少なくなってきたのて、 , プロ 手順を求めるというものて、す。 せて , 下段の状態にするための最少手数の い 0Fig. 6 の上段の状態からピースを移動さ チェンジの説明は Fig. 6 をごらんくださ た「ピースチェンジ」を選びました。ビース ' 91 年 9 月号の「 C マガ電脳クラブ」に出題され こて、は , よりやさしい例題として , 本誌 ピュータて、解くことは時間的に困難て、す。 あまりに多い ( 16 の階乗 ) ため , 通常のコン しかし , 15 パズルは調べるべき局面の数が 俗に「プラパズル」と呼ばれるパズル群てす。 の代表例は , 「 15 パズル」や「箱入り娘」など 紹介しましよう。幅優先探索て、解ける間題 こて、 , 幅優先探索の応用プログラムを 考にしていただくことにして , こては設 ハッシュ表関係のモジュール board-t tabIeCHASH-SIZE] ; board-t *finish-point, void init-table(void) table[i]. pos_space : EMPTY; for ( i : 0 : i く HAS H_S IZE : i + + ) / * ハッシュテープル * / / * 完成状態の格納位置 * / / * ハッシュテープルの初期化 * / / * することで、未使用を表す / * pos ー space に特別な値を格納 * / 124 : / * empty : ハッシュ表の項目が空であるかの判定用マクロ * / #define empty(X) ((X) . pos-space ニ = EMPTY) / * ハッシュ関数 * / int hash(char *board) unsigned x; for (x ニ 0 : i く BOARD_SIZE; return (int)(x % HASH-SIZE); X (x くく 2 ) + board[i]; i 十十 ) / * ハッシュ値の計算 * / / * 元の格納位置を返す / * 同一の盤面が格納ずみであれば、 / * 盤面を格納すべき位置を返す board_t *posi tion(char *board) I, P : p = hash(board) : for (i = 0 : i く HASH-SIZE; return &table[p]; i f ( + + p > = HASH-SIZE) int 十十 i ) if (empty(table[p]) Ⅱ memcmp(table[p]. board, board, BOARD_SIZE) / * ハッシュ表をオーパーしたら * / 計に際して考慮したことを説明します。 Fig. 6 ピースチェンジ体誌 ' 91 年 9 月号より ) ピースチェンジ 今月はスライディングプロックパズルだ。 今月のノヾスル 数の解を求めていただきたい。 動きの途中経過もしつかり書いて , 最少手 だ。何手て完成てきるだろうか。ビースの 2 の状態にしたい。「 NO 」を「 ON 」にするの の状態からビースをすべらせて移動し , Fig. Fig. 1 のようにビースが配置されている。 実践アルゴリズム戦略 0 F F 0 F F 73
現在の位置の要素を削除し , dir が正ならば前へ , るようなコード , たとえば , void f(Plex& a) ・ 負ならば後ろへ進む。 のようなコードを書くことがて、きる。しかし , ほか 日 ex クラス ( 日 ex classes) のほとんどの仮想クラスと同様 , 特定の PIex クラス を使用したほうが , より効率のよいコードを生成て "PIex" は以下の特徴を持った配列てある。 きる。 日 ex は℃ hunk の連結リストとしてインプリメント ・日 ex は任意の上限および下限を持っことがてきる。 されている。各チャンク ( Chunk ) は配列の一部を保 持している。チャンクのサイズは Plex のコンストラ たとえば , ー 10 から 10 まてのインデックスを参照て クタて指定することがて、きる。サイズにはデフォル きるように宣言することがてきる。 トもあり , #define されている ( * 10 ) 。日 ex の成長のし ・日 ex は配列の下限と上限を一要素単位て、動的に拡 かたは , チャンク中の使用されていない領域を使用 張することがてきる。 することがて、きればそれを使用し , そうてない場合 ・とくに初期化あるいは付加された要素のみがアク には , F 日 ex 以外の日 ex て、は , 新しくチャンクをつけ セス可能てある。 ・要素はインデックスてアクセスてきる。インデッ 加えるというものて、ある ( * 11 ) 。日 ex が新しいチャン クを作成したときには , 直ちにチャンク内の各要素 クスの妥当性は常に実行時にチェックされる。 PIe に対してデフォルトのコンストラクタ ( すなわち , 引 x は標準的な配列インデックスをたどるループのち 数を取らないコンストラクタ ) が呼び出される。 Ple ょっとした変形てたどることがてきる。 x が縮小した場合には , チャンク全体が解放されるま ・ Plex の要素は Pix を用いてもアクセスしたり , たど ては各要素のデストラクタが呼び出されない。した ったりすることがてきる。 がって , 副作用のないデフォルトのコンストラクタ ・ P 厄 x から日 ex への代入そのほかの日 ex 全体に関す およびデストラクタを持つ要素に対してのみ , Plex る操作がサポートされている。 を (C 十十の配列と同様に ) 使用するべきてある。 ・ PIex クラスには , プログラマがインデックスやポ 日 ex は配列と同じようにインデックス化して使用 インタ操作の妥当性を容易に検査てきるようなメ ソッドも用意されている。 したりて、きるが , 各要素をたどるためのシンタック スは少々異なる。 PIex はチャンクのリストに要素を ・ PIex は , 論理的に隣接したインデックスをあてに 保持し , かっ , このようなインプリメンテーション するしかないようなアクセスの制限されたデータ がリストに要素を保持し , かっ , 反復 (iteration) や 構造 , たとえば配列によって実現されるスタック やキューのような構造のための「自然な」べースク 参照の局所性を維持するほかの操作を行うときに , 単純な配列を用いてたどる方法に比べて , オーバへ ラスとして働く。 ッドがほとんど生じないようなインプリメンテーシ ・日 ex は擬似総称クラスとしてインプリメントされ ョンがなされている。 Pix を用いてたどる方法もサポ ているため , genclass ユーティリティて生成しな ートしている。たとえば , p が int の日 ex て、あるとき , ければならない ( * 9 ) 。 各要素をたどるために以下のメソッドが使用て、きる。 i く p. fence( ) ・ for (int i=p.low( ) ・ 日 ex には四つのサプクラスが用意されている。 p. next(i) ) use(p [i] ) : ・ F 日 ex は宣言された範囲内でのみ伸縮可能である fo 「 (int i=p. high( ) ・ ・ X 円 ex は範囲外へ動的に伸縮可能である p. prev(i)) use(p [i] ) : ・ RPIex は XPlex と同じであるが , 参照が局所的に 偏っていないようなインデックスを扱うのに優 fo 「 (Pix t=p. first( ) : use(p(i)) ; れている t ! = 0 ; p. prev(t) ) ・ M 日 ex は伸縮のほかに要素の論理的な削除と復 fo 「 (Pix t=p.last( ) : 活を認める use(p(i)) : M 円 ex 以外の日 ex て、は , 十十 i およびーー i はそれぞ これらのクラスは PIex という「抽象的な」クラスの 仮想サプクラスてあるため , どの Plex をも操作てき れ , インデックスによってたどるときに使用される ( * 9 ) Plex ては諸定義の 記述されたファイルく T >. defs. h を必要とするため , こ れも生成しておかねばなら ない。なお、 MS-DOS 上て、 はく T > defs. h てある。この あたりに関して , 本誌 ' 92 年 5 月号の f 寸録ディスクにある ファイルては #include 文の ファイル名が MS-DOS 用 に修正されていない場合が あるため , genclass の使用 に際して注意されたい。 ( * 10 ) デフォルトのサイ ズは定数 DEFAULT INI TIAL CAPACITY ( く T >. defs. h に設定されてい る。 (*11) F 円 e 最初に 宣言した範囲外に揖長て、き ないのて , 新しいチャンク は作成されない。 i > p. ecnef( ) ・ 0 ; p. next(t) ) 図 C MAGAZINE 1 3 4
数もその名前から機能を想像て、きると思う を動的に変化させたいときに便利なのが仮 想キーポードて、ある。 のて、 , 解読はさほど難しくないと思う。 仮想キーボ、一ドは , 異なるキー配置をも マクロの内容はきちんと説明すべきだろ った複数のキーボードを場面に応じて取っ うが , 誌面の関係て、そうもいかないのて、 , かえひっかえつなぎ換えるのに似ている。 ふたつの重要な概念を取りあげて説明する。 実際には仮想キーポードはスタックに積む プロセス ようになっており , キーボ、一ドをスタック にブッシュするといちばん上に置かれ同時 にアクテイプになる。このキーボ、一ドを使 このプロセスは MS ー DOS て、いうプロセス い終わったら , ポップアップする。これに とは別のものて、 , BRIEF 内て、生成された より以前のキーポードが復活する。 り , 消滅したりするプロセスを指している。 キーボ、一ドスタックの操作には次の関数 基本的には一般的なプロセスの概念に近 を使う。 いものだが , 当然ながら並行の機能はない また , 親プロセスへの戻りは子プロセスが スタックに積む 割り付けるには次の関数を使う。 明示的にプロセスを終了する関数を実行す → keyboard push ( ) assign t0 key ( キーの名前 , ることにより実現される。 スタックから取り除く キーで起動される関数 ) → keyboard pop ( ) これは第 1 引数のキーが押されたら , 第 2 今回作成したマクロプログラムて、は , 通 このようにキーの変更をキーポードをハ 引数の関数を起動せよ , という意味になる。 常のソーステキストの編集から LCS を計算 ード的につなぎ換えるような感覚て、行うこ これによりキーとその機能を対応づける。 する MS ー DOS 上のプログラム like. exe を起動 また , キーの名前には < Esc > や < Ctrl > の し , それが見つけた候補シンポルを画面に とがて、きる。 また , 仮想キーポード上に実際にキーを ような具体的なキー表記が使える。 一覧表示する場面て、子プロセスを起動して いる。ユーザがシンポルを選択すると , 子 C プログラム プロセスは元の編集に戻るためにプロセス を終了する。また , プロセス間の情報の受 け渡しは共通変数かファイルを通じて行う。 このマクロて、は共通変数を使っている。 簡単なプロセスのメカニズムて、はあるが , 普通のサプルーチンと異なり , 子プロセス から親プロセスに戻った際 , 再開された親 プロセスの実行環境が自動的に復元される のて、プログラミングが楽になる。 Fig. 7 に具体的なプロセスの切り換えおよ び関連する処理を例て、示す。 仮想キーボード Fig. 7 プロセスの切り換え 編集 find マクロ起動 ・子・ process 親 process like. exe 実行 process ( ) 候補シンホル一覧表示 exit( ) 選択 シンボル置換 return( ) fihd マクロ終了 ↓ List 1 : # i ncl ude く stdio. h> 2 : # i nc lude く ctype. h> 3 : #include く string. h 〉 4 : SYM_LEN 31 5 : #define 6 : #define WINNER MAX_SYM 991 7 : #define 8 : #define AV_LEN 9 : 10 : #define 0 EMPTY 1 1 : #def i ne SYMBOL 1 12 : #define RSV_WD 2 13 : #define OTHER 3 15 : #define BUFF_LEN 2048 ISUSCORE(p) 17 : #define MAX(), b) 18 : #define 19 : #define REHASH(h) 20 : buff[BUFF_LEN] : 21 : Char 23 : struct 24 : i n t lcs; 25 : *symbo I; Char 26 : } best-lcsCWINNER] ; 27 : sym { 28 : struct 29 : unsigned char type; 30 : char *symbo I; : } sym-tableCMAX_SYM] : 32 : sym-buf CMAX-SYM * AV_LEN] ; 33 : Char 34 : Char *max_used ニ sym-buf; 35 : unsigned int 36 : quot; 37 : 38 : FILE / * longest symbol / * retain 10 symbols for output / * number Of unique symbol / * average symbol length / * not used / * variabel, / * word token / * other token / * input buffer (a 〉ニ b ? a: b) ((quot + h) % MAX-SYM) token label. プロセスが切り換えられると , 同時にキ ーの役割りも変わるのが普通て、ある。たと えばソースコードの編集中は RET キーは行 の終わりを表し , キーを押すと編集中のテ キストに CR/LF が挿入される。ところがメ ニューの表示中は RET キーはカーソル行の 選択を意味する。このようにキーの役割り / * best lcs winner / * 1 :reserved word, 2:other * / / * symbol po 引 / * tail points for sym_buf / * share with hash() & REHASH() * / Conference Room 127
「コンパイラを使ってコンバイルする」 と何回かつぶやいてみてください。何回か 自分のロていってみるとだんだん慣れてく るものてす ( ほら , これが「やってみる」てす よ ) 。 今のポイント 今月のポイントては , そのまま覚えてし まうプログラムの例を紹介します。今月は 次のプログラムてす。 List 2 のプログラムを ご覧ください C 言語を学ぶときにいちばんはじめに学ぶ プログラムというのは相場が決っています。 List 2 はあなたのコンビュータの画面に Hello, wo 日 d. と 1 行表示するプログラムて、す ( Fig. 13 ) 。あ なたの C 言語の学習はこのプログラムからス タートします。 まずは List 2 をゆっくり目て、追ってみてく ださい。そう , まずは一字一句を覚えてし まうようなつもりて丁寧に List 2 を観察して ください。あわてずにゆっくりと C のプログ ラムの字面に慣れましよう。 ソースプログラム List 2 は , C 言語の文法に従って書かれた たプログラムてす。しかし ,List 2 はあくま ても紙の上に印刷された文字てしかありま せん。いくらすばらしいプログラムても , コンピュータの上て動作させなくては何の 仕事もしてくれません。そうてすよね。 C 言語の文法に従って書かれたプログラム を , 正確には C のソースプログラムと呼んて います。ソースといっても食べ物にかける ソース (sauce) てはなく , 「源」という意味の ソース (source) てす。 ソースプログラムは演劇やドラマの台本 のようなものてす。台本はそれ自身を読ん てもおもしろいてすが , 本来の目的は役者 が演じるためのものなのてす。それと同じ 工デイタを使ってソースプログラムを作る。 ように , ソースプログラムはそれ自身を読 んてもおもしろいてすが , 本来の目的は , そこに書かれている仕事をコンピュータに させるためのものなのてす。 List 2 をずうっと眺めていても , 勉強には なるかもしれませんが , コンヒ。ュータが動 きだすわけてはありません。以下て、は List 2 をコンピュータの上て、動かすための手順を 説明したいと思います。 List をコンバイルして動かす 実は List 2 は付録ディスクに収録されてい るのて , あなたがエデイタて入力する必要 Ⅱ 0 , v•.orld. B>I t2 ↓ A> SE3 LlST2. C Fig. 14 作業の流れ Fig. 13 List 2 の実行結果 はありません。ただし練習のために入力し てみるのはいいことてすノート 2 て、も同じ プログラムを入力する練習をしました。 こて、はファイル名が , LlST2. C てあるとします。 C 言語の習慣として , ファ イルの学は、 . C クとしておきます。 ート 2 てやったように LSIC-86 Ver. 3.30 試 食版がインストールされていれば , コマン ドラインから , A> LCC LIST2. C と入力するだけてコンパイルが開始される はずてす。 A > 〃の部分は MS ー DOS が表示 しているプロンプトてすから , あなたが入 ↓ A> LCC LlST2. C 実行ファイル LlST2. EXE ↓ A> LIST2 ↓ H 0 , world ↓ コンバイラを使って実行ファイルに変換する。 てきた実行ファイルを実行する。 結果が画面に表示される。
理 ) から取られており , PROLOG て、は論理 うことは苦手てす。 LISP は記号を処理す ール・アレンがパソコン用の BASIC 処理 学が重要な位置を占めています。 1980 年 系を開発し , その後ビル・ゲイツはマイ るためのプログラミング旨そしてさ 「 1 ロロ 代に「第五世代コンピュータ」というプロ らには人工知能を研究するための言語と クロソフト社を創設することになります。 ジェクトが日本の通産省によって興され して用いられています。 マイクロソフト社の BASIC 処理系はこれ たとき , プログラミング言語として使用 Scheme( スキーム ) まてに何度も進化を遂げ , 最近て、はⅥ su されたのがこの PROLOG て、した。 PROL LISP の一種の方言ともいえる言語て最近 alBasic という MS-Windows 対応の BAS とくに注目を浴びているものて、す。 LISP OG は C 言語やほかの言語と考え方を異に IC 処理系も販売しています。 BASIC は C した言語て、あり , 直接比較するのは難し は C 言語に比べると文法はやさしいのて、す 言語に比較すると初心者にも理解しやす が , プログラムが若干読みにくく , また い言語て、す。 い反面 , 大規模なプログラムや効率のよ LISP プログラムの例題も人工知能にまっ COBOL ( コボル ) いプログラムが書きにくいと思われるこ 1959 年にビジネスのためのデータ処理言 わるものが多く , プログラムを理解する とが多いようてす。 凵 SP ( リスプ ) のにその分野て、の知識が必要になること 語としてアメリカて、生まれました。 COB OL はてきるかぎり数式を使わず , 簡単な もあります。またメモリを大量に消費す 1950 年代の終わりころ , マッカーシーに 英語だけて、プログラムを作成することが よって開発されたプログラミング言語て、 るためパソコン上て実用に使える処理系 は多くありません。これから人工知能の て、きるように設計されました。 COBOL と す。 LISP は LISt Processor ( リスト処理 研究をやりたいと考えている方は学んて、 いう名前は Common Business Oriented 系 ) の略称てす。 LISP は記号を処理するた Language ( 共通ビジネス指向言語 ) から取 おくべき言語といえます。 めの言語として開発されました。コンビ PROLOG( プロログ ) られています。 COBOL はほかの言語に比 ュータは数値を扱うのはたいへん得意て べて事務的なデータ処理のためのプログ 1970 年代の終わりに誕生したプログラミ す。人間よりもはるかに高速に計算を行 ラムが書きやすくなっています。 ング言語て、す。 PROLOG という名前は P うことがてきます。しかし , コンヒ。ュー タは日本語や英語という言葉 ( 記号 ) を扱 ROgramming LOGic ( プログラミング論 Part マシンと MS ー DOS 。 C プログ ラミングに絶対必要なこのふた つ以外に , 不可欠なのか言語処 理系と呼ばれるコンバイラとキ ー入力のためのエデイタです。 本章では付録ディスクに収録さ れているコンバイラとエテイタ の使用法を学びます。コンバイ ラとエテイタか使えれは C プロ グラマへの道は拓かれます。 五ロ に体験する上て、必要な , いていただきたい話てすが , 読みものだけ ては退屈してしまいますね。そこて、 , 本章 ・エデイタ ては , 実際に C 言語を体験してみましよう。 ・ C コンパイラ が収録されています。 細かい理屈はさておいて , 実際に C コンパイ 本章ては , まずこれらのソフトウェアを ラをあなたのコンヒ。ュータに組み込んて使 あなたのコンピュータに組み込む方法につ います。 いて説明します。次にエデイタを使ってプ 今月号の付録ディスクには , C 言語を実際 , 長な何をするのか 前章てはコンピュータおよび C 言語を中心 としたプログラミングについての一般的な 話 , 基礎的な話をしました。絶対知ってお 42 C MAGAZINE 1 的 3 4