[過去ﾛｸﾞ] データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
1(1): 転載ダメ©2ch.net [sageteoff] 2016/06/19(日)14:47 ID:5KvSKdL/(1/2) AAS
このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 2
2chｽﾚ:tech
【関連スレ】
3Dアルゴリズム全般
2chｽﾚ:tech
＜集大成＞アルゴリズム大辞典
2chｽﾚ:tech
アルゴリズム総合スレ in ム板
2chｽﾚ:tech
アルゴリズムとデータ構造 - Kaneko Lab.
外部ﾘﾝｸ[html]:www.kkaneko.com
アルゴリズムとデータ構造 - ソースコード探険隊
外部ﾘﾝｸ:www.codereading.com
各種アルゴリズムの C++ による実装 - Spaghetti Source
外部ﾘﾝｸ:www.prefield.com
アルゴリズムとデータ構造 - プログラミングスレまとめ in VIP
外部ﾘﾝｸ[html]:vipprog.net
973(2): 2020/01/13(月)12:21 ID:jqPh5nAm(1/3) AAS
>>971
グラフのサイズが書いてないと答えられないな
974: 2020/01/13(月)13:32 ID:D6MgPK0q(2/4) AAS
>>973
条件不足で申し訳ございません
グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。
お手数お掛け致しますが、よろしくお願いします。
975(1): 2020/01/13(月)13:32 ID:D6MgPK0q(3/4) AAS
>>973
条件不足で申し訳ございません
グラフサイズの制約は特に設けないものとしています。
とりあえずは最大でも100頂点程度で考えています。
お手数お掛け致しますが、よろしくお願いします。
976(1): 2020/01/13(月)17:13 ID:jqPh5nAm(2/3) AAS
>>975
頂点数をn，辺数をmとする
ある頂点uを含んだ最小閉路は頂点uからbfsをすればO(n+m)で求められる（最初にuに戻ってきたときの経路が最小）
あとはすべての頂点に対してこれをして，その中から一番短いものを選べばいいので，全体でO(n(n+m))で求められる
977(1): 2020/01/13(月)22:42 ID:D6MgPK0q(4/4) AAS
>>976
ありがとうございます。
つまり、例えば
各頂点を始点-終点とするダイクストラアルゴリズム処理を行えば良い
ということでしょうか。
978(1): 2020/01/13(月)23:30 ID:jqPh5nAm(3/3) AAS
>>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです
ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します．このグラフ上でuからvの最短距離dを求めます
すると，d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります
グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので，すべての辺に対して上の操作を実行します
その中から一番短いものを選べば，それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です
979(1): 2020/01/15(水)13:45 ID:oHYk5H5Q(1/2) AAS
>>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
外部ﾘﾝｸ:ideone.com
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・？
(グラフは隣接行列で表現)
外部ﾘﾝｸ:ideone.com
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。
980(2): 2020/01/15(水)16:39 ID:Ex9G0OLU(1/4) AAS
>>979
>>971だと辺のコストは1となっているが，実際は辺に1以外のコストがある？
求めたい最小サイクルというのは，使う辺の本数が最小という意味なのか，使う辺の合計コストが最小という意味のどちらなのか
981(1): 2020/01/15(水)21:49 ID:oHYk5H5Q(2/2) AAS
>>980
コストは1だと申し上げましたが、
ダイクストラなので非負であれば求まると思い、汎用性を考えて1以外のコストも付与してみました。
説明不足で申し訳ございません。
982(1): 2020/01/15(水)23:25 ID:Ex9G0OLU(2/4) AAS
>>981
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う
983(1): 2020/01/15(水)23:28 ID:Ex9G0OLU(3/4) AAS
外部ﾘﾝｸ:www.geeksforgeeks.org
これとかわりとそのままだな 重みなしだけど
984(1): 2020/01/15(水)23:56 ID:Ex9G0OLU(4/4) AAS
外部ﾘﾝｸ:www.geeksforgeeks.org
こっちは重み付きのやつ
985(1): 2020/01/18(土)22:58 ID:iLU56BHo(1) AAS
>>983
>>984
ありがとうございます。
コストだけでなく、経路も出力したいのですが、弄ってみてもなかなかうまくいきません...。
986: 2020/01/19(日)12:55 ID:VFlG/sWR(1) AAS
CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。
CLRSって他の本と比べると異常に行間がないですよね。
987: 2020/01/20(月)15:11 ID:+ZQhvd/Y(1) AAS
巨大なsparce行列（ゼロ要素が多い行列）で行列演算やるときデータ構造考えるよね
988(1): 2020/01/20(月)17:27 ID:/b+J8VIk(1/2) AAS
>>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector
楽な実装方法は，グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい
989: 2020/01/20(月)17:28 ID:/b+J8VIk(2/2) AAS
途中で送信してしまった
このときの経路をvetorにいれておけばいい
990(2): 2020/01/25(土)23:49 ID:Q85YRMjK(1) AAS
>>988
正直、C++の知識不足で勉強を頑張ってはいるのですがVectorの使い方がまだ、慣れていません。。。
厚かましいのは重々理解しているのですが、可能であればFind minimum weight cycle in an undirected graphのプログラムを>>988さんなりに改変したものをお教えいただけると幸いです。。。
悪い勉強法とは分かっているのですが、答えというか実装例が無いとなかなか理解できなくて。。。
991: 2020/01/26(日)01:32 ID:63DOpTVc(1) AAS
言語の基本的な部分はさすがによそでやろうや・・・
992: 2020/01/26(日)13:25 ID:eN1PAkvI(1/4) AAS
>>990
外部ﾘﾝｸ:ideone.com
↑一応動きました。
piという変数に経路を覚えさせています。
993: 2020/01/26(日)13:32 ID:eN1PAkvI(2/4) AAS
>>990
piについては、
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、
書いてあります。
994(1): 2020/01/26(日)13:47 ID:eN1PAkvI(3/4) AAS
アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか？
995(1): 2020/01/26(日)16:03 ID:gJO14xRt(1) AAS
>>994
ネット以外だとデータ構造とアルゴリズム好きな人見たことないな
CS系だと機械学習やってるやつが多い
996(1): 2020/01/26(日)16:28 ID:eN1PAkvI(4/4) AAS
>>995
ありがとうございます。
機械学習は非常に流行していますが、勉強するのに面白い分野だとは思えません。
997(1): 2020/01/27(月)12:15 ID:Dkceayzl(1) AAS
DAGの単一始点の最短経路問題を解くアルゴリズムとか
Bellman - Fordのアルゴリズムとかの正しさの証明が非常
に面白いですね。
998: 2020/01/27(月)17:15 ID:Xu7tzl7q(1/3) AAS
>>996
+1
999(1): 2020/01/27(月)17:16 ID:Xu7tzl7q(2/3) AAS
>>997
-1
1000: 2020/01/27(月)17:16 ID:Xu7tzl7q(3/3) AAS
>>999
+1=1000
1001(1): 1001 ID:Thread(1/2) AAS
このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 1317日 2時間 28分 54秒
1002(1): 1002 ID:Thread(2/2) AAS
5ちゃんねるの運営はプレミアム会員の皆さまに支えられています。
運営にご協力お願いいたします。
───────────────────
《プレミアム会員の主な特典》
★ 5ちゃんねる専用ブラウザからの広告除去
★ 5ちゃんねるの過去ログを取得
★ 書き込み規制の緩和
───────────────────
会員登録には個人情報は一切必要ありません。
月300円から匿名でご購入いただけます。
▼ プレミアム会員登録はこちら ▼
外部ﾘﾝｸ:premium.5ch.net
▼ 浪人ログインはこちら ▼
外部ﾘﾝｸ[php]:login.5ch.net
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.185s*