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

**デフォルトの名無しさん** · 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