****** 汎用探索エンジン・ライブラリ ******

(1) 概要
　・探索エンジン・ライブラリは、深さ優先探索（縦型探索）、広さ優先探索（横型探索）
　　の２種類の汎用探索機能を提供する。
　・見つかった解は、初期状態から目標状態に至る経路として返される。
　・解は（最短解）すべてを求めることもできるし、最初に見つかった１つだけを
　　求めることもできる（縦型探索の場合、これは最短解とは限らない）。

　・状態を表すノードの定義・管理、探索状態の判定、得られた解の出力などの処理は
　　ユーザプログラムの側で用意する。
　　探索エンジン側では状態の内容に立ち入った処理は行わない。
　・ユーザ定義部分を入れ替えることにより、様々な探索型問題に対して
　　共通に使用することができる。

　・詳しい説明は以下の通りだが、これを精読することもさることながら、
　　あるいはそれよりも、直接実例（下のファイル参照）を見たほうが早いし
　　わかりやすいかもしれない。

(2) ファイル
　・search.h	探索エンジンを使用するユーザプログラムのためのヘッダファイル
　・search.c	探索エンジンの本体。
　・boat7.c	例題プログラム：川渡り問題

(3) コンパイルの仕方
　（以下でユーザプログラムのファイル名を ex.c とする。）

　・ex.c はヘッダファイルとして search.h を取り込む必要がある。
　　つまり ex.c の先頭の次の行が必要である。
	#include "search.h"	// search.h は ex.c と同じディレクトリにあるとする。

　　注：stdio.h, stdlib.h は search.h の中で取り込んでいるので、
　　　　ex.c の中で改めて include する必要はない（しても害はない）。

　・ex.c と search.c とは分割コンパイル可能である。
　　したがって：
	% cc -c search.c
　　によってあらかじめ search.o を作っておけば、改めてコンパイルし直す必要はなく：
	% cc -o prog ex.c search.o
　　によって実行プログラムが prog に作られる。
　　これらは次のようにしても結果は同じである。
	1) % cc -o prog ex.c search.c
	2) % cc -c search.c
	   % cc -c ex.c
	   % cc -o prog ex.o search.o

　　make コマンドが使えれば、大きなプログラムのバージョン管理がラクになる。

　・search.c を ex.c の中に直接取り込んでもよい。
　　この場合、ex.c の中に次の行を入れる（このときは search.h を include する必要はない）。
	#include "search.c"

　・search.c の中で、作業用に使うリンク構造の個数は 1000 に設定されている。
　　これより多い／少ない値を設定する場合には、search.c のコンパイルの際に：
	% cc -c -DMAXLINK=10000 search.c
　　のように cc の -D オプションによって設定したい大きさを設定する。

　　上のように search.c を ex.c に include する場合には、include 前に：
	#define	MAXLINK 10000
　　のように値を設定することもできる。


(4) 使い方
 (4-1) 概要（ユーザプログラムが行うことの要約）
　　・関数 int node_status(node, len, nodes) を定義する。
　　　これは各状態ノードに関する情報を返す関数であり（詳細は後述）、
　　　探索エンジンで呼び出される。
　　・探索開始前の、状態ノードの生成・初期値設定
　　・探索の起動：　search 関数を呼び出す。実際には：
	・深さ優先（縦型）：　depth_first(node)
	・広さ優先（横型）：　breadth_first(node)
　　　のいずれかになる。
　　　起動前に指定できるオプションもある（後述）。
　　・状態ノードの内容更新（必要なら）：　これは node_status の中で行う。
　　・探索結果、解を取得し、結果を出力する。
	・解の個数は search 関数が返す。
	・解（最短解）の長さ：　answer_length()
	・n 番目の解（n=1, 2, ...) の経路（ポインタ配列）：　answer_path(n)


 (4-2) 状態ノードのデータ型、準備
　・探索空間の状態ノードは、単一のデータ構造で表す。そのデータ型は普通には構造体、
　　ただし他の型（数値、配列、文字列、ポインタ等）でもよい。
　　探索エンジンではそのデータ型へのポインタによって状態を参照する。

　　　例：「マスの問題」で各マスに入っている水量 A, B 及びその他のフィールドを
　　　　　持つ構造体 NODE で状態を表す。
		struct NODE { int A, B; ... } Nodes[10][10], *node;
		...
		node = &Nodes[i][j];
	　このとき node は構造体配列の Nodes[i][j] を指すポインタ変数であり、
	　そのフィールドは node->A, node->B などによって参照できる。
　　　　
　・探索エンジンはポインタ値の保存、等しいかどうかの比較を扱うだけで、
　　それが指すデータ型の内容にはタッチしない。
　　実はどういうデータ型であるかさえ見ておらず、エンジン内では指示先の型を
　　指定しない (void *) 型で受けている。

　　ユーザは上の点を気にする必要はたぶんないが、データ型不整合の警告メッセージ
　　が出るような場合には以下のように明示的に型キャストを行う。
　　　例：
	struct NODE *node, **next_nodes;
	node_status(node, 2, next_nodes);			// node, next_nodes に型不整合の警告がでる。
	extern node_status((void *)node, int, (void **)next_nodes);	// これで警告が消える。
	nodes = answer_path(n);					// nodes に警告がでる。
	nodes = (struct NODE **)answer_path(n);			// これで警告が消える。

　============================================================================
　・エンジン側では状態ノードの内容にはタッチしないので、それに関わる処理は
　　すべてユーザプログラム側で行う必要がある。具体的には：
　　・ノード自体の割当・生成
　　・各属性値の初期設定、更新
　　・ノード内容に関わる判断（目標状態、禁止状態、既探索ノード等の区別）
	これは node_status 関数によりエンジンに伝える。
　　・ノード内容を踏まえた解の出力
　　・その他

 (4-3) node_status 関数
 　探索エンジンに対して各状態ノードの情報を伝える関数である。
 　関数はユーザ側で定義し、探索エンジンの中で呼び出される。
	int node_status(void *node, int len, void **next_nodes)
	{
		return(...);
	}
　・仮引数
　　　・node	
　　　　現在のノード（を表すデータ構造）へのポインタ。
　　　・len
　　　　node に至る探索経路の長さ。
　　　　（初期状態ノードに対する値は 0 である）。
　　　・next_nodes
　　　　ポインタ配列で、探索エンジンから領域が割り当てられる。
　　　　現ノード node から進みうる子ノードを格納する。
　　　　　例： node の子ノードとして n1, n2, n3 の３つがある：
	　　(node_status の中で）
		next_nodes[0] = n1;
		next_nodes[1] = n2;
		next_nodes[2] = n3;
		return(3);

　・返り値（整数型）
　　　・SUCCESS (=-1)	このノードが目標状態。
			探索は成功終了する（解を記録し、node の子ノードは調べない）。
　　　・FAILURE (=0)	探索が失敗（禁止状態、既訪状態、子ノードがないなど）。
　　　・n (>=1)		子ノードの個数。子ノードへのポインタは next_nodes に設定する。
　　返り値が SUCCESS, FAILURE の場合には next_nodes は意味を持たない
　　（何かを代入しても、エンジン側で無視される）。

　・関数でやるべきこと
　　主な仕事は上記のように、node の内容を判断し、それに応じて返り値を設定することである。
　　　・node が目標状態であれば SUCCESS を返す。（この先の探索は行わない）
　　　・node が禁止状態、すでに探索済みでこれ以上探索を続ける必要がない状態、
　　　　子ノードが１つもない状態であるなら FAILURE を返す。
　　　・上のいずれでもなければ、子ノードを next_nodes に設定し、
　　　　子ノードの個数を返す。

　　しかしそれ以外にも、node の内容その他で更新する必要がある場合には、
　　それらもすべて node_status の中で行う。
　　例えば経路長 len を node 内に記録しておけば、同じ node に至る複数の経路が
　　ある場合、そのうちの最短のものだけ残すことに使える。
　・特に、経路上ですでに通ったノードかどうか（経路にループが生じているかどうか）
　　の判定は、エンジン側で標準的には行っていないので、ユーザプログラム側で
　　チェックする必要がある。
　　ただし、同じポインタ値のノードがすでに経路上にないかを調べるだけの
　　簡単なチェック機能はある。これを有効にするには、探索開始前に大域変数
　　default_check の値を 1 に設定する。
	default_check = 1;	// 上記チェック機能を有効にする。
　　標準的には default_check の値は 0 で、チェック機能は起動されない。
　　（ユーザプログラムでもっと効率的なチェックを行うこともできるので。）

 (4-4) 探索の実行
 　・探索は search 関数を起動することにより実行する。
 　　探索は深さ優先（縦型）探索、広さ優先（横型）探索のどちらかを選べる。
 　　またすべての（最短）解を求める（複数ある場合にはすべて求める）、
 　　最初に見つかった解だけを返すのいずれかも設定できる。
 　　（横型探索では最初の解が最短解（の１つ）でもあるが、縦型探索では
 　　　それが最短解であるとは限らない。）
 　・search 関数には初期状態ノードへのポインタと、探索の型とを引数として与える。
 　　実際にはマクロ定義された次のいずれかを選べばよい。
　　　・深さ優先（縦型）：　depth_first(node)		search(node, DEPTH_FIRST) と同じ
　　　・広さ優先（横型）：　breadth_first(node)		search(node, BREADTH_FIRST) と同じ
 　・最初に見つかる解１個だけを求めるには、大域変数 first_only を 1 に設定する。
	first_only = 1;
 　　そうでなければ first_only == 0 であり、全探索を行う。

 　・search 関数（したがって上記の depth_first, breadth_first マクロ）は返り値として
 　　見つかった解の個数を返す。
 　　　・返り値が 0 なら解は存在しない。
 　　　・first_only == 1 のとき、解が存在すれば返り値は 1 となる。
 　　　・first_only == 0 のとき（デフォールト）、返り値は最短解の個数である。

 　・探索は経路の長さで制御される。
 　　探索中の経路の長さが、それまで得られた最短解の長さより長くなってしまう
 　　場合には、

 (4-5) 解の取得
 　・探索で得られた解の個数を N (>0) とする。これが search の返り値である。
 　・解の長さ（初期状態から目標状態までの経路の長さ） len は：
	len = answer_length();
 　　で得られる。（解が複数個あっても、いずれも最短解なので長さは同じである。）
 　・n 番目の解（n = 1, 2, ..., N）の経路は：
 　　　path = answer_path(n);
 　　で得られる。path はノードポインタ型の配列であり、
 　　　path[0], path[1], ..., path[len]
 　　に経路上のポインタ値が設定される。
 　・したがって解の出力を行うには：
	for (i=0; i<=len; i++) print_node(path[i]);
 　　などとすればよい。
 　　ただし print_node はノードを出力するユーザプログラム定義の関数である。

 　・answer_path が返す配列は一時領域上に確保されるので、
 　　もう一度 answer_path を呼び出すと内容が上書きされてしまう。
 　　経路を保存しておくには、自前の配列にコピーしておく必要がある。
 　　　例：
	struct NODE *answers[MAXANS][MAXLENGTH], **path;
	...
	N = search(...);
	len = answer_length();
	for (i=1; i<=N; i++) {
		path = answer_path(i);
		for (j=0; j<=len; j++) answers[i][j] = path[j];
	}


(5) search.c の内部処理について
　　上記の利用インタフェースさえ心得ていれば、search.c に定義されている
　　探索エンジンの内部処理を知る必要は必ずしもないが、以下に簡単に記しておく。

　・探索経路は struct LINK という構造体に記録する。
	struct LINK *p;
　　とすると：
　　　・p->node		ユーザ定義のノードへのポインタ
　　　・p->len		経路上でのこのノードまでの長さ
　　　・p->next		探索リスト上での次の要素へのポインタ
　　　・p->path		経路上での直前の要素へのポインタ

　・探索の管理は、p->next でつながれた「探索リスト」で行う。
　　リストの先頭要素は head, 末尾要素は tail が指す。
　　・縦型探索の場合、リストの「先頭」に新しい要素を追加し、
　　　処理する要素もリストの先頭から取り出す「スタック型処理」を行う。
　　・横型探索の場合、リストの「末尾」に新しい要素を追加し、処理する要素も
　　　処理する要素はリストの先頭から取り出す「キュー型処理」を行う。

　　・つまり両者の違いは、新しい要素をリストの先頭に追加するか、末尾に
　　　追加するかだけである。
　　　これは関数 newnode の中で処理する。

　　・（以下準備中）