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

**デフォルトの名無しさん** · 2021/11/03(水) 19:10:00.22

追加される時点で最短距離が決定するから問題ないと思うが。

**デフォルトの名無しさん** · 2021/11/03(水) 19:38:24.24

>>65
ありがとうございました。
あ、d'[v]のほうは更新され続けるんですね。
そして、最後に、Sに入れられるときに、d[v]に確定したd'[v]の値を入れているんですね。
dなんて使わずにd'だけでいいのにと思います。

**デフォルトの名無しさん** · 2022/03/05(土) 12:18:28.50

https://i.imgur.com/SLWsXcA.jpg

**デフォルトの名無しさん** · 2022/03/05(土) 18:15:22.85

>>67
グロ

**デフォルトの名無しさん** · 2022/04/09(土) 22:56:02.65

頭では分かってるつもりなんだけど
どうしても実際にはif , switchのオンパレードになっちゃんだよな

特に仕事だと、学術論的なことでぐずぐずハマってたら
なにやってんだってはなしになることが多い

**デフォルトの名無しさん** · 2022/08/31(水) 20:45:30.79

『アルゴリズム実技検定公式テキスト』という本に以下の最長パスの問題の出題と解答が書いてあります．

https://atcoder.jp/contests/dp/tasks/dp_g

解説を読むと，この問題を解くのに，トポロジカルソートが重要だと書いてあります．

**デフォルトの名無しさん** · 2022/08/31(水) 20:52:44.34

解答は以下のような感じです：

length(v)を点vからの最長パスの長さとします．

v → w_1
v → w_2
…
v → w_n

という辺があるとき，length(v) = max{length(w_1), …, length(w_n)}
とメモ化再帰により計算する．（深さ優先探索を使う．）

この解答のどこでトポロジカルソートの考えが使われているのかが分かりません．

**デフォルトの名無しさん** · 2022/08/31(水) 20:55:47.47

入次数が0の点達からメモ化再帰（深さ優先探索）を行っています．

**デフォルトの名無しさん** · 2022/08/31(水) 20:58:25.24

https://ideone.com/LvMx0h

例えば，上のプログラムのような感じです．

**デフォルトの名無しさん** · 2022/09/01(木) 09:35:46.60

入字数0の点が最長パスの始点候補だから、トポロジカルソートしたら始点から終点までの経路上の辺の長さをを足し合わせていけばいい

**デフォルトの名無しさん** · 2022/09/04(日) 06:43:45.43

でもトポロジカルソートしていないですよね．プログラムを見ると．

**デフォルトの名無しさん** · 2022/09/18(日) 14:40:45.95

C++の連結リスト(list)の削除に必要な計算量がO(1)であると大槻の本に書いてあるのですが、
削除したい要素を探すのにO(N)必要だと思います。

これって単に、指定した位置の要素を削除するという操作だからO(1)ということですか？

**デフォルトの名無しさん** · 2022/09/18(日) 15:28:50.46

知らね。前後の文脈含めてなんて書いてあるの？

**デフォルトの名無しさん** · 2022/09/19(月) 12:07:14.08

>>76
そう
指定した位置というか指定したノードだけど

**デフォルトの名無しさん** · 2022/09/20(火) 01:12:54.08

>>75
トポロジカルソートが重要かはよくわからんけど
状態空間も遷移の考えもほとんど同じじゃん

**デフォルトの名無しさん** · 2022/09/26(月) 15:08:47.03

比較に基づくソートの最悪の入力に対する実行時間の下限がΩ(n * log(n))であることの証明が分かりません。

**デフォルトの名無しさん** · 2022/09/26(月) 15:13:01.77

決定木で説明しますが、その説明が分かりません。

**デフォルトの名無しさん** · 2022/09/26(月) 15:53:07.65

そうか

**デフォルトの名無しさん** · 2022/09/26(月) 16:07:33.81

比較に基づく任意のソートアルゴリズムに対して、その決定木って作れますか？

**デフォルトの名無しさん** · 2022/09/26(月) 18:12:30.08

決定木の各ノードである2つの要素のペアの大小関係が決まりますが、その情報を利用しない場合にはどうなりますか？

**デフォルトの名無しさん** · 2022/09/26(月) 20:52:32.58

英語だけどイラスト付きで分かりやすく書いてある
https://medium.com/enjoy-algorithm/lower-bound-of-comparison-sorting-c3e2225e3419

**デフォルトの名無しさん** · 2022/09/26(月) 21:50:30.08

>>85
ありがとうございました。

**デフォルトの名無しさん** · 2022/10/17(月) 16:05:05.43

命題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 は上の有向閉路には含まれないからこれは矛盾である。

**デフォルトの名無しさん** · 2022/10/17(月) 17:01:23.13

もっと分かりやすく書き直しました：

命題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つ以上の枝が存在することになる。これは矛盾である。

**デフォルトの名無しさん** · 2022/11/12(土) 19:54:31.16

アルゴリズムの学習で、ツリー構造のデータ詮索とか学習してるのだが。
一般的にデータってリレーショナルデータベースとか、
プログラムで利用するなら配列とかでしょ。
ツリー構造のデータってそんなあるの？

**デフォルトの名無しさん** · 2022/11/12(土) 20:16:08.76

ファイルシステムとかHTMLとかいくらでもある

**デフォルトの名無しさん** · 2022/11/12(土) 21:18:58.24

XML

**デフォルトの名無しさん** · 2022/11/12(土) 23:06:22.44

パイ毛　パイ毛　パイ毛～

**デフォルトの名無しさん** · 2022/11/12(土) 23:15:39.39

データ詮索ワロタ

**デフォルトの名無しさん** · 2023/04/30(日) 19:23:01.90

こんなスレが埋もれてるなんて信じられん
お前らもっとアルゴリズム刻めよ

**デフォルトの名無しさん** · 2023/05/03(水) 01:15:28.00

ニューラルネットワークでデータを詮索してみるか

**デフォルトの名無しさん** · 2023/05/27(土) 13:47:32.62

デザインパターンは廃れたよな

**デフォルトの名無しさん** · 2023/05/28(日) 16:34:40.65

エディタとかDBとか巨大外部リソースとのやりとりに関してのアルゴリズムはまだまだ再考の余地があると思う

**デフォルトの名無しさん** · 2023/06/28(水) 16:50:44.07

漠∞！！！！
戸∞！！！！！
廷∞！！！！！！
与∞！！！！！！！
合∞！！！！！！！！
山∞！！！！！！！！！
α∞！！！！！！！！
野∞！！！！！！！！

**デフォルトの名無しさん** · 2023/10/13(金) 19:28:46.40

では教育してやろう。”本当のオタク”の萌えに対する論理戦というものを……

**デフォルトの名無しさん** · 2023/10/29(日) 09:40:11.61

マージソートのmidの導出ですが
mid=(left+right+1)//2
ではなく
mid=(left+right)//2
なのはなぜでしょうか

この1行で正しくソートできないのです

pythonで勉強中の超初心者です
よろしくお願いします

**デフォルトの名無しさん** · 2023/10/29(日) 09:40:36.19

マージソートのmidの導出ですが
mid=(left+right+1)//2
ではなく
mid=(left+right)//2
なのはなぜでしょうか

この1行で正しくソートできないのです

pythonで勉強中の超初心者です
よろしくお願いします

**デフォルトの名無しさん** · 2023/12/23(土) 10:34:22.20

プログラムを最近勉強し始めたのですが二分探索木や赤黒木みたいなデータ構造って現場でも実際に使われているのですか？

**デフォルトの名無しさん** · 2023/12/23(土) 13:21:36.77

必要になったことはないなあ、連想配列はハッシュテーブルの方が速いし
ソートが必要ならリストを使う

**デフォルトの名無しさん** · 2023/12/23(土) 16:14:31.33

やっぱり使わないですよねぇ
今朝からAVL木練習してるんだけど、
やはり回転とかの作業分だけハッシュテーブルに比べると圧倒的に遅いんだよなぁ
当たり前だけど。

**デフォルトの名無しさん** · 2023/12/23(土) 16:22:46.85

永続化データ構造は作りやすいから.NETのイミュータブルコレクションでは使われてるよ