- 締切済み
隣接行列プログラム
隣接行列を使ったグラフ探索のプログラムを作りたいのですが。。 手も足もでません。どなたか助けていただけないでしょうか？？ まずstate.txt 1 2 3 0 といったフォーマットに従った状態空間が記述された テキストファイルを読み込んで、隣接行列を動的に作成し、 さらにその状態空間をfwrite()を用いてバイナリ形式のファイルにする。 実行時のコマンドラインは次の書式に従う。 > ./MakeGraph テキストファイル(読み込み元） 状態空間(書き込み元） 状態数 [Enter] もうひとつは、上で作成した状態空間ファイル（バイナリ形式）をmalloc(),fread()を用いて メモリ上に復元し、経路探索を行う。 ただし、オプション指定で縦型探索と横型探索を切り替えられるようにすること。 実行時のコマンドラインは次の書式に従う。 > ./Search [-bd] 状態空間ファイル 状態数 開始状態 終了状態 [Enter] ちなみに、 使用例 > ./MakeGraph state.txt state.bin 4 [Enter] > ./Search -d state.bin 4 1 0 [Enter] > ./Search -b state.bin 4 3 3 [Enter] > ./Search -bd state.bin 4 2 0 [Enter] 結果例 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/ あとstate.txt のフォーマットは次のようになっています。 これはデータ構造などででてくる有向グラフを隣接行列で示した場合、 スタート地点の状態０から状態１に（０→１） 状態１から状態２と、ゴールの状態３に（１→２、１→３） ゴールの状態３からスタート地点の状態０に（３→０） となっていた場合に、状態０～３までのリンク先をあらわしたものです。 単に、机上において、隣接行列で表現すると ０ １ ２ ３ ０ ０ １ ０ ０ １ ０ ０ １ １ ２ ０ ０ ０ ０ ３ １ ０ ０ ０ となります。（線がはいっていないのでややこしいかもしれませんが。。） これと同じ意味で、 1 （状態０のリンク先で、１の直後に￥ｎ） 2 3 （状態１のリンク先で、２と３の間に空白、さらに３の後ろに￥ｎ） （状態２のリンク先はなにもないので、まっしろ） 0 （状態３のリンク先） となっています。こういう説明で伝わっているかわかりませんが、 よろしくおねがいします！！
- 32i
- お礼率33% (3/9)
- C・C++・C#
- 回答数1
- ありがとう数1
- みんなの回答 （1）
- 専門家の回答
みんなの回答
- Tacosan
- ベストアンサー率23% (3656/15482)
なんというか, state.txt のファイルフォーマットから考え直すべきだと思う. scanf や fgetc などを駆使するか, fgets + strtok (など) で 1行ずつ処理するか, それくらいかなぁ.
関連するQ&A
- 【C++】行列データの読み込み
C++でテキストファイルに以下のようにカンマ区切り（例なのでスペース等でも構いません）で記述された行列を２次元配列に格納する方法が分かりません。 例 1,2,3 4,5,6 7,8,9 よい方法があればご教授願います。
- ベストアンサー
- C・C++・C#
- ファイルから文字列を読み込んで、検索するプログラム
以下のようなプログラムをつくりたいのですが、 どうしたらよいでしょうか？？ 文字列を配列型に入れるときにわからなくなって しまうのですが。。。 ファイルからデータを順番に読み込み，メモリ上に一次元配列構造に並べて線形探索するプログラムを作成せよ． データの仕様 一行に、 「番号（スペース）読み仮名（スペース）文字列（住所）」 があり、これが１０～１０００行ほど、ファイルに（.dat) 入っている。 ファイルを配列に読み込んだあと、 番号を入力すると、住所が検索されてでてくる。 問題文も微妙なのですが、 これは番号の配列と住所の配列は別にして、 検索したほうがいいですよね、、？ 何かヒントになることだけでも良いので、 よろしくお願いします！
- ベストアンサー
- C・C++・C#
- ２次元配列の動的確保について、アドバイス下さい
今、大容量の２次元配列を造りたいので、 メモリの動的確保の勉強をしてました。 昔は、サイズ分mallocで確保して、配列の各行の先頭アドレスを それぞれ対応させていって、行列としてポインタを扱えるようにしてたのですが、 調べていると、もっと簡単に２次元配列のメモリを確保できるみたいなので、その方法を調べていました。 その中で、 if(!(ptr = (int (*)[RETSU])calloc(GYOU*RETSU, sizeof(int)))) こういう例題を見つけたんですけど、 これの、(*)[RETSU])のところが、理解できません。 これは何をしているのでしょうか？ どういう言葉で検索すれば、説明が出てくるのか解らなかったので質問させて頂きました。 この(*)[RETSU]の感じの書き方をすると、結構簡単にメモリ確保できるみたいなので、解説、または説明サイトなど教えて頂けると助かります。 または、例題を書いていただけるとスゴク助かります。 ちなみに私が造りたいのは、 １００行３０００００列 ほどの配列です。 是非、よろしくお願いします。
- 締切済み
- C・C++・C#
- メモリの動的確保（大容量）について
今640*480の画像を、１０枚読み込み、１枚を１行に入れた ２次元配列、10＊307200を作りました。これをXとおきます。 この転置行列、307200＊10と、Xを掛けて、 307200 * 307200 の行列を作りたいです。 その行列の確保に、 xx = (double (*)[307200])malloc(sizeof(double) * 307200 * 307200); とやったところ、 warning C4307: '*' : 整数定数がオーバーフローしました。 というエラーが出てしまいました。 これって、メモリが確保出来ないっていうエラーですよね？ 無知なので教えて頂きたいのですが、 doubleって8バイトなので、この計算だと 8 * 307200 * 307200 = 700G以上のメモリを必要としてしまう。ということでしょうか？ そうだとしたら、やっぱり、こんな容量のメモリを確保するのは無謀ですよね。 でも、この計算はしたいのですが、何か方法はありますでしょうか？
- ベストアンサー
- C・C++・C#
- 困りました。
現在SDKにて画像処理ソフトを作成しています。 そして最近フィルタリングの機能をつけてみようと思いました。 知識として３×３の配列を利用するフィルタ処理で、ラプラシアン、ノイズ除去などを行うやりかた（アルゴリズム）は知っているのですが、配列の確保に問題が出てきました。 プログラムの仕様として、入力画像の輝度情報は入力時にその情報量分のメモリを確保し、ポインタとして格納しています。つまり配列として扱うには１次元配列となってしまいます。もちろん配列をあやつる変数部分を変えるだけで、２次元的な表現はできるのですが、フィルタリング処理をする際複雑になってしまい、コーディングするのが困難になってしまっています。 そこでポインタとしての１次元配列を２次元配列に格納したいのですが、単に格納だけならできるのですが、格納する２次元配列も動的にメモリ確保を行いたいのです。 色々とごちゃごちゃした言い回しになってしまいましたが、第一の問題は２次元配列として扱えるよう動的にメモリを確保したいということです。つまり src[i][j] このように扱えるようメモリを確保したいということです。 以前メモリ確保についてここで質問させてもらいましたが、２次元配列の場合、宣言として (*src)[256] とした場合少なくとも縦が２５６の画像を読み込むことができます。しかしこの場合は”２５６”と決まった量を与えているため記述できるのですが、自分が行いたいのは関数の引数で画像サイズを取得し、その量のメモリを動的に確保したいため、画像サイズに応じて確保するメモリの量が変わってきてしまいます。そのため(*src)[256]と書くことができませんが、しかし自分では確保したメモリ配列を２次元配列として扱いたいため(*src)[256]と書かなければなりません。 つまりこれが壁になっています。 関数の引数で受け取った画像サイズ分のメモリ確保を行い、かつそのメモリ空間をを２次元配列として扱いたい場合、どのように記述すればよいでしょうか？ ひとつ考えたことが **src としてポインタのポインタを使用し、 src = (unsigend char **)GlobalAlloc(GHND, sizeof(unsigned char *) * height); for(i=0; i<height; i++) src[i] = (unsigned char *)GlobalAlloc(GHND, sizeof(unsigned char) * width); for(i=0; i<height; i++){ for(j=0; j<width; j++){ src[i][j] = Input[width * i + j]; } } このように定義してみたんですけど、src[i][j]と記述はできたのですが実行時にエラーが出てしまいました。 なにか効率の良い方法はないでしょうか？
- ベストアンサー
- C・C++・C#
- Jordan標準形にするための正則行列Pをも求めるときは，先にJord
Jordan標準形にするための正則行列Pをも求めるときは，先にJordan標準形を求めてから，逆算してPを求めればよいのですか？ 最小多項式の因子の次数（Jordan細胞の最大サイズ）と，それぞれの固有値に対する固有空間の次元（Jordan細胞の個数）がわかれば，Jordan標準形は一意に決まります．それを用いれば，計算する（Jordan標準形を求めるだけ）のはそこまで大変ではありません．さらにこうやって先にJordan標準形がわかってしまえばそこから逆算して J=P^(-1)AP （J：Jordan標準形，P：ある正則行列） となるようなPを求めることが出来ますよね． そこでなんですが，解法としてはこのような手順で問題はないのでしょうか？ 今までやってきたのは，対角化できる場合のみであって，その場合はそれぞれの固有値に対する固有ベクトルを求めて，それらを並べたものがPにあたるものでした．つまり先に正則行列を求めた上で対角化していました． しかし上の場合は，先に最終的な形を求めてから，そうなるように正則行列を定めています． なんか順番が逆なので，少し疑問に思いました． 今まで通り，先にPを求めてからJを求めたいのですが，その時のPの求め方がよく分からないのです． Jordan標準形になるような場合では，固有ベクトルの本数がn個（n：Aのサイズ）ないので新しくベクトルを作らなくてはなりません． しかし，固有値の重複度によって色々と置き方が変わってきますよね？ なのでうまい方法が分かりません． 逆算すれば出せるのですが，最初からPを作るのは難しいです． やはり先にJordan標準形の形を決めてから正則行列Pを決めるやりかたでもいいのでしょうか？ よろしくお願いします．
- ベストアンサー
- 数学・算数
- テキストファイルを二次元配列に
お世話になります。 テキストファイルを１行ずつ読み込んで二次元配列に格納するプログラムですが、 //最大行数 #define LINE_MAX 10 //行内最大文字数 #define INPUT_MAX 128 char str[LINE_MAX][INPUT_MAX]; というようにして実現しています。 これを行数が分からないテキストファイルでも大丈夫なようメモリを動的に確保したいと考えています。 二つの次元の内、一つを動的に確保するにはどのようにしたら良いでしょうか。
- ベストアンサー
- C・C++・C#
- 3次元配列を２次元配列にする方法はありますか？
3次元配列を２次元配列にする方法はありますか？ すいません、初心者です。 オープンソースとyahooとgoogleのAPIを使って統合型メタ検索エンジンを作っています。 yahooの結果の配列は２次元配列で出せました。 $search_results[$i]["url"] google APIは１回のリクエストで８件までしか呼び出せないみたいなので、 curl_multi関数を使って複数のリクエストを同時に取得しています。 そうしたら結果の配列は三次元配列になりました。 $search_results[$id][$i]["url"] 以下googleの関数です。curl_multiの部分等、文字数の関係で省略しています。 省略した部分のソースは下記リンクにのっています。 http://phpspot.org/blog/archives/2008/02/phpapi.html function search_google($query) { $curls = array(); $search_results = array(); $i=0; $site_results = array( 'http://ajax.googleapis.com/&start=0', 'http://ajax.googleapis.com/&start=8', 'http://ajax.googleapis.com/&start=16', 'http://ajax.googleapis.com/&start=24', 'http://ajax.googleapis.com/&start=32', 'http://ajax.googleapis.com/&start=40', 'http://ajax.googleapis.com/&start=48', 'http://ajax.googleapis.com/&start=56'); foreach($curls as $id=>$c) { $searchs[$id] = curl_multi_getcontent($c);//$cが$site_resultsのリクエスト結果 curl_multi_remove_handle($mh, $c); $json=json_decode($searchs[$id]); if($json->responseStatus != 200){exit();} $responseData = $json->responseData; $results = $responseData->results; for($i=0;$i<count($results);$i++){ $title = $current_result->title; $search_results[$id][$i]["title"]= $title; } } curl_multi_close($mh); return $search_results; } 統合型メタ検索にしたいと考えているのでgoogle配列の変数[$id]同士を結合して yahooの結果と同じく $search_results[$i]["url"] のような二次元配列にしたいのですが、そのようなことは可能ですか？ 本当は両方とも３次元配列にするという処理が適切だと思いますが、初心者がオープンソースを改良して使用しているので、どこを直せば３次元配列のものをうまく表示できるのかわからないのです。 わかりにくかったらすいません。どうか、よろしくお願いします。
- ベストアンサー
- PHP
- オイラー角 回転行列
オイラー角 回転行列 オイラー角について質問させて下さい。 何度も質問して申し訳ないです。 今ひとつ理解できていません。 Z-X-Zオイラー角の回転行列Rｚ・Rx・Rzについて、 「前の2つの回転行列Rｚ,Rxは固定された空間座標回りの 回転ではなく、回転後の新たな座標軸回りの回転を意味する。」 と教えて頂きました。 なぜ前の2つなのでしょうか？最初は元の座標系だから後ろの2 なら分かるのですが・・・ そもそも、なぜオイラー角は一般的に座標系の回転を示すのでしょうか？ 3次元空間（いわゆる私たちが日常過ごしている空間）において、 物体を回転するとき物体その物を回転しますよね？ 座標系を回転する方が物体を回転するよりも 何かメリットがあるのでしょうか？ またジンバルロックについてもご回答頂きました。 ジンバルロックに関してはおおよそ理解しました。 ジンバルロックとは、Z-X-Zオイラー角でRxの回転角度がπや2πのとき、 最初のRzと最後のRzとで回転軸が一致して3つの座標系の回転軸方向 ベクトルのうちRzの2つが線形従属となってオイラー角における任意の3つの 角度を決められない状態。 ジンバルロックを解消するためにクォータニオンと言われる手法があるようです。 ちなみに、このジンバルロックは頻発するように感じるのですが、それでも 回転をオイラー角で表記するのはなぜなのでしょうか？ 素人考えでは最初からクォータニオンを用いれば良いのでは？と思いました。 以上、ご回答何卒よろしくお願い致します。
- ベストアンサー
- 数学・算数
補足
ファイルのフォーマットはもう与えられていて、、 その正直なところfgetsなどの応用がうまく出来なくて困っています。