深さ優先探索（再帰なし＆あり）についての解説
- 深さ優先探索について再帰を用いずに実装する方法と再帰を用いるプログラムについて解説します。
- アルゴリズムとデータ構造の授業で深さ優先探索について学んでいますが、教授の教え方があまり理解しにくくて困っています。周りも単位を落としている人が多く、自分も興味があるため理解を深めたいです。
- 深さ優先探索を含むアルゴリズムやデータ構造についてわかりやすいサイトや書籍があれば教えていただけると助かります。
- ベストアンサー
深さ優先探索（再帰なし＆あり）
深さ優先探索で再帰呼び出しを用いないのと用いるプログラムを書く課題がありまして、まだC言語かけだしの自分にはあまりよくわかりません・・・ どこかにわかりやすいサイトとかってありますでしょうか？アルゴリズムとデータ構造という授業をとっているんですが、教授が妙な関西弁でしかも教え方も上手とはいえない感じなので全然理解が深まらず困っています。周りも１４０人中５０人くらい単位落としてるカンジなんです。周りは「あんなんんじゃ取れない」といってあきらめていってるのが大半なんですが自分は興味もありますし、１度落としているだけに今年は絶対単位を取りたいと意気込んでます。 オーダー、マージソート、リスト、スタック、深さ優先探索などアルゴリズム（Cのプログラムでよく書かされます）についてわかりやすいサイトや書籍がありましたら是非おしえてください。
- ken0129
- お礼率30% (12/39)
- C・C++・C#
- 回答数2
- ありがとう数0
- みんなの回答 （2）
- 専門家の回答
質問者が選んだベストアンサー
アルゴリズムの本でわかりやすいのは、 『定本Cプログラマのためのアルゴリズムとデータ構造』 SOFTBANK BOOKS 近藤 嘉雪 (著) です。 私はこのサイトで何回もおすすめしています。 とにかく買うべきです。 深さ優先探索そのものは書いてありませんが、 §6.4「木のなぞり」 §20.1「バックトラック法」 を参考にすればなんとかなると思います。
その他の回答 (1)
- tatsu99
- ベストアンサー率52% (391/751)
C言語による はじめてのアルゴリズム入門 が良いと思います。技術評論社 河西朝雄著 この本は結構わかりやすく書いてあります。
関連するQ&A
- C# 再帰よるスタックオーバーフローについて
VB2008 C# でプログラムしていますが、 プログラムで再帰を多く行わなくてはならず、 スタックオーバーフローが出てしまいます。 スタックオーバーフローを解決するためには、アルゴリズムを変更し、 再帰の回数を減らすしか方法はないのでしょうか？ もしスタックの上限を変更する方法などがありましたら教えてください。 VBは初心者なので、なるべく簡単にお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- クイックソートの再帰呼び出し後の記述について（特に配列の範囲）
アルゴリズムをすこしかじってみているのですが、いきなり躓いてしまいました。詳しい方にお聞きします。クイックソートの再帰呼び出し後のプログラムの記述がよくわかりません。（特に配列の範囲） ＱｕｉｃｋＳｏｒｔ（Ｈｅａｄ，Ｔａｉｌ）というプログラムがあるとします。最初の一連の処理が終わり、再帰呼び出しの部分で、 ＱｕｉｃｋＳｏｒｔ（Ｈｅａｄ，Ｌｅｆｔ－１）という前半部分を指定した再帰呼び出しとＱｕｉｃｋＳｏｒｔ（Ｒｉｇｈｔ＋１，Ｔａｉｌ）という後半部分を指定した再帰呼び出しがされるとします。ここまでは分かるのですが、この再帰呼び出しのプログラムの実行を記述するとなるとどうなるのでしょうか？特に分からないのはこの再帰呼び出しでさらに再帰呼び出しされるＱｕｉｃｋＳｏｒｔのカッコ内の配列の範囲がどのようになるのか、何か特別な記述はされるのかということです。あとソートの必要のないレベルまで来た場合の処理（記述）も分かりません。どなたかご教授願えないでしょうか？
- 締切済み
- その他（プログラミング・開発）
- 【Ｃ言語】再帰が時間がかかる理由について
再帰のプログラムがなぜ時間がかかるのかを詳しく調べています。 アセンブリレベルで見ると、 callに時間がかかるのか？それともpop命令？それとも退避？ 結局、よく分からないまま、 Ｇｏｏｇｌｅ検索して調べています。（まだよくわかってません。） 再帰呼び出しのデメリットは、 スタック領域を大量に消費する、関数呼び出しのオーバーヘッドであること。 この事実はわかりました。 しかしながら、 オーバーヘッドとは具体的に何なのか これを調べています。 どなたか、良いサイト・書籍を知らないでしょうか。 教えてください。
- ベストアンサー
- C・C++・C#
- 非再帰のマージソートについて
非再帰のマージソートを作成しているのですが、 上手いこと出来なくて困っています。 条件として配列の開始と終了のインデックスを指定して、 その間の要素だけをソートしたいのです。 ex： int array[10] = { 9,8,7,6,5,4,3,2,1,0 }; MergeSort( array, 2, 6 ); // array[2]～array[6]をソート for( int i=0; i<10; i++ ) printf( "%d, ", array[i] ); 出力） 9, 8, 3, 4, 5, 6, 7, 2, 1, 0, 以下のサイトで公開されているマージソートを元に 私なりに弄ってはいるのですが、 メモリを壊してしまうようなエラーが頻発して、 どうもうまくいかないのです・・・。 http://besky-works.spaces.live.com/Blog/cns!555CF2E2F9E31C71!557.entry どなたがおわかりの方がいらっしゃれば、 その方法を教えていただければ助かります。
- ベストアンサー
- C・C++・C#
- C#のスタック領域
C#でA*のアルゴリズムを用いたプログラムを作成しています。 しかし、探索範囲によってスタックオーバーフローを起こします。 スタック領域そのものを増やすことはできないのでしょうか？ よろしくお願いします。
- ベストアンサー
- その他（プログラミング・開発）
- 再帰的(リカーシブ)プログラムの説明について。
以下は、再帰的(リカーシブ)プログラムの説明を記載しました。 この説明文でおかしい箇所の添削をお願い出来ないでしょうか？ 宜しくお願い致します。 以下からになります。 再帰的(リカーシブ)プログラムとは、プログラムの中から自分自身を呼び出して実行することを再帰的(リカーシブ)アルゴリズムといい、この形式で再帰呼び出しを行うプログラムのこと。 まずは、再帰的アルゴリズムについて、例を使って説明を行いたい。 主プログラムとサブルーチンaがある。 主プログラムは、文字通り、主(メイン)となるプログラム。 サブルーチンは、主プログラムが呼び出して利用する処理をひとまとめにしたもの。 文字通り、サブとなる処理を行う。 主プログラムには、CALL aという命令が記述されている。 これはサブルーチンaを読み出すという命令。 この再帰的プログラムは、処理が終わったら、読み出された場所に帰っていく。 このため、戻り場所を記憶しておかないと帰る事が出来ない。 この戻り場所を記憶するのが、LIFO方式による記憶領域になる。 LIFO方式の記憶領域だから、スタック領域になる。 スタック領域だから、後入れ先出しで戻り場所を記憶していく。 まずは、1回目の呼び出しとして、主プログラムがサブルーチンaを呼び出している。 1回目の戻り場所を記憶しておく。 次にサブルーチンaを見ると、CALL a、つまり自分自身を読み出している。 これが2回目の読み出し。 このように自分自身を呼び出すことを再帰呼び出しという。 同じプログラムの中で自分自身を読み出しているのだが、コンピューターは、あたかも別のサブルーチンがあるように処理が行われている。 この場合、それぞれの処理で、別の変数を用意しながら処理を行う。 このサブルーチンで処理が終わった場合にも、もとに戻る必要がある。 これは2回目の呼び出しになるため、2回目の戻り場所を記憶しておく。 更に、3回目として再びサブルーチンaを呼び出す。 3回目の戻り場所を記憶し、また別の変数を用意しながら処理を行う。 ここで最後のサブルーチンで処理が終わったとする。 処理が終わったら、呼び出された場所に戻る。 戻り場所の記憶を見てみると、上から戻る順番に記録されていることがわかる。 戻り場所はLIFO方式、後入先出しで記録されているから、最後に呼び出した3回目の戻り場所が1番上に記録され、次に2、最後に1が記録されている。 最初は戻り場所を記憶した記憶領域を参照して、3回目に呼び出された場所に戻る。 ここで3の戻り場所が消える。 そして引き続き処理が行われる。 次に、2回目に呼び出した処理が終わり、2回目に呼び出された場所に戻り、2の戻り場所が消える。 また引き続き処理が行われ、1回目に呼び出した処理が終わり、1回目に呼び出された場所(主プログラム)に戻り、1の戻り場所が消える。 そして処理が行われ、プログラム全体が終了する。 このように、プログラムの中で自分自身を呼び出し、戻り場所を記憶しながら実行するようなプログラムを再帰的(リカーシブ)プログラムという。
- ベストアンサー
- その他（プログラミング・開発）
- 再帰呼び出しになってしまうのをループの形にしたい
VBで繰り返して実行するプログラムを作ったのですが、 スタック領域をオーバーしてしまいます。 再帰呼び出しになっているのはわかったのですが、 改善ができません。 簡略したら下記のような状態でした。 Sub test1() test2 End Sub Sub test2() test1 End Sub このtest1を実行して、繰り返し作動するようにしたのですが、 当然スタックオーバーフローになります。 簡単にループに変形できるのでしょうか?
- ベストアンサー
- Visual Basic
- 深さ優先探索について・・・
↓の文を参考にして、深さ優先探索のプログラムを書いてみました。 が、自分（初心者）ではできてるように思えたんですが、全然ダメみたいです。 再帰の使い方がよく分かってないというのもあるのですが（すみません）。 もしよろしければアドバイスを頂けませんか？お願いします！ 『・始点(ここでは「1」)を出発して、番号が小さい順に進む位置を調べていき 行けるところ(辺でつながっていて、まだ未訪問の節点)まで進む。 ・行き場所が無くなったら、行けるところがある節点まで戻っ(再帰をリターンし) て再び進めるだけ進む。 ・行き場所がなくなったなら終了(再帰からリターン) プログラムの際に節点iから節点jへ進めるか否かは節点と枝の関係を表すテーブル(これを隣接行列と言う)の要素a[i][j]の値が1であり、かつ訪問フラグv[j]が0であった時です。 訪問フラグは初期値に0を入れ(未訪問を表す)、 節点jが訪問されたならv[j]に1を入れます』 #include<stdio.h> int recurse(int i,int j); int main(void){ int recurse(int i,int j); return 0; } int recurse(int i,int j){ int v[j]; int a[i][j]; v[j]=0; v[0]=0; a[i][j]={{0,1,1,0,0,0,0,0}, {1,0,0,1,0,0,0,0}, {1,0,0,1,0,0,0,0}, {0,1,1,0,1,0,0,0}, {0,0,0,1,0,1,0,1}, {0,0,0,0,1,0,1,0}, {0,0,0,0,0,1,0,1}, {0,0,0,0,1,0,1,0}}; for(i=0;i<8;i++){ for(j=0;j<8;j++){ if(a[i][j] == 1 && v[j] == 0){ v[j]=1; printf("%d->%d ",i,j); break; } else return 0; } } return 0; }
- ベストアンサー
- C・C++・C#
- return文でもメソッドが止まらない？
いつもお世話になっております。 深さ優先探索をスタックを使わずにJavaで実装したメソッドを書いたのですが なぜかメソッドを終わらせるreturn文まで到達しているようなのに （return直前にメッセージを表示させて到達していることを確認しました） それ以降も動き続けしかも挙動がめちゃくちゃになるという現象に悩まされています。 （かなり長くなってしまっているので実際のプログラムを記載するのは止めます） returnしたら必ずメソッドは処理を終えるものではないのでしょうか？ 思い当たることとしたら、再帰呼び出しを使っているので一つメソッドの処理を終わらせても それを呼び出した側にまた処理が戻っているのかも？ぐらいとしか検討がつきません。 せめてreturnが機能しないことに再帰呼び出しが関係あるのかないのかを知りたいです。 完全にお手上げ状態なのでなにか対処法を知っている方、ぜひともよろしくお願いします。
- ベストアンサー
- Java
- クイックソートで・・・
C言語で再帰を利用してクイックソートを書いたのですが、データ数が大きくなるとプログラムが途中で終了してしまいます。これってスタック領域がなくなってしまったからでしょうか？お願いします。
- ベストアンサー
- C・C++・C#
