データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 http://mevius.5ch.net/test/read.cgi/tech/1580131715/
上
下
前
次
1-
新
通常表示
512ﾊﾞｲﾄ分割
ﾚｽ栞
4: デフォルトの名無しさん [sage] 2020/07/27(月) 15:17:43.62 ID:BQ7JhCRr >>2 |E| < |V|^2 だぞ http://mevius.5ch.net/test/read.cgi/tech/1580131715/4
5: デフォルトの名無しさん [sage] 2020/09/22(火) 22:37:15.01 ID:Ok4HXOVw ２つの同数の点集合A,Bがあって １対１対応させたときに対応させた点の距離の和が最小になるような１対１対応を探す効率の良いアルゴリズムってありますか 具体的にはa_i∈A, b_j∈B i->j : j(i) Σ_i( distance(a_i,b_j(i)) )←これが最小になるj(i) http://mevius.5ch.net/test/read.cgi/tech/1580131715/5
6: デフォルトの名無しさん [sage] 2020/09/22(火) 23:17:08.08 ID:txyi13VO 二部グラフの最小重み完全マッチングでいけないかな http://mevius.5ch.net/test/read.cgi/tech/1580131715/6
7: デフォルトの名無しさん [sage] 2020/09/22(火) 23:22:00.48 ID:txyi13VO でいけないかなというか，二部グラフの最小重み完全マッチングと同じかな それならハンガリアン法とか最小費用流で解けるのでは http://mevius.5ch.net/test/read.cgi/tech/1580131715/7
8: デフォルトの名無しさん [sage] 2020/09/22(火) 23:31:12.82 ID:Ok4HXOVw ありがとうございます 調べてみます http://mevius.5ch.net/test/read.cgi/tech/1580131715/8
9: デフォルトの名無しさん [] 2020/11/08(日) 15:47:31.10 ID:hnEKBOnE 開票所要時間は理論上 O(log n) だよね？ 【米大統領選】日本なら一晩で終わる開票作業 なぜそんなに時間がかかったのか(デイリー新潮) https://news.yahoo.co.jp/articles/e7f705c442fa18c1455c579a7cd209861ef6212b http://mevius.5ch.net/test/read.cgi/tech/1580131715/9
10: デフォルトの名無しさん [sage] 2020/11/08(日) 15:50:45.10 ID:YOqFgelx アルゴリズムで書いたら判定してやるよ http://mevius.5ch.net/test/read.cgi/tech/1580131715/10
11: デフォルトの名無しさん [] 2020/11/08(日) 16:03:50.98 ID:hnEKBOnE 自明なので判定するまでもないが。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/11
12: デフォルトの名無しさん [] 2020/11/08(日) 16:28:09.83 ID:BBDku6LQ データ構造とアルゴリズムって人気ないの？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/12
13: デフォルトの名無しさん [] 2020/11/29(日) 20:21:41.24 ID:rAnHdnpn これの 9.3. Solution が何故これで正解が導き出せるのか理解できないんですが もう少しどなたか詳細に解決して頂けないでしょうか。 https://codility.com/media/train/7-MaxSlice.pdf http://mevius.5ch.net/test/read.cgi/tech/1580131715/13
14: デフォルトの名無しさん [sage] 2020/11/29(日) 21:27:01.68 ID:exnO589A dpテーブル作って考えたほうがわかりやすいと思います https://www.nii.ac.jp/userdata/shimin/documents/H22/100805_3rdlec.pdf これの19ページとか http://mevius.5ch.net/test/read.cgi/tech/1580131715/14
15: デフォルトの名無しさん [] 2020/11/29(日) 21:37:18.71 ID:M8xgBTYt そのPDFファイルに書いてあることの繰り返しになりますが，以下が成り立つからです． max_ending == インデックスがiで終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和 であると仮定する． max_ending = max(0, max_ending+a) を実行した後， max_ending == インデックスがi+1で終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和 が成り立つ． http://mevius.5ch.net/test/read.cgi/tech/1580131715/15
16: デフォルトの名無しさん [] 2020/11/29(日) 22:05:05.40 ID:M8xgBTYt 5, -7, 3, 5, -2, 4, -1 インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceは，3, 5, -2, 4です． インデックスが6で終わるsliceまたは空のsliceのうち，その和が最大であるsliceをSとする． Sは何になるか？ 3 + 5 - 2 + 4 - 1 = 9 > 0なので，Sは空のsliceではありません． Sは，例えば，5, -2, 4, -1ではありません．もし，Sが，5, -2, 4, -1であるとすると， 5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1 したがって， 5 - 2 + 4 > 3 + 5 - 2 + 4 となってしまい，インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceが，3, 5, -2, 4ではなく， 5, -2, 4であるということになってしまうからです． Sは，例えば，-7, 3, 5, -2, 4, -1ではありません．もし，Sが，-7, 3, 5, -2, 4, -1であるとすると， -7 + 3 + 5 - 2 + 4 - 1 > 3 + 5 - 2 + 4 - 1 したがって， -7 + 3 + 5 - 2 + 4 > 3 + 5 - 2 + 4 となってしまい，インデックスが5で終わるsliceまたは空のsliceのうち，その和が最大であるsliceが，3, 5, -2, 4ではなく， -7, 3, 5, -2, 4, -1であるということになってしまうからです． http://mevius.5ch.net/test/read.cgi/tech/1580131715/16
17: デフォルトの名無しさん [sage] 2020/11/29(日) 23:01:49.05 ID:0fgKV2B3 >>13 これ最初から足していってマイナスになったらリセットしてまた足し始める それまでの最大を超えたら最大値を更新するってだけじゃないの マイナスになったらそれを足し続けても得しないって訳だから http://mevius.5ch.net/test/read.cgi/tech/1580131715/17
18: デフォルトの名無しさん [sage] 2020/11/29(日) 23:10:03.18 ID:M8xgBTYt そうですね． 足していってマイナスにならなければ，無いよりはましだから，捨てずにsliceに含め続けるということですね． http://mevius.5ch.net/test/read.cgi/tech/1580131715/18
19: (u＿・y) [sage] 2020/11/30(月) 17:46:41.21 ID:nGWGFXsH そうですよ。マイナスでさえなければ、いないよりはマシだから、あなたも雇われ続けているんです。 さらに2 + 2は必ずしも4ではなく、2 +2 = 80にもなるんです。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/19
20: デフォルトの名無しさん [sage] 2020/12/03(木) 18:30:54.40 ID:Fq1nYucp >>14 分離定理初めて知った、しゅごい まあ算術でとかループでとか、ジャンプと変数があればとか、λさえあれば…とか似たような定理は見掛けたけど、は低レベル過ぎて指針にならんからな これらでできないかひとしきり考えてみることにする (もちろんちゃんと使える演算子は使います) http://mevius.5ch.net/test/read.cgi/tech/1580131715/20
21: デフォルトの名無しさん [sage] 2020/12/22(火) 15:07:11.40 ID:h5DFCbD/ 近似アルゴリズムの本に 極大マッチングは，単に辺を一つずつ選んでいきながら，選んだ辺の両端点とそれらに接続するすべての辺を除いて辺がなくなるまで繰り返すことで得られる とあり，nを頂点の数，mを辺の数としたとき，計算時間がO(n + m)と書いてあるのですが nはどこから来たのでしょうか 両方に点が残っている辺を見ていけばいいのでO(m)でできると思うのですが http://mevius.5ch.net/test/read.cgi/tech/1580131715/21
22: デフォルトの名無しさん [age] 2020/12/31(木) 21:02:35.54 ID:pjMyqahK ArrayListって実装的にはただの可変長配列ですか？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/22
23: デフォルトの名無しさん [sage] 2021/01/01(金) 06:52:59.87 ID:L8CQYPdE >>16 これは、最大連続区間か？ http://mevius.5ch.net/test/read.cgi/tech/1580131715/23
24: デフォルトの名無しさん [sage] 2021/02/27(土) 15:27:53.95 ID:cGuo4IiQ ウィキペディアの焼きなまし法 https://ja.wikipedia.org/wiki/%E7%84%BC%E3%81%8D%E3%81%AA%E3%81%BE%E3%81%97%E6%B3%95 にある擬似コードの if nextE < bestE then の部分はもしかして間違ってたりします？ この評価だとnextEが悪化するたびbestが更新されるように見えますが http://mevius.5ch.net/test/read.cgi/tech/1580131715/24
25: デフォルトの名無しさん [sage] 2021/02/27(土) 16:54:14.85 ID:Hg2wHc/X 小さい方が良いでしょ http://mevius.5ch.net/test/read.cgi/tech/1580131715/25
26: デフォルトの名無しさん [sage] 2021/02/27(土) 16:54:38.59 ID:q6FQGtjh 値が小さい方が望ましい http://mevius.5ch.net/test/read.cgi/tech/1580131715/26
27: デフォルトの名無しさん [sage] 2021/02/27(土) 17:10:02.18 ID:cGuo4IiQ よく読んでなかったすまんかった http://mevius.5ch.net/test/read.cgi/tech/1580131715/27
28: デフォルトの名無しさん [sage] 2021/03/08(月) 16:54:28.07 ID:H4OoIpXQ 焼きなましに例えるんだからEnergyのEだろうね 線形計画法が流行ってた時代はとりあえず目標関数は最大化するものとしてた風潮があった(LPでは双対問題と厳密に等価) シュミレーション分野、最近の機械学習の流行りでとりあえずコスト関数を最小化する雰囲気 LPじゃないんで同じ点で極値を与える関数にも良し悪しがある点には気を付けねば 実数関数なら符号の反転と、並進に依らないアルゴリズムであれば並進を加えたもののみ等価 http://mevius.5ch.net/test/read.cgi/tech/1580131715/28
29: デフォルトの名無しさん [sage] 2021/03/17(水) 19:38:57.60 ID:DuV9YnX6 初歩的な質問かもしれず、恐縮ですがお願いいたします。 i Phoneを使って、端末が始点から終点まで移動した角度をx,y,z（オイラー角）で取得したいと考えています。 最初は、始点と終点の端末の位置をオイラー角で取得し、その差分を出してみたのですが、ジンバルロックによりpitchの値を正確に取得できませんでした。 ジンバルロックを回避するためクォータニオンを使うといいようなのですが、クォータニオンを使って目的の値を算出する方法が分からない状態です。 もし分かる方がおられましたら、ご助言いただると幸いです。 よろしくお願いします。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/29
30: デフォルトの名無しさん [sage] 2021/05/19(水) 16:18:22.70 ID:7NWiu4qI Minimum Mean Cycleでこのスライドを見ているのですが 3ページでmaxをとっているのに正しい答えがでる理由ってなんでですか？ http://www.columbia.edu/~cs2035/courses/ieor6614.S16/mmc.pdf (d^n(v) - d^k(v)) / (n - k)はｖからスタートしたときのMean Cycleですよね d^k(v)が無限の場合を避けるためにmaxをとっていると思うのですが，なぜ正しい答えになるのでしょうか http://mevius.5ch.net/test/read.cgi/tech/1580131715/30
31: デフォルトの名無しさん [sage] 2021/05/22(土) 02:18:16.19 ID:/00w7bM8 >>29 取り敢えず理解はほっといて動けばいいのなら、ウィキペにでも公式載ってたと思うよ http://mevius.5ch.net/test/read.cgi/tech/1580131715/31
32: デフォルトの名無しさん [] 2021/10/03(日) 17:59:42.80 ID:nkudyinT 幅優先探索の計算量がO(N)ではなくO(N + E)なのはなぜ？ Nは頂点の数、Eは辺の数です。 http://mevius.5ch.net/test/read.cgi/tech/1580131715/32
33: デフォルトの名無しさん [sage] 2021/10/03(日) 20:36:41.51 ID:KyHKDHW1 辺の数だけ処理が増えるから 頂点の数を同じにして辺の数が異なる2つのグラフを比較してみればわかる http://mevius.5ch.net/test/read.cgi/tech/1580131715/33
ﾒﾓ帳
(0/65535文字)
上
下
前
次
1-
新
書
関
写
板
覧
索
設
栞
歴
あと 72 ﾚｽあります
ｽﾚ情報
赤ﾚｽ抽出
画像ﾚｽ抽出
歴の未読ｽﾚ
Google検索
Wikipedia
ぬこの手
ぬこTOP
0.007s