データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4

**デフォルトの名無しさん** · 2020/01/27(月) 22:28:35.79

【前スレ】
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3
https://mevius.5ch.net/test/read.cgi/tech/1466315249/

【関連スレ】
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

**デフォルトの名無しさん** · 2020/07/27(月) 12:25:50.05

深さ優先探索の計算時間がO(|V| + |E|)と評価されるのはなぜですか？
|V| << |E|だから、O(|E|)でOKな気がします。

**デフォルトの名無しさん** · 2020/07/27(月) 12:40:31.34

わからんけどグラフの連結性を仮定してないのでは

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

>>2
|E| < |V|^2 だぞ

**デフォルトの名無しさん** · 2020/09/22(火) 22:37:15.01

２つの同数の点集合A,Bがあって
１対１対応させたときに対応させた点の距離の和が最小になるような１対１対応を探す効率の良いアルゴリズムってありますか

具体的にはa_i∈A, b_j∈B
i->j : j(i)
Σ_i( distance(a_i,b_j(i)) )←これが最小になるj(i)

**デフォルトの名無しさん** · 2020/09/22(火) 23:17:08.08

二部グラフの最小重み完全マッチングでいけないかな

**デフォルトの名無しさん** · 2020/09/22(火) 23:22:00.48

でいけないかなというか，二部グラフの最小重み完全マッチングと同じかな
それならハンガリアン法とか最小費用流で解けるのでは

**デフォルトの名無しさん** · 2020/09/22(火) 23:31:12.82

ありがとうございます
調べてみます