このスレッドは天才チンパンジー「アイちゃん」が
言語訓練のために立てたものです。
アイと研究員とのやり取りに利用するスレッドなので、
関係者以外は書きこまないで下さい。
京都大学霊長類研究所
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 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
探検
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
レス数が1000を超えています。これ以上書き込みはできません。
2016/06/19(日) 14:47:29.63ID:5KvSKdL/
978デフォルトの名無しさん
2020/01/13(月) 23:30:01.64ID:jqPh5nAm >>977
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです
ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します．このグラフ上でuからvの最短距離dを求めます
すると，d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります
グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので，すべての辺に対して上の操作を実行します
その中から一番短いものを選べば，それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です
イメージとしてはそんな感じです
辺を考えたほうがわかりやすいかもしれないです
ある辺(u-v)を含むようなサイクルの中で最小のものを求めたいとします
まずグラフから辺(u-v)を除去します．このグラフ上でuからvの最短距離dを求めます
すると，d + 辺(u-v)が辺(u-v)を含むサイクルの中で最小のものとなります
グラフの中で一番短いサイクルは辺(u-v)を含んでいるかはわからないので，すべての辺に対して上の操作を実行します
その中から一番短いものを選べば，それがグラフの中で一番短いサイクルです
この場合だとO(m(n+m))です
979デフォルトの名無しさん
2020/01/15(水) 13:45:14.74ID:oHYk5H5Q >>978
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・？
(グラフは隣接行列で表現)
https://ideone.com/snxvav
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。
ありがとうございます。
ご教授いただいた考えをもとに、ダイクストラ法を用いて実装してみました。
・ダイクストラ(グラフは頂点とコストで表現)
https://ideone.com/bXF0iQ
また、以前似たものを実装したのですが、これはダイクストラ(もしくはBFS)の考えに則れていますでしょうか・・・？
(グラフは隣接行列で表現)
https://ideone.com/snxvav
どちらにしても、始点と終点が同一でない場合はうまくいくのですが、
始点と終点を同一として閉路で求めようとすると、うまくいきません。
自己ループ辺のコストが0であるから、と思い9999などにしてみましたが、うまくいきませんでした。
すごく単純なミスなのでしょうが、詰まってしまっている状態です。
修正等いただけると幸いです。
一応、(可能であれば)望む仕様と結果としては
・グラフは隣接行列で表現
・辺の重みは非負である(今回、簡易化のために辺の重みは1~9)
・グラフサイズは制限しない(今回、簡易化のために10頂点程度)
・ダイクストラを用いて自分自身を始点かつ終点とする最短経路を求める
・各頂点に対して上のダイクストラを行い、中でも最短の閉路の経路とそのコストを表示する
です。
お手数をおかけしますが、よろしくお願いします。
980デフォルトの名無しさん
2020/01/15(水) 16:39:42.37ID:Ex9G0OLU981デフォルトの名無しさん
2020/01/15(水) 21:49:25.61ID:oHYk5H5Q982デフォルトの名無しさん
2020/01/15(水) 23:25:41.19ID:Ex9G0OLU >>981
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う
無向グラフだと面倒くさくて，uからvにいったあとvからuにいくような場合がでてくるのでこれを除かないといけない
そのような経路を除いたうえで始点に戻ってきたものが最短になる
ある辺が2回使われることはないので，辺は1度しか使えないようにすればいいと思う
983デフォルトの名無しさん
2020/01/15(水) 23:28:15.13ID:Ex9G0OLU https://www.geeksforgeeks.org/shortest-cycle-in-an-undirected-unweighted-graph/
これとかわりとそのままだな 重みなしだけど
これとかわりとそのままだな 重みなしだけど
984デフォルトの名無しさん
2020/01/15(水) 23:56:14.28ID:Ex9G0OLU985デフォルトの名無しさん
2020/01/18(土) 22:58:37.26ID:iLU56BHo986デフォルトの名無しさん
2020/01/19(日) 12:55:00.98ID:VFlG/sWR CLRSのダイクストラのアルゴリズムの正しさの証明を読み終わりました。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。
CLRSって他の本と比べると異常に行間がないですよね。
行間が全くなく、確かに、正しいことは分かりますが、あまりイメージのわかない証明ですね。
CLRSって他の本と比べると異常に行間がないですよね。
987デフォルトの名無しさん
2020/01/20(月) 15:11:46.01ID:+ZQhvd/Y 巨大なsparce行列（ゼロ要素が多い行列）で行列演算やるときデータ構造考えるよね
988デフォルトの名無しさん
2020/01/20(月) 17:27:30.27ID:/b+J8VIk >>985
どのへんがわからないか言ってくれ
Find minimum weight cycle in an undirected graphは
int Graph :: ShortestPathでu-vを削除したときの最短経路を求めてる
このときdist[v]が更新されるたびにvにきたノードをメモしておけば最後にvからprevをたどって復元できる
このときの経路をvector
楽な実装方法は，グローバル変数にこれまでの最短経路の距離とルートをもっておいて
常に最短のものを保存しておけばいい
どのへんがわからないか言ってくれ
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:22.60ID:/b+J8VIk 途中で送信してしまった
このときの経路をvetorにいれておけばいい
このときの経路をvetorにいれておけばいい
990デフォルトの名無しさん
2020/01/25(土) 23:49:17.89ID:Q85YRMjK991デフォルトの名無しさん
2020/01/26(日) 01:32:16.02ID:63DOpTVc 言語の基本的な部分はさすがによそでやろうや・・・
992デフォルトの名無しさん
2020/01/26(日) 13:25:18.52ID:eN1PAkvI993デフォルトの名無しさん
2020/01/26(日) 13:32:46.65ID:eN1PAkvI >>990
piについては、
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、
書いてあります。
piについては、
Cormen, Leiserson, Rivest, Stein著『Introduction to Algorithms 3rd Edition』の最短路の章を見ると、
書いてあります。
994デフォルトの名無しさん
2020/01/26(日) 13:47:50.10ID:eN1PAkvI アルゴリズムとデータ構造ってコンピューターサイエンスの分野で人気ないんですか？
995デフォルトの名無しさん
2020/01/26(日) 16:03:48.66ID:gJO14xRt996デフォルトの名無しさん
2020/01/26(日) 16:28:11.19ID:eN1PAkvI997デフォルトの名無しさん
2020/01/27(月) 12:15:36.42ID:Dkceayzl DAGの単一始点の最短経路問題を解くアルゴリズムとか
Bellman - Fordのアルゴリズムとかの正しさの証明が非常
に面白いですね。
Bellman - Fordのアルゴリズムとかの正しさの証明が非常
に面白いですね。
998デフォルトの名無しさん
2020/01/27(月) 17:15:29.90ID:Xu7tzl7q >>996
+1
+1
999デフォルトの名無しさん
2020/01/27(月) 17:16:05.01ID:Xu7tzl7q >>997
-1
-1
1000デフォルトの名無しさん
2020/01/27(月) 17:16:23.08ID:Xu7tzl7q >>999
+1=1000
+1=1000
10011001
Over 1000Thread このスレッドは１０００を超えました。
新しいスレッドを立ててください。
life time: 1317日 2時間 28分 54秒
新しいスレッドを立ててください。
life time: 1317日 2時間 28分 54秒
レス数が1000を超えています。これ以上書き込みはできません。
ニュース
- 中国、日本行き“50万人”キャンセル 渡航自粛でコロナ禍以来最大 [お断り★]
- 高市首相答弁を“引き出した”立民・岡田克也氏が改めて説明「なぜ慎重な答弁をされなかったのか。非常に残念に思っている」 ★5 [ぐれ★]
- 【次の一手】台湾問題で小林よしのり氏が私見「まさに戦争前夜」「ただちに徴兵制を敷いて、高市支持者を最前線へ」… ★4 [BFU★]
- 【速報】日本産牛肉の対中国輸出再開協議が中止 ★2 [おっさん友の会★]
- 毛寧（もう・ねい）報道官「中国に日本の水産品の市場は無い」 高市首相の国会答弁に「中国民衆の強い怒り」 [ぐれ★]
- 【外交】前台湾総統・馬英九氏、高市首相発言に「台湾を危険にさらす」台湾海峡の問題は「両岸の中国人が自ら話し合うべき」 [１ゲットロボ★]
- 【ござる専🏡】風間🥷配信実況スレ🏯【風間いろは】
- 【愛国者速報】フィフィ、中国の“日本産水産物輸入停止”措置に私見「中国依存しないとやっていけない企業は考えを改めて」 [856698234]
- 【速報】中国政府、ゲームを禁輸。原神やブルアカ、荒野行動が日本で影響 [347751896]
- Samsungのスマホに削除不可能な情報収集アプリ「AppCloud」(イスラエル製アドウェアらしい)がプリインストールされて物議を醸す [303493227]
- 中国「私達が怒ってるのは日本の政治家に対してで、日本の観光客や日本企業はこれまで通り歓迎する。これこそが大国としての余裕」 [377482965]
- 【悲報】韓国、領土問題担当大臣の発言にソウルの日本大使を召喚して抗議… 高市首相の親韓外交実らず、中国包囲網崩壊へ [452836546]