- データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
242 ：デフォルトの名無しさん[]：2017/01/03(火) 08:50:16.82 ID:hCDXc7Qp - >>224
>>227
閉路を含まないから、各点を高々1回しか通らない。（端点も）
直通の経路が １
途中でｋ個所を通過する経路が
(n-2)(n-3)･････(n-k-1) = (n-2)!/(n-k-2)!
だけある。ただし、k≦n-2
よって
a_n = (n-2)!｛1 + 1/1! + 1/2! + … + 1/(n-2)!},
n ≧ 2 のとき、
(n-2)! ≦ (n-2)! * (1 + 1/1! + 1/2! + … + 1/(n-2)!) ≦ e * (n-2)!
したがって、
a_n = Θ((n-2)!)
である。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
243 ：デフォルトの名無しさん[]：2017/01/03(火) 08:52:54.04 ID:hCDXc7Qp - >>234-238
のダイクストラのアルゴリズムの正しさの証明に間違いはないという
ことでOKですか？
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
244 ：デフォルトの名無しさん[]：2017/01/03(火) 11:39:58.60 ID:hCDXc7Qp - Erik DemaineはMITの歴史上最年少で教授になったという天才だそうですね。
今、そのErik Demaineの2005年のダイクストラのアルゴリズムについての講義を見ています。
見終わったら、講義の要約について書きます。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
245 ：デフォルトの名無しさん[]：2017/01/03(火) 13:47:58.01 ID:hCDXc7Qp - ダイクストラのアルゴリズム：
01: d[s] ← 0
02: for each v ∈ V - {s}:
03: ■■d[v] ← ∞
04: S ← Φ
05: Q ← V
06: while Q ≠ Φ:
07: ■■u ← ExtractMin(Q)
08: S ← S ∪ {u}
09: for each v ∈ Adj[u]:
10: ■■if d[v] > d[u] + w(u, v):
11: ■■■■d[v] ← d[u] + w(u, v)
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
246 ：デフォルトの名無しさん[]：2017/01/03(火) 13:49:29.21 ID:hCDXc7Qp - Correctness I:
d[v] の初期化の直後、およびLine 11の直後において、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が
成り立つ。
証明：
d[v] の初期化の直後には、
d[s] = 0 かつすべての v ∈ S - {v} に対して、d[v] = ∞
が成り立っている。
δ(s, s) = 0 かつすべての v ∈ S に対して、 δ(s, v) ≦ ∞
であるから、d[v] の初期化の直後には、
すべての v ∈ V に対して、 d[v] ≧ δ(s, v) が確かに
成り立っている。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
247 ：デフォルトの名無しさん[]：2017/01/03(火) 13:49:56.08 ID:hCDXc7Qp - Line 11の直後において、すべての v ∈ V に対して、
d[v] ≧ δ(s, v) が成り立つことを背理法により示す。
Line 11の直後において、 d[v] ≧ δ(s, v) が
成り立たないような v ∈ V が存在するとする。
v をそのような点の中で、最初の点とする。
d[v] < δ(s, v)
d[v] < δ(s, v) ≦ ∞ であるから、
ダイクストラのアルゴリズムのLine 11は少なくとも1回は
実行されているはずである。そのような最後の実行を
d[v] ← d[u] + w(u, v)
とすると、
d[u] + w(u, v) = d[v] < δ(s, v)
が成り立つ。
一方、 d[u] ≧ δ(s, u) であるから、
d[u] + w(u, v) ≧ δ(s, u) + w(u, v)
≧ δ(s, u) + δ(u, v)
≧ δ(s, v)
が成り立つが、これは矛盾である。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
248 ：デフォルトの名無しさん[]：2017/01/03(火) 13:51:21.27 ID:hCDXc7Qp - Correctness Lemma:
s → … → u → v を s から v への一つの最短路とする。
d[u] = δ(s, u) であるとする。
このとき、Line10-11を実行すると、
d[v] = δ(s, v)
が成り立つ。
証明：
δ(s, v) = w(s → … → u) + w(u, v)
= δ(s, u) + w(u, v)
Correctness Iより、 d[v] ≧ δ(s, v)
(1)Line10-11の実行前に、 d[v] = δ(s, v) である場合。
Line10-11の実行後も d[v] = δ(s, v) である。
(2)Line10-11の実行前に、 d[v] > δ(s, v) である場合。
d[v] > δ(s, v) = δ(s, u) + w(u, v) = d[u] + w(u, v)
Line10-11の実行後は、 d[v] = d[u] + w(u, v) = δ(s, v)
となる。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
249 ：デフォルトの名無しさん[]：2017/01/03(火) 13:52:06.64 ID:hCDXc7Qp - Correctness II:
ダイクストラのアルゴリズムが終了したとき、
すべての v ∈ V に対して、 d[v] = δ(s, v) が成り立つ。
証明：
d[v] は v が S に追加された後は、不変である。
よって、 v が S に追加されたときに、
d[v] = δ(s, v) であることを示せばよい。
背理法で示す。
v が S に追加されたときに、 d[v] ≠ δ(s, v) であるような
v ∈ V が存在すると仮定する。
u をそのような点の中で、最初に S に追加された点とする：
d[u] ≠ δ(s, u)
Correctness Iより、
d[u] > δ(s, u)
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
250 ：デフォルトの名無しさん[]：2017/01/03(火) 13:52:49.71 ID:hCDXc7Qp - 今、 u が S に追加される直前の状況を考えることにする。
u はまだ S に追加されていないから、 u ∈ Q である。
p を s から u への一つの最短路とすると、 w(p) = δ(s, u) である。
s ∈ S, u ∈ Q であるから、 p 上の辺 (x, y) で x ∈ S, y ∈ Q となる
ような辺が存在する。そのような辺の一つを (x, y) とする。
すると、 p は以下のようになる。
p : s → … → x → y → … → u
x ∈ S であるから、 u に関する仮定より、
d[x] = δ(s, x) が成り立つ。また、明らかに、
s → … → x → y は s から y への一つの最短路であるから、
Correctness Lemmaより、 d[y] = δ(s, y) が成り立つ。
明らかに、 δ(s, y) ≦ δ(s, u) であるから、
d[y] ≦ δ(s, y)
また、Line07を見れば分かるように、
d[u] ≦ d[y] である。
よって、
d[u] ≦ δ(s, u) となるが、これは矛盾である。
| - データ構造,アルゴリズム,デザインパターン総合ｽﾚ 3©2ch.net
251 ：デフォルトの名無しさん[]：2017/01/03(火) 13:55:46.21 ID:hCDXc7Qp - Lec 17 | MIT 6.046J / 18.410J Introduction to Algorithms (SMA 5503), Fall 2005
https://youtu.be/xhG2DyCX3uA
|
|