データ構造,アルゴリズム,デザインパターン総合ｽﾚ 4 (105ﾚｽ)
上下前次1-新
67(1): 2022/03/05(土)12:18 ID:c2cv6ICZ(1) AAS
画像ﾘﾝｸ
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 の中には
v_* に向かう枝が2つ以上ある。
…
v_* に向かう枝が2つ以上あることの証明ですが、どのような証明が典型的なものと考えられますか？
証明：
T を無向グラフと考えたとき、 T は連結であり、 #T = n だから無向閉路が存在する。
T の作り方から s に向かう枝は存在しないから、 s はこの無向閉路上にはない。
仮に、上の v_* が存在しないと仮定する。
v を 上の無向閉路上の任意の頂点とする。 T の定義により、 T の中には v へ向かう枝が存在するが、
仮定により、そのような枝は唯一つしか存在しない。ゆえに、この無向閉路を有向グラフとして考えた
とき、有向閉路である。
T の作り方から、 s から v への有向路が存在する。
ところが、 s は上の有向閉路には含まれないからこれは矛盾である。
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 以上の場合は、
以下の手順で最短路を繰り返し修正することにより、所望の有向全域木を求めることができる。
T の要素数が n 以上と仮定する。このとき、ある頂点 v_* ∈ V - {s} が存在して、 T の中には
v_* に向かう枝が2つ以上ある。
…
v_* に向かう枝が2つ以上あることの証明ですが、どのような証明が典型的なものと考えられますか？
証明：
T を無向グラフと考えたとき、 T は連結であり、 #T = n だから無向閉路が存在する。
仮に、上の v_* が存在しないと仮定する。
v を上の無向閉路上の任意の頂点とする。 T の定義により、 T の中には v へ向かう枝が存在するが、
仮定により、そのような枝は唯一つしか存在しない。ゆえに、この無向閉路を有向グラフとして考えた
とき、有向閉路である。この有向閉路を C とする。 T の作り方から s に向かう枝は存在しないから、
s は C 上にはない。
T の作り方から、 s から v への有向路 P が存在する。
s は C 上にはなく、 v は C 上にあることに注意する。
P 上の頂点で最初に C 上の頂点ともなる頂点を w とする。
w は s とは異なるから、 P 上には、 w の直前の頂点 u が存在する。u は w についての仮定から、
C 上の頂点ではない。 w は C 上の頂点であるから、 w へ向かう C 上の枝が存在する。
以上から、 w へ向かう少なくとも2つ以上の枝が存在することになる。 これは矛盾である。
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
デザインパターンは廃れたよな
上下前次1-新書関写板覧索設栞歴
あと 9 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ
ぬこの手 ぬこTOP 0.014s