データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
1: 2020/01/27(月)22:28 ID:yq8WVV9K(1) AAS
【前スレ】
データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3
2chｽﾚ:tech
【関連スレ】
3Dアルゴリズム全般
2chｽﾚ:tech
＜集大成＞アルゴリズム大辞典
2chｽﾚ:tech
アルゴリズム総合スレ in ム板
2chｽﾚ:tech
省8
2(1): 2020/07/27(月)12:25 ID:n24uY58k(1) AAS
深さ優先探索の計算時間がO(|V| + |E|)と評価されるのはなぜですか？
|V| << |E|だから、O(|E|)でOKな気がします。
3: 2020/07/27(月)12:40 ID:NergLkg0(1) AAS
わからんけどグラフの連結性を仮定してないのでは
4: 2020/07/27(月)15:17 ID:BQ7JhCRr(1) AAS
>>2
|E| < |V|^2 だぞ
5: 2020/09/22(火)22:37 ID:Ok4HXOVw(1/2) AAS
２つの同数の点集合A,Bがあって
１対１対応させたときに対応させた点の距離の和が最小になるような１対１対応を探す効率の良いアルゴリズムってありますか
具体的にはa_i∈A, b_j∈B
i->j : j(i)
Σ_i( distance(a_i,b_j(i)) )←これが最小になるj(i)
6: 2020/09/22(火)23:17 ID:txyi13VO(1/2) AAS
二部グラフの最小重み完全マッチングでいけないかな
7: 2020/09/22(火)23:22 ID:txyi13VO(2/2) AAS
でいけないかなというか，二部グラフの最小重み完全マッチングと同じかな
それならハンガリアン法とか最小費用流で解けるのでは
8: 2020/09/22(火)23:31 ID:Ok4HXOVw(2/2) AAS
ありがとうございます
調べてみます
9: 2020/11/08(日)15:47 ID:hnEKBOnE(1/2) AAS
開票所要時間は理論上 O(log n) だよね？
【米大統領選】日本なら一晩で終わる開票作業 なぜそんなに時間がかかったのか(デイリー新潮)
外部ﾘﾝｸ:news.yahoo.co.jp
10: 2020/11/08(日)15:50 ID:YOqFgelx(1) AAS
アルゴリズムで書いたら判定してやるよ
11: 2020/11/08(日)16:03 ID:hnEKBOnE(2/2) AAS
自明なので判定するまでもないが。
12: 2020/11/08(日)16:28 ID:BBDku6LQ(1) AAS
データ構造とアルゴリズムって人気ないの？
13(1): 2020/11/29(日)20:21 ID:rAnHdnpn(1) AAS
これの 9.3. Solution が何故これで正解が導き出せるのか理解できないんですが
もう少しどなたか詳細に解決して頂けないでしょうか。
外部ﾘﾝｸ[pdf]:codility.com
14(1): 2020/11/29(日)21:27 ID:exnO589A(1) AAS
dpテーブル作って考えたほうがわかりやすいと思います
外部ﾘﾝｸ[pdf]:www.nii.ac.jp
これの19ページとか
15: 2020/11/29(日)21:37 ID:M8xgBTYt(1/3) AAS
そのPDFファイルに書いてあることの繰り返しになりますが，以下が成り立つからです．
max_ending == インデックスがiで終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
であると仮定する．
max_ending = max(0, max_ending+a)
を実行した後，
max_ending == インデックスがi+1で終わるすべてのsliceの和と空のsliceの和（= 0）のうち最大の和
が成り立つ．
16(1): 2020/11/29(日)22:05 ID:M8xgBTYt(2/3) AAS
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ではなく，
省7
17: 2020/11/29(日)23:01 ID:0fgKV2B3(1) AAS
>>13
これ最初から足していってマイナスになったらリセットしてまた足し始める
それまでの最大を超えたら最大値を更新するってだけじゃないの
マイナスになったらそれを足し続けても得しないって訳だから
18: 2020/11/29(日)23:10 ID:M8xgBTYt(3/3) AAS
そうですね．
足していってマイナスにならなければ，無いよりはましだから，捨てずにsliceに含め続けるということですね．
19: (u＿・y) 2020/11/30(月)17:46 ID:nGWGFXsH(1) AAS
そうですよ。マイナスでさえなければ、いないよりはマシだから、あなたも雇われ続けているんです。
さらに2 + 2は必ずしも4ではなく、2 +2 = 80にもなるんです。
20: 2020/12/03(木)18:30 ID:Fq1nYucp(1) AAS
>>14
分離定理初めて知った、しゅごい
まあ算術でとかループでとか、ジャンプと変数があればとか、λさえあれば…とか似たような定理は見掛けたけど、は低レベル過ぎて指針にならんからな
これらでできないかひとしきり考えてみることにする
(もちろんちゃんと使える演算子は使います)
21: 2020/12/22(火)15:07 ID:h5DFCbD/(1) AAS
近似アルゴリズムの本に
極大マッチングは，単に辺を一つずつ選んでいきながら，選んだ辺の両端点とそれらに接続するすべての辺を除いて辺がなくなるまで繰り返すことで得られる
とあり，nを頂点の数，mを辺の数としたとき，計算時間がO(n + m)と書いてあるのですが
nはどこから来たのでしょうか
両方に点が残っている辺を見ていけばいいのでO(m)でできると思うのですが
22: [age] 2020/12/31(木)21:02 ID:pjMyqahK(1) AAS
ArrayListって実装的にはただの可変長配列ですか？
23: 2021/01/01(金)06:52 ID:L8CQYPdE(1) AAS
>>16
これは、最大連続区間か？
24: 2021/02/27(土)15:27 ID:cGuo4IiQ(1/2) AAS
ウィキペディアの焼きなまし法
外部ﾘﾝｸ:ja.wikipedia.org
にある擬似コードの
if nextE < bestE then
の部分はもしかして間違ってたりします？
この評価だとnextEが悪化するたびbestが更新されるように見えますが
25: 2021/02/27(土)16:54 ID:Hg2wHc/X(1) AAS
小さい方が良いでしょ
26: 2021/02/27(土)16:54 ID:q6FQGtjh(1) AAS
値が小さい方が望ましい
27: 2021/02/27(土)17:10 ID:cGuo4IiQ(2/2) AAS
よく読んでなかったすまんかった
28: 2021/03/08(月)16:54 ID:H4OoIpXQ(1) AAS
焼きなましに例えるんだからEnergyのEだろうね
線形計画法が流行ってた時代はとりあえず目標関数は最大化するものとしてた風潮があった(LPでは双対問題と厳密に等価)
シュミレーション分野、最近の機械学習の流行りでとりあえずコスト関数を最小化する雰囲気
LPじゃないんで同じ点で極値を与える関数にも良し悪しがある点には気を付けねば
実数関数なら符号の反転と、並進に依らないアルゴリズムであれば並進を加えたもののみ等価
29(1): 2021/03/17(水)19:38 ID:DuV9YnX6(1) AAS
初歩的な質問かもしれず、恐縮ですがお願いいたします。
i Phoneを使って、端末が始点から終点まで移動した角度をx,y,z（オイラー角）で取得したいと考えています。
最初は、始点と終点の端末の位置をオイラー角で取得し、その差分を出してみたのですが、ジンバルロックによりpitchの値を正確に取得できませんでした。
ジンバルロックを回避するためクォータニオンを使うといいようなのですが、クォータニオンを使って目的の値を算出する方法が分からない状態です。
もし分かる方がおられましたら、ご助言いただると幸いです。
よろしくお願いします。
30: 2021/05/19(水)16:18 ID:7NWiu4qI(1) AAS
Minimum Mean Cycleでこのスライドを見ているのですが
3ページでmaxをとっているのに正しい答えがでる理由ってなんでですか？
外部ﾘﾝｸ[pdf]:www.columbia.edu
(d^n(v) - d^k(v)) / (n - k)はｖからスタートしたときのMean Cycleですよね
d^k(v)が無限の場合を避けるためにmaxをとっていると思うのですが，なぜ正しい答えになるのでしょうか
31: 2021/05/22(土)02:18 ID:/00w7bM8(1) AAS
>>29
取り敢えず理解はほっといて動けばいいのなら、ウィキペにでも公式載ってたと思うよ
32: 2021/10/03(日)17:59 ID:nkudyinT(1) AAS
幅優先探索の計算量がO(N)ではなくO(N + E)なのはなぜ？
Nは頂点の数、Eは辺の数です。
33: 2021/10/03(日)20:36 ID:KyHKDHW1(1) AAS
辺の数だけ処理が増えるから
頂点の数を同じにして辺の数が異なる2つのグラフを比較してみればわかる
34: 2021/10/03(日)22:55 ID:45cLxSS6(1) AAS
モートン順序によって当たり判定を一瞬で計算するというのがありました
あれ特定の境目の上にオブジェクトがあるとすべてのオブジェクトとの衝突判定が発生するんですが
世の中のゲームってそんなふうにやってるんですか
35: 2021/10/04(月)18:40 ID:N2yAdGNd(1) AAS
計算量がO(V + E)であるの定義は何ですか？
36: 2021/10/04(月)22:35 ID:qkBPKVDO(1) AAS
それは計算量の定義をきいているのか？
37(1): 2021/10/05(火)00:11 ID:wQtjKuKa(1/2) AAS
そのアルゴリズムの計算時間を f(n) とし、オーダーが O(g(n)) と表記される場合、定数cがあって、n がある程度大きくなれば常に f(n) <= c * g(n) が成り立つ。言い方を変えれば計算時間は最悪のケースでも c * g(n) を超えない
g(n) が N (Nの1次式) なら計算時間は c * N を超えないし
g(n) が N^2 (2次式) なら c * N^2 を超えない
c はマシンのスペックや環境で変わるので具体的な数値は追求しない
Nの入力サイズが10倍、100倍、...、1万倍となったときに計算時間がおおよそどのくらいのスピードで増えるか見積もれれば良い
O(N) なら10倍、100倍、...、1万倍
O(N^2) なら100倍、1万倍、...、1億倍..
詳しくはアルゴリズムの教科書か
外部ﾘﾝｸ:ja.wikipedia.orgランダウの記号
38(1): 2021/10/05(火)02:13 ID:3IOuHtiP(1/2) AAS
>>37
ありがとうございます。
ですが、O(V + E)の中に書かれている式であるV + Eは2変数の関数です。それでも1変数の場合と同じ定義でいいんですか？
39(1): 2021/10/05(火)03:31 ID:wQtjKuKa(2/2) AAS
>>38
定義は同じ
V個の頂点はそれぞれ1回キューに入れられて1回キューから取り出される
E本の辺はある頂点から隣接する次の頂点を見つけるのに1度処理されるだけ
合わせてc0 * E + c1 * V の手間がかかるが、c0, c1 の大きい方を c として c0 * E + c1 * V <= c (E+V)、これは最悪でも計算量は c (E+V) を超えないことを意味し、E+V の部分が g(E+V) となる
40: 2021/10/05(火)08:50 ID:3IOuHtiP(2/2) AAS
>>39
なるほど。ありがとうございました。
41(1): 2021/10/10(日)18:05 ID:6QW0WSDe(1/3) AAS
以下のプログラミングコンテストの問題なのですが、『アルゴリズム実技検定』という本の解説では、これは動的計画法の問題であると書いてあります。
本当にこういうのも動的計画法と言いますか？
外部ﾘﾝｸ:atcoder.jp
42(1): 2021/10/10(日)19:42 ID:CKYp8hS8(1/2) AAS
>>41
ツリーを作って再帰にもできそうだけど、番号の1番大きい社員から少ない社員に向かって1つずつ処理していけば動的計画法になるね
最初に各社員に部下の給料のリスト（最初は空）を持たせて、社員番号Nから2番に向かって部下の給料のリストに値があればそこから自分の給与を計算して上司のリストに加えることを繰り返す
社員N番を含めて部下がいない、自分の番が回ってきても部下の給料リストが空なら1を上司のリストに加えればいい
43(1): 2021/10/10(日)20:02 ID:CKYp8hS8(2/2) AAS
部下の給与リストじゃなくて最大値と最小値だけ覚えとけばもっと賢いか
44: 2021/10/10(日)20:08 ID:6QW0WSDe(2/3) AAS
>>42-43
ありがとうございました。
『アルゴリズム実技検定』では、上司部下の関係を親子の関係と考えたツリーを考えて、再帰を使った深さ優先探索のような処理をしています。
そして、そのプログラムを動的計画法を使ったプログラムと書いています。
45(2): 2021/10/10(日)22:19 ID:shNjC7Q8(1) AAS
英語版Wikipedia（その出展として挙げられている『アルゴリズムイントロダクション』）の説明に従うと、この例は部分問題重複性が無いので、動的計画法ではなく分割統治アルゴリズムと呼ぶべきでしょうね
外部ﾘﾝｸ:en.m.wikipedia.org
競技プログラミング界隈だとこのような例も動的計画法と呼ぶ人はいますが、書籍でそれが一般的であるかのように書かれているのはあまりよくないように思えますね
46: 2021/10/10(日)22:22 ID:6QW0WSDe(3/3) AAS
>>45
ありがとうございました。
47(1): 2021/10/11(月)16:16 ID:bJ9NE0N3(1/2) AAS
閉路を含まない有向グラフのすべての有向パスのうち長さが最長の有向パスの長さを計算せよという問題について質問があります。
AtCoderの出題ページは以下になります。
外部ﾘﾝｸ:atcoder.jp
『アルゴリズム実技検定』という本の解説を読みますと「トポロジカルソート」という考え方を使うと書いてあります。
私は「トポロジカルソート」について何も知りませんが、制限時間内に答えを出すPythonプログラムを書けました。
本当に「トポロジカルソート」というのが必要でしょうか？
なお、上記ページにリンクが貼ってある解説のページ（hamayanhamayanというユーザーの解説のページ）にも「トポロジカルソートを知っていれば一瞬だが、知らないと解けない。」
と書いています。
『アルゴリズム実技検定』という本の模範解答を見ても、「トポロジカルソート」によって頂点に番号を割り振ったりはしていません。
つまり「トポロジカルソート」など不要ではないかと思うんです。
省2
48: 2021/10/11(月)16:25 ID:bJ9NE0N3(2/2) AAS
>>47
あともう一点。
この問題の出題カテゴリは動的計画法に属します。
『アルゴリズム実技検定』の模範解答も私のコードも、深さ優先探索 + 「メモ化再帰」で答えを計算しています。
>>45
確かにこの問題の場合部分問題重複性はあると思いますが、こういう単なる、いわゆる「メモ化再帰」も動的計画法と言っていいのでしょうか？
49(1): 2021/10/12(火)00:41 ID:mo6bbxTQ(1) AAS
まず、動的計画法の実現方法にはトップダウン方式とボトムアップ方式があり、メモ化再帰はトップダウン方式の実現方法に当たります
こちらは日本語版のWikipediaにも記載があります
外部ﾘﾝｸ:ja.m.wikipedia.org
トポロジカルソートの知識が必須になるのは、ボトムアップ方式で実現する場合です
メモ化再帰する場合にはトポロジカルソートを意識する必要はありません
ここで行われているメモ化再帰の実装は、深さ優先検索を用いたトポロジカルソートの実装と類似しており、結果的にトポロジカルソートの逆順で計算結果が確定されていくことになります
50: 2021/10/12(火)07:51 ID:9oya6EGe(1) AAS
>>49
ありがとうございました。
『アルゴリズム実技検定』でのコードは、トップダウン方式ですので、「トポロジカルソート」などという言葉を出さなくても良かったわけですね。
51: 2021/10/15(金)14:52 ID:n9WPu0Ca(1/2) AAS
外部ﾘﾝｸ:atcoder.jp
↑の問題を↓のように解きました。
外部ﾘﾝｸ:ideone.com
コメントアウトしている行をアンコメントするとジェッジにパスしなくなります。
理由が分かりません。
理由が分かる方、教えて下さい。
52: 2021/10/15(金)15:11 ID:n9WPu0Ca(2/2) AAS
あ、わかりました。
53: 2021/10/15(金)15:13 ID:/Buyr3BY(1) AAS
よかったね、さようなら
54(1): 2021/10/24(日)20:12 ID:tzzO99P4(1) AAS
外部ﾘﾝｸ:atcoder.jp
この問題は貪欲法が適用できるとのことですが、適用できることの証明はどう証明するのでしょうか？
55: 2021/10/24(日)22:55 ID:340Kt+5N(1) AAS
>>54
k日間で得られるポイントの合計の最大値を P(k) と表し、k日目に解禁されるタスクが2つあってそれぞれのポイントを p, q (p < q) とする。
貪欲法でないやり方で求めた最適解P(k)*があるとする。--- (1)
貪欲法でないある方針に基づいてpポイントのタスクを選択したとする。
このとき、貪欲法に基づいてqポイントのタスクを選択したとすると、P(k) = P(k)* + q - p となる更に良い解が得られ、(1) の「貪欲法でなくても最適解」の前提条件に矛盾する。
毎回思うけどこの atcoder てあんまり良くないね。
日本語の問題文があるから重宝されてるのかもしれないけど、入力のサイズが小さすぎてブルートフォースでも瞬時に解けたり、解説ないからもっと良い解があるのかわからないし、leetcode あたりのが勉強になると思う。
56: 2021/10/25(月)11:24 ID:vmRZrQEp(1) AAS
まるちんこ
57: 2021/10/25(月)12:10 ID:Ex1ycVpJ(1/2) AAS
以下のような感じで証明できないですかね？
タスク T のポイントを p(T) で表すことにする。
貪欲法によって選ばれたタスク列を
T_1, T_2, …, T_n
とする。
省4
58: 2021/10/25(月)16:58 ID:Ex1ycVpJ(2/2) AAS
Introduction to Algorithms 3rd Editionがくどすぎて読みにくい。
59: 2021/10/26(火)11:19 ID:CwYCZWUI(1/2) AAS
タスク T のポイントを p(T) で表すことにする。
貪欲法によって選ばれたタスク列を
T_1, T_2, …, T_n
とする。
S := {k | 1 ≦ k ≦ n, 第1日目から第k日目の間に得られるポイントの合計の最大値 > p(T_1) + … + p(T_k)} が空集合ではないと仮定して矛盾を導く。
省10
60: 2021/10/26(火)11:33 ID:CwYCZWUI(2/2) AAS
このとき、長さ n のタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} で
p(R_{k_0}) = p(T_{k_0})
p(R_{k_0+1}) = p(T_{k_0+1})
…
p(R_{n}) = p(T_{n})
を満たすようなものが存在することは明らかである。
このタスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} も貪欲法によって選ばれうるタスク列である。
ところが、タスク列 S_1, S_2, …, S_{k_0-1}, R_{k_0}, R_{k_0+1}, …, R_{n} は第k_0日において、 p(S_{k_0}) > p(T_{k_0}) = p(R_{k_0}) であるにもかかわらず、
タスク S_{k_0} を選択しないタスク列であるから、このタスク列は貪欲法によって選ばれうるタスク列ではない。
省2
61(1): 2021/10/31(日)19:17 ID:BY7qrcrb(1) AAS
外部ﾘﾝｸ:atcoder.jp
↓途中の段階で最終的に得られる互いの幸福度の総和をどうやって彼らは知るのでしょうか？
ただし、彼らはともに、「最終的に自分が得る幸福度の総和」から「最終的に相手が得る幸福度の総和」を引いた値を最大化するように料理を選びます。
このとき、「最終的に高橋くんが得る幸福度の総和」から「最終的に青木さんが得る幸福度の総和」を引いた値はいくつになるでしょうか？
62: 2021/11/02(火)10:37 ID:px0qcy1y(1) AAS
>>61
動画ﾘﾝｸ[YouTube]
63: 2021/11/02(火)13:38 ID:RQoewYsN(1) AAS
『Introduction to Algorithms 3rd Edition』よりも『Algorithm Design』のほうがずっといい本だと思うのですが、どうですか？
64: 2021/11/03(水)18:42 ID:K+j19pQn(1/2) AAS
画像ﾘﾝｸ[jpg]:i.imgur.com
↑は、Dijkstraのアルゴリズムの擬似コードですが、これって間違っていますよね？
Sに付け加えられるvに対してのみd[v]を計算しています。
65(1): 2021/11/03(水)19:10 ID:p70BP33u(1) AAS
追加される時点で最短距離が決定するから問題ないと思うが。
66: 2021/11/03(水)19:38 ID:K+j19pQn(2/2) AAS
>>65
ありがとうございました。
あ、d'[v]のほうは更新され続けるんですね。
そして、最後に、Sに入れられるときに、d[v]に確定したd'[v]の値を入れているんですね。
dなんて使わずにd'だけでいいのにと思います。
67(1): 2022/03/05(土)12:18 ID:c2cv6ICZ(1) AAS
画像ﾘﾝｸ[jpg]:i.imgur.com
68: 2022/03/05(土)18:15 ID:2/qEYPh4(1) AAS
>>67
グロ
69: 2022/04/09(土)22:56 ID:NDf9sYGT(1) AAS
頭では分かってるつもりなんだけど
どうしても実際にはif , switchのオンパレードになっちゃんだよな
特に仕事だと、学術論的なことでぐずぐずハマってたら
なにやってんだってはなしになることが多い
70: 2022/08/31(水)20:45 ID:CIcCYvEQ(1/4) AAS
『アルゴリズム実技検定公式テキスト』という本に以下の最長パスの問題の出題と解答が書いてあります．
外部ﾘﾝｸ:atcoder.jp
解説を読むと，この問題を解くのに，トポロジカルソートが重要だと書いてあります．
71: 2022/08/31(水)20:52 ID:CIcCYvEQ(2/4) AAS
解答は以下のような感じです：
length(v)を点vからの最長パスの長さとします．
v → w_1
v → w_2
…
v → w_n
という辺があるとき，length(v) = max{length(w_1), …, length(w_n)}
とメモ化再帰により計算する．（深さ優先探索を使う．）
この解答のどこでトポロジカルソートの考えが使われているのかが分かりません．
72: 2022/08/31(水)20:55 ID:CIcCYvEQ(3/4) AAS
入次数が0の点達からメモ化再帰（深さ優先探索）を行っています．
73: 2022/08/31(水)20:58 ID:CIcCYvEQ(4/4) AAS
外部ﾘﾝｸ:ideone.com
例えば，上のプログラムのような感じです．
74: 2022/09/01(木)09:35 ID:NAQLmVKw(1) AAS
入字数0の点が最長パスの始点候補だから、トポロジカルソートしたら始点から終点までの経路上の辺の長さをを足し合わせていけばいい
75(1): 2022/09/04(日)06:43 ID:x0sSmgMe(1) AAS
でもトポロジカルソートしていないですよね．プログラムを見ると．
76(1): 2022/09/18(日)14:40 ID:suxGffYa(1) AAS
C++の連結リスト(list)の削除に必要な計算量がO(1)であると大槻の本に書いてあるのですが、
削除したい要素を探すのにO(N)必要だと思います。
これって単に、指定した位置の要素を削除するという操作だからO(1)ということですか？
77: 2022/09/18(日)15:28 ID:69Jy4am9(1) AAS
知らね。前後の文脈含めてなんて書いてあるの？
78: 2022/09/19(月)12:07 ID:yWkM0kBX(1) AAS
>>76
そう
指定した位置というか指定したノードだけど
79: 2022/09/20(火)01:12 ID:zbB+YFPz(1) AAS
>>75
トポロジカルソートが重要かはよくわからんけど
状態空間も遷移の考えもほとんど同じじゃん
80: 2022/09/26(月)15:08 ID:cqAm7B1L(1/5) AAS
比較に基づくソートの最悪の入力に対する実行時間の下限がΩ(n * log(n))であることの証明が分かりません。
81: 2022/09/26(月)15:13 ID:cqAm7B1L(2/5) AAS
決定木で説明しますが、その説明が分かりません。
82: 2022/09/26(月)15:53 ID:Dh3HDIpo(1) AAS
そうか
83: 2022/09/26(月)16:07 ID:cqAm7B1L(3/5) AAS
比較に基づく任意のソートアルゴリズムに対して、その決定木って作れますか？
84: 2022/09/26(月)18:12 ID:cqAm7B1L(4/5) AAS
決定木の各ノードである2つの要素のペアの大小関係が決まりますが、その情報を利用しない場合にはどうなりますか？
85(1): 2022/09/26(月)20:52 ID:Sp/QOOjd(1) AAS
英語だけどイラスト付きで分かりやすく書いてある
外部ﾘﾝｸ:medium.com
86: 2022/09/26(月)21:50 ID:cqAm7B1L(5/5) AAS
>>85
ありがとうございました。
87: 2022/10/17(月)16:05 ID:BBjAlznw(1/2) AAS
命題2.4：
始点 s から各頂点へ最短路が存在すると仮定する。このとき、 s を根とする
有向全域木 T が存在して、 T における s から頂点 v への有向路は、 s から
頂点 v への最短路となっている。
証明：
始点 s から各頂点 v への最短路（の枝集合）を P_v とし、 T = ∪_{v ∈ V} P_v とおく。
定理2.3と命題2.2より、 P_v は単純有向路としてよい。 T の要素数がちょうど n - 1 であれば、
これは有向全域木であり、各頂点への最短路を含む。一方、 T の要素数が n 以上の場合は、
以下の手順で最短路を繰り返し修正することにより、所望の有向全域木を求めることができる。
T の要素数が n 以上と仮定する。このとき、ある頂点 v_* ∈ V - {s} が存在して、 T の中には
省12
88: 2022/10/17(月)17:01 ID:BBjAlznw(2/2) AAS
もっと分かりやすく書き直しました：
命題2.4：
始点 s から各頂点へ最短路が存在すると仮定する。このとき、 s を根とする
有向全域木 T が存在して、 T における s から頂点 v への有向路は、 s から
頂点 v への最短路となっている。
証明：
始点 s から各頂点 v への最短路（の枝集合）を P_v とし、 T = ∪_{v ∈ V} P_v とおく。
定理2.3と命題2.2より、 P_v は単純有向路としてよい。 T の要素数がちょうど n - 1 であれば、
これは有向全域木であり、各頂点への最短路を含む。一方、 T の要素数が n 以上の場合は、
以下の手順で最短路を繰り返し修正することにより、所望の有向全域木を求めることができる。
省17
89: 2022/11/12(土)19:54 ID:xCg5uX6U(1) AAS
アルゴリズムの学習で、ツリー構造のデータ詮索とか学習してるのだが。
一般的にデータってリレーショナルデータベースとか、
プログラムで利用するなら配列とかでしょ。
ツリー構造のデータってそんなあるの？
90: 2022/11/12(土)20:16 ID:WvbeP05G(1) AAS
ファイルシステムとかHTMLとかいくらでもある
91: 2022/11/12(土)21:18 ID:EqzcHwUy(1) AAS
XML
92: 2022/11/12(土)23:06 ID:Y42oI462(1) AAS
パイ毛 パイ毛 パイ毛〜
93: 2022/11/12(土)23:15 ID:mqwguCdy(1) AAS
データ詮索ワロタ
94: 2023/04/30(日)19:23 ID:dQsz62eN(1) AAS
こんなスレが埋もれてるなんて信じられん
お前らもっとアルゴリズム刻めよ
95: 2023/05/03(水)01:15 ID:ZUlTYoGm(1) AAS
ニューラルネットワークでデータを詮索してみるか
96: 2023/05/27(土)13:47 ID:dQE1+1Te(1) AAS
デザインパターンは廃れたよな
97: 2023/05/28(日)16:34 ID:pV4wEcmO(1) AAS
エディタとかDBとか巨大外部リソースとのやりとりに関してのアルゴリズムはまだまだ再考の余地があると思う
98: 2023/06/28(水)16:50 ID:BVdlIcNn(1) AAS
漠∞！！！！
戸∞！！！！！
廷∞！！！！！！
与∞！！！！！！！
合∞！！！！！！！！
山∞！！！！！！！！！
α∞！！！！！！！！
野∞！！！！！！！！
99: 2023/10/13(金)19:28 ID:ANHPZuQm(1) AAS
では教育してやろう。”本当のオタク”の萌えに対する論理戦というものを……
100: 2023/10/29(日)09:40 ID:nlAlD3dC(1/2) AAS
マージソートのmidの導出ですが
mid=(left+right+1)//2
ではなく
mid=(left+right)//2
なのはなぜでしょうか
この1行で正しくソートできないのです
pythonで勉強中の超初心者です
よろしくお願いします
101: 2023/10/29(日)09:40 ID:nlAlD3dC(2/2) AAS
マージソートのmidの導出ですが
mid=(left+right+1)//2
ではなく
mid=(left+right)//2
なのはなぜでしょうか
この1行で正しくソートできないのです
pythonで勉強中の超初心者です
よろしくお願いします
102: 2023/12/23(土)10:34 ID:9iMk1h5v(1) AAS
プログラムを最近勉強し始めたのですが二分探索木や赤黒木みたいなデータ構造って現場でも実際に使われているのですか？
103: 2023/12/23(土)13:21 ID:ppz7uSBz(1/2) AAS
必要になったことはないなあ、連想配列はハッシュテーブルの方が速いし
ソートが必要ならリストを使う
104: 2023/12/23(土)16:14 ID:mgbjvOvz(1) AAS
やっぱり使わないですよねぇ
今朝からAVL木練習してるんだけど、
やはり回転とかの作業分だけハッシュテーブルに比べると圧倒的に遅いんだよなぁ
当たり前だけど。
105: 2023/12/23(土)16:22 ID:ppz7uSBz(2/2) AAS
永続化データ構造は作りやすいから.NETのイミュータブルコレクションでは使われてるよ
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.568s*