隣接行列プログラム

[のん]

隣接行列を使ったグラフ探索のプログラムを作りたいのですが。。
手も足もでません。どなたか助けていただけないでしょうか？？




まずstate.txt
1
2 3

0

といったフォーマットに従った状態空間が記述された
テキストファイルを読み込んで、隣接行列を動的に作成し、
さらにその状態空間をfwrite()を用いてバイナリ形式のファイルにする。

実行時のコマンドラインは次の書式に従う。
> ./MakeGraph テキストファイル(読み込み元）　状態空間(書き込み元）　状態数 [Ente[/url]




もうひとつは、上で作成した状態空間ファイル（バイナリ形式）をmalloc(),fread()を用いて
メモリ上に復元し、経路探索を行う。
ただし、オプション指定で縦型探索と横型探索を切り替えられるようにすること。

実行時のコマンドラインは次の書式に従う。
> ./Search [-bd] 状態空間ファイル　 状態数 　開始状態 　終了状態 [Ente[/url]





ちなみに、
使用例
> ./MakeGraph state.txt state.bin 4 [Ente[/url]
> ./Search -d state.bin 4 1 0 [Ente[/url]
> ./Search -b state.bin 4 3 3 [Ente[/url]
> ./Search -bd state.bin 4 2 0 [Ente[/url]


結果例
1-0 : d : 0 <- 3 <- 1
3-3 : b : 3 <- 1 <- 0 <- 3
2-0 : b : Not Found...
2-0 : d : Not Found...



これらを作るうえでのヒントのようなものもあるのですが、さっぱりで。。

状態空間をファイルから取り込むため、隣接行列で表現した状態空間のサイズは可変、
（たとえば、状態数５ならば、２５個）である。したがって、メモリは動的に確保する必要がある。
また探索時に容易に扱えるようにするため、隣接行列は２次元配列であることが望ましい。
しかし、２次元の動的確保は難易度が高いので、１次元配列の動的確保を応用することで考える。
１次元配列を状態数２個確保し、２点の座標を指定することで、要求する要素へ
アクセスできるマクロCoordinates(x, y, size)を用意する。
このマクロを利用すれば、１次元配列で確保したデータを２次元として扱うことができる。

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

MakeGraph.cとSearch.cは次にあります。
ここにはのせきれなかったので。。

お手数おかけします。

http://mugen.cc.osaka-kyoiku.ac.jp/pg/

[box]

> まずstate.txt
> 1
> 2 3
>
> 0
>
> といったフォーマットに従った状態空間が記述された
> テキストファイル

どういったフォーマットなのか、説明が不十分です。
ファイル中の 1, 2, 3, 空白行 , 0 の各々の意味を説明してください。

[のん]

説明不足でごめんなさい。

これはデータ構造などででてくる有向グラフを隣接行列で示した場合、
スタート地点の状態０から状態１に（０→１）
状態１から状態２と、ゴールの状態３に（１→２、１→３）
ゴールの状態３からスタート地点の状態０に（３→０）

となっていた場合に、状態０～３までのリンク先をあらわしたものです。
単に、机上において、隣接行列で表現すると
　　０　１　２　３

０　０　１　０　０

１　０　０　１　１

２　０　０　０　０

３　１　０　０　０

となります。（線がはいっていないのでややこしいかもしれませんが。。）

これと同じ意味で、


> 1 （状態０のリンク先で、１の直後に￥ｎ）
> 2 3 （状態１のリンク先で、２と３の間に空白、さらに３の後ろに￥ｎ）
> 　　（状態２のリンク先はなにもないので、まっしろ）
> 0 （状態３のリンク先）


となっています。こういう説明で伝わっているかわかりませんが、
よろしくおねがいします！！

[のん]

この問題は今までに出会った中で、一番手ごわく
なんにも進めることができません。。

どなたかお力をお貸しいただけませんでしょうか。。

みなさんにとっても難しいくらいのものと諦めたほうがよいのでしょうか。。

[parapara]

>>この問題は今までに出会った中で、一番手ごわく
>>なんにも進めることができません。。
>>どなたかお力をお貸しいただけませんでしょうか。。
>>みなさんにとっても難しいくらいのものと諦めたほうがよいのでしょうか。。

隣接行列の問題は、僕にとっては簡単でしたよ。box様辺りなら鼻歌交じりで出来そうｗｗｗ。
今は、かつての早稲田塾(現役生のみ＆年間１００万円位)の（東大・東工大）数学クラス(入れるのはごく一部の人だけ)の勘(いつも小テスト一番でした)を取り戻そうとしてるから、自分の事で精一杯なんで、box様辺りに聞いてください。やっぱり、プログラミングより数学の方が俺には得意だった。数学の本はプログラミングの本の３倍の速さで終わらせられる。
すいません、痛い文を書いてしまった。ただ、ここの教えてる人たちは少なくともプログラミングに関しては、俺より遥かに上です。

この文章に対する中傷はやめてください。

[やそ]

数学は超ニガテです（笑）
計算は電卓やＰＣがあれば出来るじゃんってタイプですから（笑）

最近（ここ数年）数学に興味を持ち始め、深夜番組の「コマネチ大学」やＮ○Ｋの「高校講座　数学」などでお勉強中です。

ということで、行列なんてチンプンカンプンでございます。
行列に関する思い出なんてドラクエ３で徹夜で並び、高校受験の当日朝までやっていた記憶しかないです（そんなの関係ねえ！！）

駄文失礼しました。
ツッコミは大歓迎ですが、中傷には耐えられませんので、華麗にスルーでお願いします。

[のん]

みなさんさまざまなコメント、ありがとうございます★
中傷なんてするどころか、なんかすごいなぁって思います。
苦手なんだといっても、余裕が感じられたり、
自分の才能をしっかりと認めているのが、
すごくうらやましい感じです。

box様、お忙しいかもしれませんが、また手があきましたら
コメントのほど、よろしくお願いします★☆

[parapara]

中傷されるの覚悟(自爆テロ)で書いたのに、中傷されなかったので、助け舟を出します。
縦・横型探索はアルゴリズムの本に大抵載っていますので、説明し辛いし、そちらを参考に。
縦・横型探索は本に載ってるよりもかなり改良できるので、頑張ってみてください。
int *Allocate(const int stateSize) {
	return (int *)malloc(sizeof(int)*stateSize*stateSize);
}
int Free(int *graph) {
	int i;
	for(i=(dMatrixSize+1)*(dMatrixSize+1)-1;i>=0;i--){
		free(graph+i);
	}
         return(0);
}
int ReadFile(int *graph, const char *readFileName, const int stateSize) {
	int i,j,n;
	FILE *fpin;
	char buf[4];
	if((fpin=fopen(readFileName,"rb"))==NULL)return(1);
	for(j=0;j<stateSize;j++){
		fgets(buf,stateSize,fpin);
		for(i=0;*(buf+i)!='\n';i++){
			sscanf(buf+i,"%d",&n);
			graph[Coordinates(j, n, stateSize)]=1;
		}
	}
	fclose(fpin);
         return(0);
}
int WriteGraph(const int *graph, char *writeFileName, const int stateSize) {
	int i,j,n;
	FILE *fpout;
	if((fpout=fopen(readFileName,"wb"))==NULL)return(1);
	for(j=0;j<stateSize;j++){
		for(i=0;i<stateSize;i++){
			if(graph[Coordinates(j, i, stateSize)]==1){
				fprintf("%d ",i);
			}
		}
		fprintf(fpout,"\n");
	}
	fclose(fpout);
         return(0);
}
↑こんな感じではないでしょうか？