注意！！
- 本ページ自身及び以下のファイルは学外のマシンからは見たり印刷したりすることができません。 学内マシンからアクセスしてください。
- 公開ファイルは、リンクをクリックして表示し、直接ダウンロードすることができるほか、 icho 上でコピーすることもできます（コピー・実行方法）。
- 公開ファイルは EUC コードで書かれています。 表示に文字化けが起きる場合には、文字コードを EUC に設定してください。
- 公開ファイルは、授業履修者は自由に閲覧、コピーすることができます。 しかし無断で外部に持ち出すことは禁止します。
また公開ファイル類の著作権は平賀に属します。- 本ページは随時更新しています。 「再読み込み」によって必ず最新版を取り寄せてください。
公開日 タイトル ファイル名 実行結果 概要 08/04/22 「ハノイの塔」再帰版プログラム hanoi.c ハノイの塔問題を、再帰的に解く基本プログラム 08/04/22 川渡り問題 (1) boat1.c boat1.txt 川渡り問題の簡易版プログラム（深さ優先探索） 08/04/22 川渡り問題 (1-1) boat1x.c boat1x.txt boat1.c のプログラムの改造版： 探索経過をすべて出力する 08/04/22 川渡り問題 (2) boat2.c （boat1 と同じ） boat1.c のプログラムで、構造体配列参照を構造体ポインタ参照に書き換えたもの 08/04/22 川渡り問題 (3) boat3.c （boat1 と同じ） 位置情報をビットマップで表すように変更したもの 08/04/22 川渡り問題 (4) boat4.c boat4.txt 状態ノードをあらかじめ作成・展開したもの（大改造） 08/04/22 川渡り問題 (5) boat5.c boat5.txt スタック・キューを使った縦型・横型探索の実現（探索過程のみ） 08/04/22 川渡り問題 (6) boat6.c （boat4 とほぼ同じ） boat5 を、実行結果を出力するようにしたもの 08/04/22 川渡り問題 (7) boat7.c （boat6 とほぼ同じ） 汎用の探索エンジン (search.c, search.h) を使って boat6.c を書き換えたもの 08/04/22 汎用探索ルーチン search.c
search.h---- 汎用の探索エンジン
説明は search.txt 参照08/04/22 マスの問題（未完成版） crockx.c ---- 探索エンジンを使って「マスの問題」を解くプログラムの未完成版。
リスト中の指示された箇所を穴埋めしてプログラムを完成すること。08/05/20 マスの問題 (0) crock0.c crock0.txt 「マスの問題」について、到達可能な全状態を列挙し、状態空間を表示するプログラム。 08/05/20 マスの問題（完成版） crock1.c crock1.txt 探索エンジンを使って「マスの問題」を横型探索で解くプログラム。 08/05/20 「ハノイの塔」探索版プログラム hanoi1.c
hanoi2.chanoi.txt 汎用の探索エンジン (search.c, search.h) を使って「ハノイの塔」を解くプログラム
hanoi2.c は解の唯一性を使って探索ノード数を少なくしたもの08/06/16 パーセプトロン学習の簡易プログラム(1) per0.c per0.txt パーセプトロン学習の簡易プログラム。
例題（液晶ディスプレイの数字表示パターン）の１つのパターンを学習する。08/06/16 パーセプトロン学習の簡易プログラム(2) per1.c per1.txt per0 をすべての数字について学習し、結果を出力するようにしたもの。 08/06/16 パーセプトロン学習の簡易プログラム(3) per2.c per2.txt 入力・出力のビット列を自由に定義できるやや汎用型のプログラム。 出力形式は per1 と同じ。
per2.txt に例示したのは、表示数字を表す２進数（4 bit 列）を学習させた結果。
% csh % source ~hiraga.yuzuru.gf/public/.cshrc % .... 以下通常のコマンド実行 .... % exit # csh を終了：logout する前に必要
~hiraga.yuzuru.gf/public/AIicho 上で直接ファイルをコピーするには、
% cd ~hiraga.yuzuru.gf/public/AI % cp ファイル名 コピー先のようにしてください。
一般的な注意
- プログラムリストは、8 文字ごとのタブ設定を想定している。
他のタブ設定で表示するとプログラムレイアウトが崩れるので注意。
- 関数宣言の冒頭で：
int fn(x, y) int x, y;のような書き方があるのは旧式の C での書き方で、int fn(int x, int y)と同じこと。 このように仮引数の型宣言を、(...) 内に書くのではなく、 下に分けて書くこともできる（このほうが便利なことも多い）。
なお "int fn(...)" のように書かず、関数値の型 (int) と関数名の間で改行するのは、
大規模なプログラムの場合、関数宣言の位置を検索するのが簡単になるからある。
つまり関数名 fn が行頭にあれば関数宣言、 字下げされたところにあれば関数参照、のように区別できる。
- 一般に
if (value) { if_true; } else { if_false; }のような条件判断において、value の値が 0 でなければ if_true が実行され、 0 であれば if_false が実行される。
つまり条件の真偽は、value が 0 なら偽、それ以外なら真として解釈する。 だから：if (value) .... と if (value != 0) if (!value) ... と if (value == 0)はそれぞれ同じ結果になる。
- 出力文には原則として printf (fprintf) のみを用いた。
putchar, puts などを使ったほうが簡潔な場合にも、 printf に統一するようにした。
これはそのほうが出力文を検索するのが容易なこと、その他いくつかの理由による。- 入出力に日本語コードは原則として用いていない。
そのほうがわかりやすくなるのは確かだが、 日本語入出力にはいくつか問題が生じるため、それを避けた。
プログラムリストのコメントには日本語コードを使ってある。「ハノイの塔」再帰版プログラム (hanoi.c)
- 再帰的な処理の最も基本的な例である。
C のように再帰呼び出しが使える言語（多くのプログラミング言語がそう）では、 再帰的なプログラミングは強力な技法ではあるが、一方で慣れないとわかりにくい面もあろう。- 本問の場合、 「N 枚を移動するには、上の N-1 枚をまず移動し、 円盤 N を移動してからその上に N-1 枚を移動すればよい」 というアイディアがそのまま再帰的プログラムの形に翻訳できる。
- プログラム自体は、これが最短手順であるとか、他の解がないことの保証は与えていない点に注意。
川渡り問題 (1) (boat1.c)
- 状態は、旅人(T)、狼(W)、ヤギ(G)、キャベツ(C) のそれぞれが 左岸（LEFT = 0）、右岸（RIGHT = 1）のいずれにいるかで表す。
NODE 構造体はそれらの値を１つにまとめたものである。- したがって配列 node[] の各々の要素はそれぞれ状態を表す。
配列全体は、実は探索経路を表す。 つまり探索中の経路は、node[0], node[1], node[2], ... という状態の列にあたる。
もし node[n] が目標状態であれば、 node[0], ..., node[n] という状態列が問題の解になる。
- 関数 inhibit(step) は、状態 node[step] が禁止状態であるかどうかを判定する。
禁止状態でなければ 0 が、禁止状態であれば 0 でない値（実際には 1）が値として返される。
禁止状態は：
・T と G とが同じ岸にはおらず、かつ
・W, C の少なくとも一方が G と同じ岸にいる
としてまとめることができる。それを論理式で表せばよい。
- 関数 previous(step) は、 状態 node[step] と同じ状態が node[0], ..., node[step-1] の中にあるかを判定する。
つまり現在の経路中の状態に戻るかのチェックである。 同じ状態に戻るというのは探索としてムダであるだけでなく、 無限ループにはまってしまうので避けなければならない。
なお、これは「現在の経路上」でのチェックであって、 すでに探索した状態のチェックではないことに注意。
また探索経路が長大になると、このような単純なチェック方法は非効率になる （boat4.c 以降を参照）。
- 結果の出力は print_answer(step) が行い、 その下請け手続きとして print_member(step, lr) を用いる。
詳細の説明は省略するので、出力結果とも比較して各自で理解しておくこと。
- 探索の中核部分を実行するのが search(step) である。
search は再帰的呼び出しにより縦型探索（深さ優先探索）を実行する。
探索経路の最先端である状態 node[step] に対し：例えば状態 A において、そこから移動可能な状態が X, Y, Z の３つあったとしよう。
- 目標状態なら、結果を出力して戻る。（final_state, print_answer）
- 禁止状態、すでに通った状態ならこの先の探索を打ち切り、戻る。 （inhibit, previous）
- それ以外の場合、この状態から移動可能な状態に対して、 search を再帰的に呼び出すことによって探索を続行する。
（可能な移動は、T 単独、T と W, G, C のいずれかの最大４通り）search は１つの経路を進めるだけ進むから、これは縦型探索になる。
- まずそのうちの１つ、例えば X に対して search を呼び出す。
- するとその search 呼び出しの中で、さらに search が再帰的に呼び出される。
- 再帰呼び出しが終了するのは、上記のように目標状態に達して探索が成功するか、 禁止状態、以前の状態に至って探索が失敗した場合である。
- これにより、A→X→... という経路のすべてが探索される。
- 最初の X に対する search の呼び出しが戻ってきたら、 以下 Y, Z に対する search も同様に行われる。
なお本プログラムの search は値を返さない（void 型）だが、 探索が成功・失敗のいずれであるかなどの情報を返す関数にすれば、 その情報を利用した処理が行える。
注： search 中の T = 1-T; のような代入文は、 T が 0, 1 の２値をとるという前提のもとでは、 T の値を反転する（0→1, 1→0）という意味である。
- main() ルーチンは、単に初期設定（今の場合、初期状態の作成）を行い、 search を起動するだけである。
川渡り問題 (1-1) (boat1x.c)
- boat1.c のプログラムを改造して、探索経過を逐一表示するようにしたもの。
search 手続きが呼び出されるたびに、渡された状態の内容を表示する。
字下げ及び先頭の数字は、各時点での経路の長さを表す。
本来の結果出力（print_answer）は見づらくなるので行わないようにしてある。- この出力結果を通じてプログラムの動作を理解すること。
同様の経過出力は、プログラムの動作を理解したり、デバッグのために有効である。
ただし、探索空間が巨大だと出力量も巨大になるので注意。川渡り問題 (2) (boat2.c)
- boat1.c のプログラムでは NODE 構造体への参照を、 構造体配列及び添字で行っていたのに対し、ポインタを使う形に変更したもの。 他には本質的な違いはない。
- ポインタ変数は、慣れないうちは使いにくい、理解しにくい、間違えやすいという問題はあるが、 使いこなせるようになれば強力な技法となる （もっともそれでも間違えやすいことには変わりはない）。
したがってムリに使う必要は必ずしもないが、積極的に取り組んでみることも大事ではある。
- ポインタと配列・構造体との関係（ポインタについての基本的知識は前提とする：準備中）
- array[0] と *array とは同じ
- array[i] と *(array+i) とは同じ
- 言い換えると、array が配列変数なら、 array+i はその第 i 要素のアドレスとなる。
つまり array+i と &array[i] は同じアドレスを指す。
- structure->fld は (*structure).fld の略記法
川渡り問題 (3) (boat3.c)
- 状態の表現を、T, W, G, C といった個別の変数にではなく、 全部まとめて１つのビット列として表したもの。
このようなビット列表現を用いると、一般にコンパクトで効率の良い表現・実行が可能になるが、 場合によっては処理が複雑でわかりにくくなるケースもある。
- ビット列の扱いについて
- 16進定数： ビット列の定数値を示すには、16進定数（古くは 8進定数）が便利で、 ビット列との対応は 10進数と違って直接的である。
例： 0x34 = (00110100), 0xfa = (11111010)
ただし、(...) はビット列（2進列）を表す。 本当は 0b00110100 のように直接ビット列が書けたほうがさらに便利なのだが、 標準的な C の文法ではこの記法は存在しない。
- ビット列演算子： 以下はいずれも、ビット列の対応するビット同士の演算
a | b ビット同士の論理和。 例： (0101) | (1001) ⇒ (1101) a & b ビット同士の論理積。 例： (0101) | (1001) ⇒ (0001) a ^ b ビット同士の排他的論理和。 例： (0101) | (1001) ⇒ (1100)
対応するビットが等しければ 0、等しくなければ 1 になる。a >> n ビット列の右シフト。 例： (1101) >> 2 ⇒ (0011)
（ただし上位ビットはすべて 0 とする）a << n ビット列の左シフト。 例： (0101) << 1 ⇒ (1010)
- ビット演算の例
以下では a, b 等は unsigned int (32 bit) の変数とする。 また各ビットは下位から順に、bit 0, bit 1, ..., bit 31 とする。
ビット列を「集合」と見なす場合、各ビットに集合の要素を１つ対応させ、 ビット値が 1 ならその要素が集合に含まれることを、0 なら含まれないことを意味する。
実際には 0xffffffff, (1 << n) 等はあらかじめ定数宣言をしたり、 変数（配列）に格納しておいて利用するほうがよい。
bit n のみ 1、他は 0 であるビット列を作る (1 << n) bit n のみ 0、他は 1 であるビット列を作る (1 << n) ^ 0xffffffff a の bit n が 1 かどうかをチェックする a & (1 << n) （結果が 0 なら bit n は 0、そうでなければ bit n は 1） a の bit n を 1 にする a | (1 << n) a の bit n を 0 にする (a | (1 << n)) ^ (1 << n)
a & ((1 << n) ^ 0xffffffff)a の bit n を反転する a ^ (1 << n) a の全ビットを反転する a ^ 0xffffffff a と b の和集合 a | b a と b の積集合 a & b （これは a に対し、b でフィルタをかけていることにもあたる） a は b の部分集合かのチェック (a & b) == a a の 1 であるビット数を数える for (s=0; a; a >>= 1) s += a & 1; （結果は変数 s に）
- 例えば search 中の pos ^ (T | W) のような式は、 T と W のビットを反転する（ボートで移動する）ことを表す。
- same_side(nd, members) は、ビット列 members で表されるメンバーが、 同じ側の岸にいるかどうか（つまり対応するビットがすべて 0 かすべて 1であること） をチェックしている。
- print_member 中の処理が少しわかりにくい。
C では文字列は文字の配列と同一視され、文字配列名を書くところに文字列定数を書いてもかまわない。
したがって： "ABCD"[0] → 'A', "ABCD"[2] → 'C' などとなる。
プログラム中の "T "[(pos & 1) ^ lr] は、添字の値によって、 文字 'T', ' ' のいずれかを出力する。 添字部分については各自で解読を試みよ。川渡り問題 (4) (boat4.c)
- 状態ノードを、初期化段階で（リンクも含めて）すべて生成したもの。
search の処理が軽くなっている。 そこで行っていたことの大部分が initialize() の中で行われることに注意。
- それに伴い、NODE 構造体の中身も拡張してある。 詳細はプログラムリストを参照のこと。
- このうち link フィールドは、このノードから移動可能なノードへのリンクである。 最大 4 本であることは明らかなので link[4] になっているが、 実際にはこれより少ない。 禁止状態を含めても 4 本あるのは初期・目標状態だけであり、 禁止状態を除けば最大でも 3 本である。 initialize() では禁止状態へのリンクを始めからつながないようにしている。
本数がもっと多い場合、またノードによって本数のバラツキが大きい場合には、 link は固定長の配列ではなく、必要に応じて動的に割り当てたほうがよい。- この結果、search の中では現在のノードの link フィールドでつながったノードを探索すればよい。
また禁止状態は除外してあるので、search の中では、 すでに訪問済みのノードかどうかのチェックだけすればよい。 このチェックも、（boat1-3 のように）現在の経路にあるノードすべてを調べにいく必要はない。 ノードの len フィールドには現在までの探索により、 そのノードに至る最短経路の長さが記されており、 それより経路が長くなるなら探索を続ける必要がないからである。
これは（boat1-3 のように）単に現在の経路にあるノードに戻ったかのチェックだけでなく、 他の経路でもっと短い道筋がないかのチェックにもなっており、より一般性がある。
- 本プログラムのもう１つの特徴は、経路を PATH 構造体を用いたリストで表している点である。 これにより、全探索が終了した時点ですべての解が保存できる （実際にはプログラムではそのことを利用してはいないが）。
これに対し、boat1-3 では目標状態に達した時点で記録されている解に至る経路は、 探索を続けると上書きされて残らない。- 経路のリンクは、目標状態から初期状態まで逆向きにつながれている。 したがって解として出力するときには逆順に書き出さなければならない。
本プログラムではこれを print_step の再帰呼び出しで実現している。 つまり直前のノードを次々たどっていき、先頭（初期状態）に達したところで、 それぞれのノードを書き出しながら呼び出しから戻っていく。- さらに結果の出力は、「移動するボート」も出力に加えることで、 boat1-3 よりは少し凝ったものになっている。
川渡り問題 (5) (boat5.c)
- 再帰呼び出しを使わず、縦型探索（スタック）、横型探索（キュー）を行う。
このプログラムは探索過程（各ステップでのスタック、キューの状態）だけを表示する。
- 探索中のノードは、スタック、キューとも、ポインタ配列 stack に格納する。
- スタック、キューとも、新たに探索すべきノードは stack の末尾に追加する （push(...)）。
- スタックではデータを stack の末尾から順に取り出す （pop()）。
- キューではデータを stack の先頭から順に取り出す （dequeue()）。
その際、データを配列の前方に前詰めしていない。 つまりゴミ集めは行っていない。
キューの先頭位置 head、末尾位置（の１つ先）tail はデータの出入りにしたがって 単調に増加していく（スタックでは head=0 に固定）。- 探索は boat1-4 の search() のような再帰呼び出しを行うのではなく、
次の探索ノードを取り出し、 push() 操作を呼び出す expand_nodes(...) で次の探索ノードを設定するループを回るだけである。
- 縦型探索（depth_first()）では pop() によって、
- 横型探索（breadth_first()）では dequene() によって、
スタック／キューが空になったところ（head == tail）で全探索を終了する。
- stack は NODE 型へのポインタ配列であり、 したがって boat4 のように PATH 型構造体は使っていない。
言い換えると、経路情報は保持していないので、 探索が目標状態に達してもそこに至る経路を復元することはできない。
プログラムの出力は、print_stack(step) によって、 ループの各時点でのスタック／キューの内容を表示するだけである。
川渡り問題 (6) (boat6.c)
- boat5 のプログラムを、結果出力を行うように変更したもの。 出力形式は boat4 と同じ。
- 経路を記録するノード (PATH) は配列に記録し、使い捨て（ゴミ集めはしていない）。
- 本質的には、boat4.c と boat5.c のプログラムの主要部分をつないだだけである。
川渡り問題 (7) (boat7.c)
- 探索エンジンを抽出したプログラム。
内容的には boat6.c と同じだが、探索部分を汎用エンジンに切り替えたもの。- 汎用エンジンを利用するため、node_status 関数を新たに定義し、 また depth_first, breadth_first への呼び出し、 answer_length, answer_path 関数を利用するなどの修正を加えてある。
- 汎用探索エンジンについては 下記参照。
汎用探索エンジン(search.c, search.h)
- 説明は search.txt 参照。
「マスの問題」の探索版プログラム (crock0.c)
- 「マスの問題」の全状態空間探索プログラム（説明準備中）
- 実質的には広さ優先探索（横型探索）を全状態空間に対して行い、 ノードへの最短経路長を求める。
- 出力結果の上半分は探索の様子を示す。
2: o xxxxo xxxxx xoxxx xoxxx xxxxx xxxo | [ 0 12] [12 5] [12 17]上のような出力行で、左端は経路長、間の ox は量り得た量を示す。
左端を 0、以下 1, 2, 3, ... に対応し、最大は両マスの合計値（今の場合、12+17=29）である。
量ることが可能なすべての量を求めたところで実行を終了する。- 下半分は、状態空間を２次元の表で表したもの。
到達可能なノードは輪郭にへばりついている（内側の [5,10] などは到達可能でない）ことが特徴。
「マスの問題」の探索版プログラム (crock1.c)
- 探索エンジンを使って「マスの問題」を横型探索で解くプログラム（レポート解答例）
- 使い方は：
% cc -o crock1 crock1.c # コンパイル % crock1 v A B # 実行v は量りとる水量、A, B が２つのマスの容量。
v, A, B は整数で、v ≦ A, v ≦ B でなければならない。
広さ優先探索（横型探索）を行い、得られた解の経路を出力する。「ハノイの塔」の探索版プログラム (hanoi1.c, hanoi2.c)
- 探索エンジンを使って「ハノイの塔」を探索的に解くプログラム
- hanoi1.c は基本版、hanoi2.c は hanoi1.c の生成する探索ノードのうち、 重複するものなどを抑制したもの。
- 使い方は共通で：
% cc -o hanoi1 hanoi1.c # コンパイル % hanoi1 [-ad] [n] # 実行n はディスクの枚数で、1 以上 10 以下（省略すると n=3 になる）。
デフォールトでは広さ優先探索（横型探索）を行い、 解の経路は出力せず、探索結果の情報（解の数、長さ、探索のために生成したリンクののべ数、 実使用の最大数）を表示する。
-a, -d は実行時オプションで、解の経路を出力する場合には -a を、 深さ優先探索（縦型探索）を行う場合には -d を指定する。
（本問の場合、合流が多いので、縦型探索はかなり効率が悪い。）- hanoi2.c は hanoi1.c が展開する探索ノードのうち、重複するものなどを抑制して 生成数を少なくするようにしたもの。
hanoi.txt にある出力結果を通じて両者を比較せよ。
- 状態の表現は、各ディスクがどの軸にあるかを３進数で表している。 （詳細説明は準備中）
パーセプトロン学習の簡易プログラム(1) (per0.c)
- 単層パーセプトロンの学習を行うプログラム。
例題として、液晶ディスプレイの数字表示パターンの学習を行う。- 出力は１ノードのみで、１つの数字に対する数字パターンの学習・出力を行う。
per0 n として実行すると、数字 n のパターンの重みベクトルを学習し、 その学習過程が表示される。
- 目標とする学習例（正例）に対して正値、他の学習例（負例）に対して非正値の出力が得られるまで、 重みベクトル weight を調整する。
- 学習アルゴリズムは単純パーセプトロン学習で、 正例に対して非正値が出力される場合には正例のパターンベクトルを weight に加え、 負例に対して正値が出力される場合には正例のパターンベクトルを weight から引く。
これをすべての学習例に対して正しい出力が得られるまで繰り返す。 （収束するかどうかのチェックはしていない。）
- per0.txt には実行例として、n=0, 1, 8 の３つの場合が示してある。 実行例で：
0[ 0]: [ 0 1 1 1 1 1 1 1] (+[ 0 1 1 1 1 1 1 1]) 1[ 3]: [ 0 1 1 0 0 1 1 0] (-[ 0 0 0 1 1 0 0 1])のようにあるのは：などを表す。
- 学習例 0 に対する出力値が 0 であり、 右端にある [ 0 1 1 1 1 1 1 1 1] を加えて重みベクトルを修正したこと、
（修正結果が [ 0 1 1 1 1 1 1 1]）- 学習例 1 に対する出力値が 3 であり、 右端にある [ 0 0 0 1 1 1 0 0 1] を引いて重みベクトルを修正したこと
（修正結果が [ 0 1 1 0 0 1 1 0]）