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