データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net

**デフォルトの名無しさん転載ダメ©2ch.net** · 2016/06/19(日) 14:47:29.63

このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。

アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。

　　　　　　　　　　　　　　　　　　京都大学霊長類研究所

データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
http://echo.2ch.net/test/read.cgi/tech/1362301811/

【関連スレ】
3Dアルゴリズム全般
http://toro.2ch.net/test/read.cgi/tech/1164171086/
＜集大成＞アルゴリズム大辞典
http://toro.2ch.net/test/read.cgi/tech/1086272325/
アルゴリズム総合スレ in ム板
http://toro.2ch.net/test/read.cgi/tech/1217773415/

アルゴリズムとデータ構造 - Kaneko Lab.
ttp://www.kkaneko.com/adp/algo/index.html
アルゴリズムとデータ構造 - ソースコード探険隊
ttp://www.codereading.com/algo_and_ds/
各種アルゴリズムの C++ による実装 - Spaghetti Source
ttp://www.prefield.com/algorithm/
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
ttp://vipprog.net/wiki/algo_and_data_const.html

**デフォルトの名無しさん** · 2018/09/11(火) 22:11:28.88

え！？童貞なのにセクロスを！？

**デフォルトの名無しさん** · 2018/09/12(水) 03:44:12.77

できらあ！

**デフォルトの名無しさん** · 2018/09/12(水) 07:05:35.15

それページ逆だぞ

**デフォルトの名無しさん** · 2018/11/05(月) 18:00:44.74

有向グラフの有向閉路を求める問題です。

深さ優先探索を実行したときに、 Backward Edge が存在する。

⇔

有向閉路をもつ

⇒は自明ですが、逆はどう証明するのでしょうか？

**デフォルトの名無しさん** · 2018/12/03(月) 20:50:16.30

深さ優先、幅優先探索を理解するのにオススメの本ってありますか？(コードサンプル付きでできればC)

**デフォルトの名無しさん** · 2018/12/04(火) 09:57:38.19

https://www.amazon.co.jp/dp/4874084141

**デフォルトの名無しさん** · 2018/12/04(火) 10:14:50.08

>>957

全くおすすめできません。その本。

**デフォルトの名無しさん** · 2018/12/04(火) 10:27:11.51

>>956

グラフ・ネットワークアルゴリズムの基礎: 数理とCプログラム
浅野孝夫
固定リンク: http://amzn.asia/d/2MetXvf

**デフォルトの名無しさん** · 2018/12/04(火) 11:20:17.46

馬鹿アスペの推奨ｗ

**デフォルトの名無しさん** · 2018/12/04(火) 14:19:52.12

学ぶ目的には全くお勧めできないってのはその通りだけど、
手元に置いておいて使う分には便利な本ではあるような。
あ、浅野先生の本も待ってます。
(この分野、浅野先生が2人いて紛らわしい)

**デフォルトの名無しさん** · 2018/12/04(火) 14:28:35.23

>>956

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造
渡部有隆
固定リンク: http://amzn.asia/d/g8qmfS6

↑この本にも、 BFS、DFS共に書いてあります。

解説は非常に雑ですが。

**デフォルトの名無しさん** · 2018/12/04(火) 14:33:05.75

>>959

の本には、再帰を使う DFS プログラムが書いてあります。（スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできます。）

**デフォルトの名無しさん** · 2018/12/04(火) 14:34:21.14

>>963

スタックを使う DFS プログラムは演習問題にあり、コードをダウンロードできますし、本にも解答のところにコードが載っています。）

**デフォルトの名無しさん** · 2018/12/04(火) 14:39:02.72

前置記法（ポーランド記法） + 1 2
後置記法（逆ポーランド記法） 1 2 +
中置記法 1 + 2

確か、構文木をたどる時に、どれかが幅優先で、どれかが深さ優先探索になると、記憶している

**デフォルトの名無しさん** · 2018/12/05(水) 13:24:47.73

shaderって何回書き換えてもメモリ壊れない？

**デフォルトの名無しさん** · 2018/12/05(水) 21:47:02.62

テンプレのソース探検なんちゃらのサイトいいね
pdf買えはうざいけど

ソートはクイックマージヒープの特性くらい押さえとけば良さそうな感じだな
そこら中に実装あるしまあ
バケットソートは聞いたこと無かったけど、これは局所で凄い威力発揮しそうだ
覚えとく価値ありそう

**デフォルトの名無しさん** · 2019/06/19(水) 04:49:26.98

【出資】松本卓朗人工知能詐欺【注意】
https://rio2016.5ch.net/test/read.cgi/rikei/1560859403/

**デフォルトの名無しさん** · 2020/01/03(金) 12:48:16.96

O(n)で中央値を求めるアルゴリズムを思いついた

**デフォルトの名無しさん** · 2020/01/04(土) 01:21:11.30

クイックセレクトのこと？

**デフォルトの名無しさん** · 2020/01/13(月) 02:33:48.51

こんにちは、初質問させていただきます、グラフアルゴリズム初心者です

・無向グラフGが入力として与えられる(ファイルからでも、コード内での手打ちでも、どちらも良い)
・Gがサイクルを持てばGの中の最小サイクル(長さが最も短いサイクル)とそのコストを出力する
・各辺、頂点の重みは考えなくても良い(つまり辺のコストは1とする)
といったアルゴリズムを実装したいです。
できればC言語もしくはC系統の言語でコーディングしたいです。

考え方と共に、コーディング例をご教授いただけると幸いです。

浅い知識ではありますが、この実装に必要そうである
・DFS,BFS
・ダイクストラ、ベルマンフォード
に関しては、基礎レベルは把握しています。

お手数おかけしますが、ご助力いただけると幸いです。

**デフォルトの名無しさん** · 2020/01/13(月) 04:31:10.60

適当に言うけど、

すべての辺を1回だけ通りながら、通った頂点を記録していく
それで同じ頂点を、2回以上通ったら、閉路がある？

**デフォルトの名無しさん** · 2020/01/13(月) 12:21:39.99

>>971
グラフのサイズが書いてないと答えられないな

**デフォルトの名無しさん** · 2020/01/13(月) 13:32:08.60

>>973
条件不足で申し訳ございません

グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。

お手数お掛け致しますが、よろしくお願いします。

**デフォルトの名無しさん** · 2020/01/13(月) 13:32:16.76

>>973
条件不足で申し訳ございません

グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。

お手数お掛け致しますが、よろしくお願いします。

**デフォルトの名無しさん** · 2020/01/13(月) 17:13:44.37

>>975
頂点数をn，辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる（最初にuに戻ってきたときの経路が最小）
あとはすべての頂点に対してこれをして，その中から一番短いものを選べばいいので，全体でO(n(n+m))で求められる

**デフォルトの名無しさん** · 2020/01/13(月) 22:42:08.62

>>976
ありがとうございます。

つまり、例えば
各頂点を始点-終点とするダイクストラアルゴリズム処理を行えば良い
ということでしょうか。

**デフォルトの名無しさん** · 2020/01/13(月) 23:30:01.64

>>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです

ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します．このグラフ上でuからvの最短距離dを求めます
すると，d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります

グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので，すべての辺に対して上の操作を実行します
その中から一番短いものを選べば，それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です

**デフォルトの名無しさん** · 2020/01/15(水) 13:45:14.74

>>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ

また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・？
(グラフは隣接行列で表現)
https://ideone.com/snxvav

どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。

すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。

一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する

です。

お手数をおかけしますが、よろしくお願いします。

**デフォルトの名無しさん** · 2020/01/15(水) 16:39:42.37

>>979
>>971だと辺のコストは1となっているが，実際は辺に1以外のコストがある？
求めたい最小サイクルというのは，使う辺の本数が最小という意味なのか，使う辺の合計コストが最小という意味のどちらなのか

**デフォルトの名無しさん** · 2020/01/15(水) 21:49:25.61

>>980
コストは1だと申し上げましたが、
ダイクストラなので非負であれば求まると思い、汎用性を考えて1以外のコストも付与してみました。
説明不足で申し訳ございません。

**デフォルトの名無しさん** · 2020/01/15(水) 23:25:41.19

>>981
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う

**デフォルトの名無しさん** · 2020/01/15(水) 23:28:15.13

https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/
これとかわりとそのままだな　重みなしだけど

**デフォルトの名無しさん** · 2020/01/15(水) 23:56:14.28

https://www.geeksforgeeks.org/find-minimum-weight-cycle-undirected-graph/
こっちは重み付きのやつ

**デフォルトの名無しさん** · 2020/01/18(土) 22:58:37.26

>>983
>>984

ありがとうございます。
コストだけでなく、経路も出力したいのですが、弄ってみてもなかなかうまくいきません...。

**デフォルトの名無しさん** · 2020/01/19(日) 12:55:00.98

CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。

CLRSって他の本と比べると異常に行間がないですよね。

**デフォルトの名無しさん** · 2020/01/20(月) 15:11:46.01

巨大なsparce行列（ゼロ要素が多い行列）で行列演算やるときデータ構造考えるよね

**デフォルトの名無しさん** · 2020/01/20(月) 17:27:30.27

>>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector

楽な実装方法は，グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい

**デフォルトの名無しさん** · 2020/01/20(月) 17:28:22.60

途中で送信してしまった
このときの経路をvetorにいれておけばいい

**デフォルトの名無しさん** · 2020/01/25(土) 23:49:17.89

>>988
正直、C++の知識不足で勉強を頑張ってはいるのですがVectorの使い方がまだ、慣れていません。。。

厚かましいのは重々理解しているのですが、可能であればFind minimum weight cycle in an undirected graphのプログラムを>>988さんなりに改変したものをお教えいただけると幸いです。。。

悪い勉強法とは分かっているのですが、答えというか実装例が無いとなかなか理解できなくて。。。

**デフォルトの名無しさん** · 2020/01/26(日) 01:32:16.02

言語の基本的な部分はさすがによそでやろうや・・・

**デフォルトの名無しさん** · 2020/01/26(日) 13:25:18.52

>>990

https://ideone.com/pShuim

↑一応動きました。
piという変数に経路を覚えさせています。

**デフォルトの名無しさん** · 2020/01/26(日) 13:32:46.65

>>990

piについては、

Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、

書いてあります。

**デフォルトの名無しさん** · 2020/01/26(日) 13:47:50.10

アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか？

**デフォルトの名無しさん** · 2020/01/26(日) 16:03:48.66

>>994
ネット以外だとデータ構造とアルゴリズム好きな人見たことないな
CS系だと機械学習やってるやつが多い

**デフォルトの名無しさん** · 2020/01/26(日) 16:28:11.19

>>995

ありがとうございます。

機械学習は非常に流行していますが、勉強するのに面白い分野だとは思えません。

**デフォルトの名無しさん** · 2020/01/27(月) 12:15:36.42

DAGの単一始点の最短経路問題を解くアルゴリズムとか
Bellman - Fordのアルゴリズムとかの正しさの証明が非常
に面白いですね。

**デフォルトの名無しさん** · 2020/01/27(月) 17:15:29.90

>>996
+1

**デフォルトの名無しさん** · 2020/01/27(月) 17:16:05.01

>>997
-1

**デフォルトの名無しさん** · 2020/01/27(月) 17:16:23.08

>>999
+1=1000

**1001** · Over 1000

このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 1317日 2時間 28分 54秒

**1002** · Over 1000

5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。

───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────

会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。

▼ プレミアム会員登録はこちら ▼
https://premium.5ch.net/

▼ 浪人ログインはこちら ▼
https://login.5ch.net/login.php