テーマ3: 凸 包 凸 包 の 定 義, 構 成 アルゴリズム
凸 包 の 定 義 凸 包 (convex hull)とは, 与 えられた 点 をすべて 包 含 する 最 小 の 凸 多 角 形 ( 凸 多 面 体 )のこと.
凸 包 の 定 義 凸 包 (convex hull)とは, 与 えられた 点 をすべて 包 含 する 最 小 の 凸 多 角 形 ( 凸 多 面 体 )のこと. 1 点 ずつ 加 えて 行 く. 現 在 の 凸 包 の 内 部 の 点 なら 何 もしない. 現 在 の 凸 包 の 外 部 の 点 なら その 点 から 凸 包 に 接 線 をひき, 凸 包 を 修 正 する. 問 題 1: 凸 包 の 内 部 / 外 部 の 判 定 方 法 問 題 2: 凸 包 への 接 線 の 求 め 方
凸 包 の 定 義 凸 包 (convex hull)とは, 与 えられた 点 をすべて 包 含 する 最 小 の 凸 多 角 形 ( 凸 多 面 体 )のこと. 全 ての 点 を 含 む 最 小 の 軸 平 行 長 方 形 から 始 め,ここから 削 っていく. 削 りすぎ ちょうど 良 い 削 りすぎた 分 をどのように 復 元 するか?
凸 包 構 成 アルゴリズム(1) 凸 包 の 基 本 的 な 性 質 1: 平 面 上 の 点 集 合 Sの 凸 包 の 頂 点 はすべてSの 点 である. 凸 包 の 基 本 的 な 性 質 2: 平 面 上 の 点 集 合 Sの 点 が 凸 包 の 頂 点 となるための 必 要 十 分 条 件 は, その 点 を 内 部 に 含 む 三 角 形 をなす3 点 がSの 中 に 存 在 しないことである. 性 質 1を 証 明 せよ( 背 理 法 ).
凸 包 構 成 アルゴリズム(2) 凸 包 構 成 の 素 朴 なアルゴリズム (0)S: 平 面 上 に 与 えられた 点 集 合 (1)Sのすべての3 点 の 組 (p, q, r)について,この3 点 で 決 まる 三 角 形 の 内 部 に 含 まれる 点 を 集 合 Sから 取 り 除 く. (2)すべての3 点 組 について 調 べた 後 で 残 った 点 が 凸 包 の 頂 点 となる. (3) 残 った 点 を 凸 包 内 部 の 点 (たとえば 重 心 点 )に 関 して 偏 角 順 に 並 べると 凸 包 を 構 成 できる. P[i] 点 P[m]が 三 角 形 (P[i], P[j], P[k])の 内 部 に 存 在 するのは, d1 = orientation(p[m], P[i], P[j]); d2 = orientation(p[m], P[j], P[k]); d3 = orientation(p[m], P[k], P[i]); P[j] がすべて 同 じ 方 向 に 順 序 付 けられているとき. P[m] この 性 質 を 使 うと, 素 朴 な 凸 包 構 成 アルゴリズムが 出 来 上 がる. 計 算 時 間 はO(n 4 ). P[k]
次 の 点 集 合 に 対 してアルゴリズムの 動 作 を 確 かめよ. 三 角 形 を 順 に 生 成 してみること. 5 3 0 2 4 1
凸 包 構 成 アルゴリズム(2) 凸 包 構 成 の 素 朴 なアルゴリズム (0)S: 平 面 上 に 与 えられた 点 集 合 (1)Sのすべての3 点 の 組 (p, q, r)について,この3 点 で 決 まる 三 角 形 の 内 部 に 含 まれる 点 を 集 合 Sから 取 り 除 く. (2)すべての3 点 組 について 調 べた 後 で 残 った 点 が 凸 包 の 頂 点 となる. (3) 残 った 点 を 凸 包 内 部 の 点 (たとえば 重 心 点 )に 関 して 偏 角 順 に 並 べると 凸 包 を 構 成 できる. この 性 質 を 使 うと, 素 朴 な 凸 包 構 成 アルゴリズムが 出 来 上 がる. 計 算 時 間 はO(n 4 ). すべての3 点 の 組 を 列 挙 すると,n 個 から3 個 取 る 組 合 せ n C 3 =n(n+1)(2n+1)/6 = O(n 3 )だけある.それらすべてについて,Sの 他 の 点 がその3 個 で 作 られる 三 角 形 の 中 に 含 まれているかどうかを 調 べるのに,O(n)の 時 間 がかかる. よって, 全 体 ではO(n 4 ) 時 間 かかる.
凸 包 構 成 アルゴリズム(2) 凸 包 構 成 の 素 朴 なアルゴリズム (0)S: 平 面 上 に 与 えられた 点 集 合 (1)Sのすべての3 点 の 組 (p, q, r)について,この3 点 で 決 まる 三 角 形 の 内 部 に 含 まれる 点 を 集 合 Sから 取 り 除 く. (2)すべての3 点 組 について 調 べた 後 で 残 った 点 が 凸 包 の 頂 点 となる. (3) 残 った 点 を 凸 包 内 部 の 点 (たとえば 重 心 点 )に 関 して 偏 角 順 に 並 べると 凸 包 を 構 成 できる. プログラム for p=1 to n-2 for q=p+1 to n-1 for r=q+1 to n 3 点 p, q, rで 決 まる 三 角 形 をTとする. for i=1 to n if 点 iは 三 角 形 Tの 内 部 にある then 点 iを 集 合 から 除 く. 残 った 点 のx,y 座 標 の 平 均 を 計 算 することにより, 重 心 点 を 求 める. 残 った 点 を 重 心 点 に 関 して 偏 角 順 に 並 べる.
#include <LEDA/window.h> using namespace leda; using namespace std; point P[1000]; int window W (500, 500); hull[1000]; int main(void) { point p, lastp; int i, j, k, q, left, n=0, inside, d1, d2, d3; W.display(); while(w >> p){ W << p; P[n++] = p; } for(i=0; i<n; i++) hull[i] = 1; for(i=0; i<n-2; i++) for(j=i+1; j<n-2; j++) for(k=j+1; k<n; k++){ for(q=0; q<n; q++){ d1 = orientation(p[i], P[j], P[q]); d2 = orientation(p[j], P[k], P[q]); d3 = orientation(p[k], P[i], P[q]); if(d1 == d2 && d2 == d3) { hull[q] = 0; // point q is not on the convex hull } } } for(i=0; i<n; i++) if(hull[i] == 1) W.draw_circle(P[i], 0.5, red); } W.read_mouse(); return 1;
#include <LEDA/window.h> using namespace leda; using namespace std; point P[1000]; int window W (500, 500); hull[1000]; void draw_triangle(int i, int j, int k, color col) { W.draw_segment(P[i], P[j], col); W.draw_segment(P[j], P[k], col); W.draw_segment(P[k], P[i], col); } int main(void) { point p, lastp; int i, j, k, q, left, n=0, inside, d1, d2, d3; W.display(); while(w >> p){ W << p; P[n++] = p; } for(i=0; i<n; i++) hull[i] = 1; for(i=0; i<n-2; i++) for(j=i+1; j<n-2; j++) for(k=j+1; k<n; k++){ draw_triangle(i, j, k, black); for(q=0; q<n; q++){ d1 = orientation(p[i], P[j], P[q]); d2 = orientation(p[j], P[k], P[q]); d3 = orientation(p[k], P[i], P[q]); if(d1 == d2 && d2 == d3) { hull[q] = 0; // point q is not on the convex hull W.draw_circle(P[q], 0.5, blue); } } W.read_mouse(); draw_triangle(i, j, k, white); } } for(i=0; i<n; i++) if(hull[i] == 1) W.draw_circle(P[i], 0.5, red); W.read_mouse(); return 1;
凸 包 構 成 アルゴリズム(2) Jarvisのアルゴリズム(ギフト 包 装 法 ) p 2 平 面 に 釘 が 打 たれているとする. 凸 包 上 にあることが 分 かっている 点 (たとえば 最 も 下 の 点 )から 始 め て, 紐 をかけていく 要 領 で 凸 包 を 求 める. p[k] p[j] p 1 p 0 p[i-1] 点 p[i+1]の 求 め 方 : 任 意 のp[k]に 対 して,(p[j], p[i], p[k])が 右 回 りであるような 点 p[j] p[i] 凸 包 のサイズ( 頂 点 数 )をhとすると, 計 算 時 間 はO(nh)となる. h=o(n)と 考 えると,O(n 2 )となる.
次 の 点 集 合 に 対 してアルゴリズムの 動 作 を 確 かめよ. 2 7 6 1 3 4 10 9 5 0 8
効 率 の 良 い 方 法 凸 包 内 部 の 点 (たとえば, 任 意 の3 点 でできる 三 角 形 の 重 心 ) pを 取 り,すべての 点 をpの 周 りに 角 度 順 にソート. ソート 順 に 点 を 調 べて, 凹 部 の 点 を 順 次 取 り 除 く. この 説 明 だけではアルゴリズムを 実 装 するのは 難 しい.
点 pの 周 りに 点 を 角 度 順 にソートするにはどうするか? p a b c a(x a, y a ), b(x b, y b ), c(x c, y c ) p(x, y) O θ θ θ c b a, tan, tan, tan 1 1 1 x x y y x x y y x x y y c c b b a a 角 度 表 現 が 得 られたら, 後 はソートするだけ. しかし,この 方 法 では 除 算 を 使 うので 計 算 誤 差 が 心 配. 練 習 問 題 : 計 算 誤 差 のせいで 角 度 順 のソートが 難 しいような 3 点 を 与 えよ.
計 算 誤 差 に 強 い 方 法 考 え 方 : 三 角 形 の 符 号 付 き 面 積 を 用 いる II a b I 最 初 に, 点 を4つの 象 限 に 分 類 することで 大 雑 把 にソート p III IV 第 一 象 限 の2 点 a と b について if (p,a,b) が 時 計 回 り then angle(a) > angle(b)
3 点 が 凹 部 を 作 るか? 1 点 pの 回 りに 時 計 回 りの 順 に 並 んだ3 点 (a, b, c)について, 3 点 が 凹 部 を 成 すような 配 置 になっているか? a b (a,b,c) は 凸 か? p c (a,b,c) が 凸 である (a, b, c) が 時 計 回 りの 順 a p b c (a,b,c) が 凹 である (a,b,c) が 反 時 計 回 りの 順
Grahamの 方 法 (R. Graham, 1972) 入 力 : n 点 からなる 点 集 合 S 凸 包 CH(S) 内 部 にある 点 p を 選 ぶ ( 最 初 の3 点 で 作 られる 三 角 形 の 重 心 点 を 計 算 する) 集 合 Sの 点 を 点 pの 周 りの 角 度 順 にソート ( 点 をpの 周 りに 時 計 回 りの 順 にソート) 最 大 のx 座 標 をもつ 点 p 0 を 求 める. (p 0, p 1, p 2,..., p n = p 0 ) をソート 列 とする. L: 点 のリスト(p 0, p 1 ). for i=2 to n do{ do{ a と b をリストL の 最 後 の2 点 とする (b が 最 後 の 点 ); if (a,b, p i ) が 凸 then b をLから 削 除 ; } until( (a, b, p i ) は 凸 ); 点 p i を Lの 末 尾 に 挿 入 ; }
10 8 9 12 13 11 7 list L = (0,1) 2: add 2 (0,1,2) 3: delete 2 delete 1 add 3 (0,3) 4: add 4 (0, 3,4) 5: delete 4 add 5 (0,3,5) 6: delete 5 add 6 (0,3,6) 6 5 14 15 2 4 16 3 1 7: add 7 (0,3,6,7) 8: delete 7 add 8 (0,3,6,8) 9: add 9 (0,3,6,8,9) 10: delete 9 add 10 (0,3,6,8,10) 11: add 11 (0,3,6,8,10,11) 12: delete 11 add 12 (0,3,6,8,10,12) 17 0 練 習 問 題 : x 座 標 最 大 の 点 を 最 初 に 選 ぶのはなぜか? 13: delete 12 add 13 (0,3,6,8,10,13) 14: add 14 (0,3,6,8,10,13,14) 15: delete 14 add 15 (0,3,6,8,10,13,15) 16: add 16 (0,3,6,8,10,13,15,16) 17: delete 16 add 17 (0,3,6,8,10,13,15,17) 0: delete 17 add 0 (0,3,6,8,10,13,15,0)
定 理 : Grahamの 方 法 では n 点 から 成 る 点 集 合 を O(n log n) の 時 間 とO(n) のメモリで 構 成 できる. 証 明 : ソーティングの 部 分 はO(n log n) 時 間 でできる. メインループでの 繰 り 返 し 回 数 は O(n) 毎 回 の 繰 り 返 しでは 点 を 削 除 するか,あるいは 点 をリストに 挿 入 する 注 意 :どの 点 も1 度 しか 削 除 されない.また,リストへの 追 加 も 各 点 高 々1 回 のみ. よって, 繰 り 返 し 回 数 は O(n). 必 要 なメモリは O(n).
凸 包 構 成 アルゴリズム(3) 点 のソーティングに 基 づく 方 法 (1)x 座 標 の 昇 順 に 点 を 整 列. (2) 順 に 見 ることによって 上 側 凸 包 を 構 成. (3) 同 じ 要 領 で, 下 側 凸 包 を 構 成. 上 側 凸 包 上 では, 連 続 する3 点 は 右 回 りの 順 でなければならない. もし 左 回 りになっていれば, 真 ん 中 の 点 を 除 去 する. この 操 作 を 繰 り 返 すと, 上 側 凸 包 が 構 成 できる. ちょっと 休 憩
次 の 点 集 合 に 対 してアルゴリズムの 動 作 を 確 かめよ. 2 7 6 1 3 4 10 9 5 0 8
分 割 統 治 法 に 基 づく 凸 包 構 成 アルゴリズム 分 割 統 治 法 分 割 : ほぼ 同 じサイズの2つの 部 分 集 合 に 分 割 再 帰 :それぞれの 部 分 集 合 に 対 する 凸 包 を 再 帰 的 に 構 成. 統 治 : 得 られた 凸 包 を 一 つの 凸 多 角 形 に 統 合 する (2つの 凸 包 を 含 む 最 小 の 凸 多 角 形 を 求 めること).
18 点 9 個 の 赤 点 と 9 個 の 青 点
9 個 の 赤 点 を4 個 の 紫 の 点 と5 個 の 黄 色 の 点 に 分 割
凸 包
定 理 : 分 割 統 治 法 のアルゴリズムはn 点 からなる 点 集 合 の 凸 包 を O(n log n) の 時 間 と O(n) のメモリで 構 成 する. 分 割 部 はO(n) 時 間 でできる. 再 帰 部 は 2T(n/2) 時 間 でできる. 統 合 部 は O(n) でできる. 再 帰 部 では, 点 は 既 にソートされているので,2つのソート 列 の マージは 線 形 時 間 でできることに 注 意. ソートの 後 の 走 査 はO(n) 時 間 でできる. よって, 次 の 漸 化 式 とその 解 を 得 る. T(n) = 2T(n/2) + O(n) T(n) = O(n log n)
分 割 統 治 法 によるアルゴリズム(2) 1. 点 集 合 を,それらの 点 のx 座 標 の 中 央 値 を 通 る 垂 直 線 によって2 分 割 する. 2. それぞれの 部 分 集 合 に 対 する 凸 包 を 再 帰 的 に 計 算 する. 3. 出 来 上 がった2つの 凸 包 を 一 つの 凸 多 角 形 に 統 合 する. ( 統 合 のために,2 本 の 外 接 線 を 求 める)
n 個 の 値 の 中 央 値 を 求 めるアルゴリズム 1. n 個 の 値 をO(n log n) 時 間 でソートし, 中 央 にある 値 を 求 める. 2. n 個 の 値 の 集 合 をサイズ5のグループに 分 け,それぞれの グループで 中 央 値 を 求 める(O(n) 時 間 でできる). 次 に,それらn/5 個 のグループ 中 央 値 の 中 央 値 xを 再 帰 的 に 求 め, xより 大 きい 要 素 の 数 gを 求 める. if g n/2 then ( 全 体 の 中 央 値 はxより 大 きい 筈 ) A をx より 大 きい 要 素 の 集 合 とする. Aにおいてn/2 番 目 に 大 きい 値 を 再 帰 的 に 求 め,それを 返 す. else A をx 以 下 の 要 素 の 集 合 とする. Aにおいてn/2 番 目 に 小 さい 値 を 再 帰 的 に 求 め,それを 返 す. 上 記 のアルゴリズムで, 集 合 A のサイズは 高 々3n/4. よって, 次 式 を 得 る. T(n) = T(n/5) + T(3n/4) + O(n), これより,T(n) = O(n)を 得 る.
例 題 : 24 個 の 値 の 場 合 S = {12,56,43,22,31,25,57,75,45,33,39,85,37,44,19,28,18,23,92,73,77,28,64,35} S = {12,56,43,22,31,25,57,75,45,33,39,85,37,44,19,28,18,23,92,73,77,28,64,35} グループ 中 央 値 ={31,45,39,28,35} グループ 中 央 値 の 中 央 値 = 35 値 > 35 = {56,43,57,75,45,39,85,37,44,92,73,77,64} 13 個 の 要 素 > 24/2 全 体 の 中 央 値 はこの 集 合 にあるはず この 集 合 で12 番 目 に 大 きい 値 を 再 帰 的 に 求 める S = {56,43,57,75,45,39,85,37,44,92,73,77,64} グループ 中 央 値 = {56,44,73},グループ 中 央 値 の 中 央 値 = 56 値 > 56 = {57,75,85,92,73,77,64} 7 個 の 要 素 > 13/2 12 番 目 に 大 きい 値 はこの 集 合 には 含 まれない 残 りの 値 の 集 合 で(12-7) 番 目 に 大 きい 要 素 を 求 める S = {56,43,45,39,37,44} 5 番 目 に 大 きい 値 = 39 全 体 の 中 央 値 は 39 実 際, > 39: 56,43,57,75,45,85,44,92,73,77,64, 39 < 39: 12,22,31,25,33,37,19,28,18,23,28,35
2つの 凸 包 の 統 合 u v 左 の 凸 多 角 形 で 最 も 右 の 頂 点 u と, 右 の 凸 多 角 形 で 最 も 左 の 頂 点 v を 求 める.
点 対 (u,v) から 始 めて, 上 部 接 線 に 到 達 するまで 上 へ 上 へと 点 対 を 更 新 し, 次 に, 下 部 接 線 に 到 達 するまで 下 へ 下 へと 点 対 を 更 新 していく. u v この 操 作 は 線 形 時 間 で 実 行 できる. なぜなら, 毎 回 どちら かの 頂 点 が 移 動 する から. 直 線 (u,v) がvを 上 部 接 点 とする 接 線 であるのは, (u, v, t)が 時 計 回 りの 順 になっているとき. ただし,tは 反 時 計 回 りの 順 でvの 次 の 点 直 線 (u,v) がuを 上 部 接 点 とする 接 線 であるのは, (v, u, w)が 時 計 回 りの 順 になっているとき. ただし,wは 時 計 回 りの 順 でuの 次 の 点
次 の2つの 凸 多 角 形 について 前 頁 のアルゴリズムの 動 作 を 調 べよ.
次 の2つの 凸 多 角 形 について 前 頁 のアルゴリズムの 動 作 を 調 べよ.
アルゴリズムの 解 析 1. 点 集 合 を,それらの 点 のx 座 標 の 中 央 値 を 通 る 垂 直 線 によって2 分 割 する. 2. それぞれの 部 分 集 合 に 対 する 凸 包 を 再 帰 的 に 計 算 する. 3. 出 来 上 がった2つの 凸 包 を 一 つの 凸 多 角 形 に 統 合 する. ( 統 合 のために,2 本 の 外 接 線 を 求 める) 1: O(n) 時 間 ( 中 央 値 発 見 アルゴリズム) 2: 2T(n/2) 時 間 3: O(n) 時 間 よって, 次 式 を 得 る. T(n) = 2T(n/2) + O(n), これより, 次 式 を 得 る. T(n) = O(n log n) 定 理 : 分 割 統 治 法 で 凸 包 を 求 めるアルゴリズムの 計 算 時 間 は O(n log n) で 必 要 なメモリはO(n) である.
双 対 変 換 に 基 づくアルゴリズム y y=cx+d 双 対 変 換 (a, b) x 点 (a, b) 直 線 y = ax + b 直 線 y= cx + d 点 (-c, d) (-c, d) y=ax+b 双 対 変 換 は, 点 と 直 線 の 間 の( 符 号 つき) 垂 直 距 離 を 保 存 す る. y y=cx+d (a, b) D=ca + d - b x (-c, d) y=ax+b D =d - (-ac+b) =ca + d - b = D
5 O d e a c b 0.5 1 a(0.4, 1) y=0.4x + 1 b(0.8, 2) y=0.8x + 2 c(0.6, 4) y=0.6x + 4 d(0.2, 5) y=0.2x + 5 e(0.1, 3) y=0.1x + 3 上 部 凸 包 上 側 エンベロープ( 包 絡 線 ) 上 部 の 無 限 領 域 の 境 界 下 部 凸 包 下 側 エンベロープ( 包 絡 線 ) 下 部 の 無 限 領 域 の 境 界 e よって, 問 題 は 双 対 平 面 における 直 線 のアレンジメントの 上 側 と 下 側 のエンベロープを 求 める 問 題 に 帰 着 される. d b c b a e
上 部 包 絡 線 の 計 算 (L 1, L 2,..., L n ): を 傾 きの 昇 順 に 並 べられた 直 線 の 列 とする. 下 のアルゴリズムでは, 直 線 のリスト(L 1, L 2,..., L k )は, 左 から 右 へと 並 んだ 多 角 形 の 辺 列 を 表 す. L 1 L2 L 3 L 4 T=(L 1 ); for i=2 to n do{ L=リストTにおける 最 後 の 直 線 ; while(tにおける 線 分 Lが L i と 交 差 しない) TからLを 削 除 し,Lをその 直 前 の 線 分 で 置 き 換 える. 直 線 L i をリストTの 最 後 尾 に 追 加 する }
例 1 直 線 の 集 合 1 上 側 エンベロープ 6 5 2 4 3 3 4 2 5 6 補 題 : n 本 の 直 線 をO(n log n) 時 間 でソートすると, 上 側 エンベロープ はO(n) 時 間 で 計 算 できる. 略 証 : 新 たな 直 線 を 挿 入 するとき, 多 数 の 直 線 を 調 べることもあるが, 調 べた 直 線 は, 最 後 の 直 線 以 外,すべて 削 除 される.
逐 次 構 成 法 3 点 からなる 凸 包 から 始 めて,1 点 ずつ 加 えながら, 凸 包 を 更 新 していく. アルゴリズム 1: CH(3) = 最 初 の3 点 で 構 成 される 凸 包 ( 三 角 形 ); for i=4 to n do{ if i 番 目 の 点 p がCH(i-1)の 内 部 にある then CH(i) = CH(i-1); else // p は CH(i-1)の 外 にある pからch(i-1) への2 本 の 接 線 を 求 め,2 本 の 接 線 の 間 にある 点 を 削 除 することによって,CH(i-1) から CH(i) への 更 新 を 実 行 する. }
1 8 2 7 4 5 6 3 困 難 な 点 : 1 点 が 凸 多 角 形 の 内 部 にあるかどうかをどう 判 定 するか. 効 率 よく 実 行 できるか? 1 点 からの 接 線 をどのように 求 めるか? 両 方 とも O(log n) 時 間 で 実 行 したい.できるか?
アルゴリズム 2: 与 えられた 点 をx 座 標 の 昇 順 にソートしておく. CH(3) = 最 初 の3 点 からなる 凸 包 ( 三 角 形 ); for i=4 to n do{ // i 番 目 の 点 p は 常 に CH(i-1)の 外 部 にある pから CH(i-1) への2 本 の 接 線 を 求 めよ. 2 本 の 接 線 の 間 にある 点 を 削 除 することによって, CH(i-1) から CH(i) への 更 新 を 実 行 する. } 現 在 の 凸 包 CH(i-1) p i 現 在 の 凸 包 を 更 新 するには, 直 前 の 点 p i-1 から 接 点 に 至 るまで 凸 包 の 境 界 上 を 上 と 下 に 移 動 する. 定 理 : アルゴリズム2は, O(n log n) の 計 算 時 間 と O(n) の メモリで,n 点 の 凸 包 を 求 める.
次 の 点 集 合 に 対 してアルゴリズムの 動 作 を 確 かめよ. 2 7 6 1 3 4 10 9 5 0 8
付 録
アルゴリズムの 記 述 株 で 儲 ける 方 法! 1990.01 135 1990.02 137 1990.03 150 1990.04 124 1990.05 118 1990.05 145 1990.06 132 1990.07 119 1990.08 105 1990.09 139 1990.10 138 1990.11 129 1990.12 100 何 月 に 買 って 何 月 に 売 れば 利 益 が 最 大 になるか?
sp[ ]: 株 価 を 蓄 える 配 列 sp[0]からsp[n-1]に 株 価 が 順 に 蓄 えられているとする. i 月 に 買 って,j 月 に 売 ると 買 値 :sp[i] 売 値 :sp[j] 利 益 :sp[j]-sp[i] これを 最 大 にしたい. ただし,i<j. アルゴリズム1: for i=0 to n-2 for j=i+1 to n-1 利 益 sp[j]-sp[i]を 求 める; アルゴリズム2: for j=1 to n-1 for i=0 to j-1 利 益 sp[j]-sp[i]を 求 める;
株 式 投 資 における 最 大 売 却 益 :(A) 方 式 入 力 : 毎 月 の 株 価 sp[0],..., sp[n-1]. mxp = 0; // 利 益 の 最 大 値 mxp を0に 初 期 化 for i=0 to n-2 for j=i+1 to n-1{ d = sp[j]-sp[i]; // 売 却 益 = 売 値 - 買 値 if d > mxp then mxp = d; // 今 まで 以 上 の 売 却 益 であればmxpの 値 を 更 新 する } mxpを 答 として 返 す; 改 良 1: 買 った 月 i を 固 定 すると,i 月 以 降 で 値 段 が 最 大 になったときが 最 良 の 売 り 月 j であるから, 毎 回 引 き 算 をしなくても, 最 大 値 を 求 めるだけでよい.(これで 引 き 算 の 回 数 が 減 る)
株 式 投 資 における 最 大 売 却 益 :(A) 方 式 入 力 : 毎 月 の 株 価 sp[0],..., sp[n-1]. mxp = 0; // 利 益 の 最 大 値 mxp を0に 初 期 化 for i=0 to n-2{ mxsp = sp[i]; // 株 価 の 最 高 値 mxsp を sp[i]に 初 期 化 for j=i+1 to n-1 if sp[j] > mxsp then mxsp = sp[j]; d = mxsp - sp[i]; // 売 却 益 = 買 値 とそれ 以 降 の 最 高 値 との 差 if d > mxp then mxp = d; // 今 まで 以 上 の 売 却 益 であればmxpの 値 を 更 新 する } mxpを 答 として 返 す;
株 式 投 資 における 最 大 売 却 益 :(B) 方 式 入 力 : 毎 月 の 株 価 sp[0],..., sp[n-1]. mxp = 0; // 利 益 の 最 大 値 mxp を0に 初 期 化 for j=1 to n-1{ mnsp = sp[j]; // 株 価 の 最 安 値 mnsp を sp[i]に 初 期 化 for i=0 to j-1 if sp[i] < mnsp then mnsp = sp[i]; d = sp[j] - mnsp; // 売 却 益 = 売 値 とそれ 以 前 の 最 安 値 との 差 if d > mxp then mxp = d; // 今 まで 以 上 の 売 却 益 であればmxpの 値 を 更 新 する } mxpを 答 として 返 す;
アルゴリズムの 効 率 それぞれのアルゴリズムにおける 繰 り 返 し 回 数 を 評 価 ) O(n (A) 2 1 ) ( 2 1 1) 2)( ( 2 1 1) ( 1 1 (A) : 2 2 2 n-2 0 i 2 2 0 n-1 1 i j は よって, 方 式 方 式 n n n n n n i n n i ) O(n (B) 2 1 1) ( 2 1 1 (B) : 2 2 n-1 1 j 1 1 j-1 0 i も よって, 方 式 方 式 n n n j n j O(n 2 ): n 2 に 比 例 する 程 度 の 量,ビッグオーn 2,またはn 2 のオーダ
アルゴリズムの 改 善 (A) 方 式 では, 各 i に 対 して,i 月 以 降 での 株 価 の 最 大 値 を 求 める MAX[i, n-1]: i 月 からn-1 月 までの 最 大 値 とすると, (A) 方 式 では,MAX[1,n-1], MAX[2, n-1],... の 順 に 計 算 MAX[i-1,n-1]の 値 がMAX[i,n-1]の 値 に 役 立 つか? NO! (B) 方 式 では, 各 j に 対 して,j 月 以 前 での 株 価 の 最 安 値 を 求 める MIN[0, j-1]: 0 月 からj-1 月 までの 最 安 値 とすると, (B) 方 式 では,MIN[0,0], MIN[0,1], MIN[0,2]... の 順 に 計 算 MIN[0,j-1]の 値 がMIN[0,j]の 値 に 役 立 つか? MIN[0, j] = min{ MIN[0, j-1], sp[j]} 配 列 を 探 索 しなくても,1 回 の 比 較 だけで 十 分. YES!
株 式 投 資 における 最 大 売 却 益 ( 改 良 版 ) 入 力 : 毎 月 の 株 価 sp[0],..., sp[n-1]. mxp = 0; // 利 益 の 最 大 値 mxp を0に 初 期 化 msf = sp[0]; // これまでの 最 安 値 msfをsp[0]に 初 期 化 for j=1 to n-1{ d = sp[j] - msf; // 売 却 益 if d > mxp then mxp = d; // 今 まで 以 上 の 売 却 益 であればmxpの 値 を 更 新 する if sp[j] < msf then msf = sp[j]; // これまでの 最 安 値 の 更 新 } mxpを 答 として 返 す; 上 記 のアルゴリズムの 計 算 時 間 は 明 らかにO(n)である.
線 形 配 列 上 での 直 近 上 位 要 素 問 題 : n 個 の 実 数 値 が 読 み 出 し 専 用 の 配 列 A[1..n]に 蓄 えられ ているとする. 各 要 素 A[i]に 対 して, A[i]より 大 きな 値 を もつ 要 素 の 中 でインデックスの 意 味 でA[i]に 最 も 近 い 要 素 ( 直 近 上 位 要 素 )を 求 めよ. 1 2 3 4 5 6 7 8 9 10 A 87 32 12 54 28 35 14 61 18 53 NLN 10 1 2 1 4 4 6 1 8 8 最 大 値
1 2 3 4 5 6 7 8 9 10 A 87 32 12 54 28 35 14 61 18 53 NLN 10 1 2 1 4 4 6 1 8 8 Algorithm 1: 単 純 な 双 方 向 スキャン for i=1 to n NLN[i] = -n; for d=1 to n-1{ if i-d 1 and A[i-d]>A[i] then NLN[i] = i-d; break; if i+d n and A[i+d]>A[i] then NLN[i] = i+d; break; } O(n 2 ) 時 間, 作 業 領 域 はO(1)
Algorithm 2: ダブルスタック 法 スタック S を 空 に 初 期 化 for i=1 to n{ // 左 から 右 にスキャン while( S が 空 でなくA[i] A[top(S)] ) pop(s); If ( S は 空 ) LNLN[i] = -n; else LNLN[i] = top(s); push A[i] onto S } スタック S を 空 に 初 期 化 ; for i=n downto 1 { // 右 から 左 にスキャン while( S が 空 でなくA[i] A[top(S)] ) pop(s); if( S は 空 ) RNLN[i] = -n; else RNLN[i] = top(s); push A[i] onto S; } for i=1 to n{ // 最 後 のスキャン if( I - NLN[i] RNLN[i] - I ) NLN[i] = LNLN[i]; else NLN[i] = RNLN[i]; } O(n) 時 間, O(n)の 作 業 領 域 省 メモリアルゴリズム?
定 理 [ 双 方 向 探 索 の 威 力 ] 配 列 要 素 はすべて 異 なると 仮 定 すると, 双 方 向 探 索 に 基 づくアルゴリズムの 計 算 時 間 はO(n log n)である. 証 明 d[i] = NLN[i] - i i=1,, n, を 要 素 A[i]からその 直 近 上 位 要 素 までの 距 離 とする. 最 大 値 A[j]についてはd[j]=nとする. このとき, 計 算 時 間 は 2(d[1]+d[2]+ d[n]) で 抑 えられる. k を 整 数 とし,D k = {d[i], d[j], } をd[]の 中 で 大 きい 方 から k 個 の 値 の 集 合 とし, C k を 対 応 するインデックスの 集 合 とする. そのような 要 素 のことを 重 い 要 素 と 呼 ぶことにしよう.
重 い 要 素 の 間 の 最 短 間 隔 をd k としよう (i, j) を 最 も 近 い 重 い 要 素 のペアとしよう. どの 要 素 も 異 なっているから,A[i]<A[j] または A[j]<A[i]で ある.したがって,d[i] d k または d[j] d k が 成 りたつ. d k は 高 々n/(k-1) であるから,これよりk 番 目 に 大 きなd[]の 値 は n/(k-1) で 抑 えられることが 分 かる. よって,dの 値 の 合 計 は 次 のようになる. n + n/1 + n/2 + n/(n-2) = O(n log n).