PDF資料

On-line Problems
Kyushu Institute of Technology

データ処理特論
Off-line問題

普通の問題
問題を解き始める前に、入力が完全に分かっている
最短経路探索問題
入力：グラフ
目的： s-t間の最短経路
オンラインアルゴリズム

宮野英次
九州工業大学情報工学部
制御システム工学科
[email protected]
実時間問題
On-line問題

時間が経過するに従って，入力が分かってくる
円からドルへの通貨交換問題
入力：為替相場
目的：なるべく多くのドルを手に入れる
http://tcs.ces.kyutech.ac.jp/~miyano/Classes
1
2
Ski Rental Problem
Kyushu Institute of Technology
Ski Rental Problem

スキー道具をレンタルするか，または，買うかを決める問題
レンタル：１千円/日
購入：
T 千円

このとき、できるだけ費用（コスト）を少なくしたい
Cost = （レンタルした日数）×1千円 + T千円
仮定１：一度スキーを買ったらシーズン終了まで壊れない
仮定２：毎日スキーに行く
オンラインアルゴリズムの評価基準
competitive ratio （競合比）
問題：何日目にスキー道具を購入すれば良いか？
3
Off-line の場合

4
On-line の場合
On-lineの場合：シーズン開始時にＬを知らない
On-line Algorithm
整数 k を決める（0 ≤ k ≤ L）
始めのk日はレンタルして，もしk+1日目もシーズンが続いて
いるなら k+1 日目にスキー道具を購入
スキーシーズンの長さをＬとする
Off-lineの場合：シーズン開始時にＬを知っている
L < T ならシーズン中ずっとレンタルで済ます（Ｌ千円）
L ≥ T なら初日にスキー道具を買う（Ｔ千円）
Cost
Cost
例えば
k=0（初日に買う）
k=2（3日目に買う）
T
T+2
T
L
L
T
T
5
6
1
競合比（評価尺度）
競合比の例

オンラインアルゴリズムＡはα-競合（α-competitive）
オンラインアルゴリズムＡはα-競合（α-competitive）

k = 0（初日に買う）としたとき
初日に買ったが，シーズンが1日で終わった

任意の入力列σ
オンラインアルゴリズムＡのコスト CA(σ)
最適オフラインアルゴリズムOPTのコストを COPT(σ)
とするとき，

オフライン：レンタルで済ますことでコストは１千円
オンライン： T千円で購入
⇒ Ｔ-competitive

C A (σ ) ≤ αCOPT (σ )
が成り立つならば，オンラインアルゴリズムＡはα-競合
である（Aはα-競合比を持つ）と言う
k = T – 1 としたとき
Ｔ日以上続いた場合（L≥T）

オフライン：初日に購入することでコストはT千円
オンライン： T-1日分はレンタル（T-1千円），その後T千円で購入
⇒ (2 ‐ 1/T)-competitive

αの値が1に近いほど良いオンラインアルゴリズム
7
8
最適オンラインアルゴリズム
最適性の証明
On-line algorithm：
k を最初に決め，k+1日目にスキー道具を購入する

最適On-line algorithm：
k = T – 1 と決める

オンラインアルゴリズムのコスト
CA = k + T
最適なオフラインアルゴリズムのコスト
 L if L < T (L :シーズン期間)
CMIN = 
T otherwise
スキー道具がＴ千円のときは，Ｔ日目に購入する
定理
k = T – 1 のとき，competitive ratio が最も

シーズン期間Lが最初に決めたkより小さいとき
競合比＝１
小さい（ = 2 – 1/T ）
9
10
最適性の証明

L = k+1 だと仮定して，競合比を見積もる
（L>>k+1 のときは，競合比は小さくなっていく）
競合比 α = C A CMIN は，L<T の時：
α=

L −1+ T
T −1
1
= 1+
≥ 2 > 2−
L
L
T
Paging Problem
k=L–1
L ≥ T の時：
α=

Kyushu Institute of Technology

L −1+ T
L −1
1
= 1+
≥ 2−
T
T
T

最適オフラインアルゴリズム
最適オンラインアルゴリズム
L=k+1のとき，α ≥ 2 − 1 T なので，任意のLに対し α ≥ 2 − 1 T
11
12
2
Paging Problem
Paging Problem

kページ分の高速アクセス可能なメモリーを持つコンピュータ

キャッシュ ⇔ ディスク間のページ入れ替え
メモリ上に無いページ σ i へのアクセス要求が来た場合
（page fault），メモリ上のどれかのページと σ i を入れ換える
（page swap）

1 6 3 4
2
5
入力：ページアクセス要求列 σ 1 , σ 2 , σ 3 ,L
問題：メモリ上のどのページと入れ換えるか？
目的：なるべくコスト（page fault の回数）を少なくしたい
1 6 3 2
ページ2への
アクセス要求
↓
page fault
↓
page swap
page fault
1 6 3
4
5
要求 2
page fault
1 6 2
1 6 3
要求 3
13
14
LIFO vs FIFO
様々な戦略

LIFO (Least In Fast Out)
replace the page most recently placed in fast memory

FIFO (First In First Out)
replace the page that has been in memory longest

LRU (Least Recently Used)
replace the page whose most recent access is earliest

LFU (Least Frequently Used)
replace the page that has been accessed the least

FWF (Flush-When-Full)
replace any unmarked page and mark the requested
page. Whenever all pages in fast memory are marked,
unmarked them all
[例] k = 3，要求列〈3, 2, 1, 4, 5, 2, 1〉
LIFO： {3, ○, ○} ⇒ {3, 2, ○} ⇒ {3, 2, 1} ⇒ {3, 2, 4}
⇒ {3, 2, 5} ⇒ {3, 2, 5} ⇒ {3, 2, 1}
FIFO： {3, ○, ○} ⇒ {3, 2, ○} ⇒ {3, 2, 1} ⇒ {4, 2, 1}
⇒ {4, 5, 1} ⇒ {4, 5, 2} ⇒ {1, 5, 2}
page fault の回数： LIFO 3回，FIFO 4回
しかし，LIFO は competitive ではない
[例] k = 3，要求列〈…, a, b, a, b, a, b, a, b, …〉
LIFO： …⇒ {○, ○, a} ⇒ {○, ○, b} ⇒ {○, ○, a} ⇒ …
FIFO： …⇒ {○, ○, a} ⇒ {○, a, b} ⇒{○, a, b} ⇒ …
どんなαを用いても CLIFO ≤ αCFIFO ≤ αα ' CMIN と表せない
15
16
Optimal Off-line Algorithm
LRUの解析
定理 LFDアルゴリズムは，最適なオフラインアルゴリズム

定理 LRU は k-competitive である
LFD (Longest Forward Distance)
replace the page among the pages currently in
memory, whose next request comes last

定理すべてのアルゴリズムAに対して，
CA (σ A ) ≥ k ⋅ CLFD (σ A )
となる要求列 σ , σ ,L, σ
A
1

A
2
A
n

が存在

もしも，k-competitive なオンラインアルゴリズムが存在する
としたら，そのアルゴリズムは最適である
17
LRU はどんなページ要求列に対しても，最適なオフラインア
ルゴリズムの k 倍以下のページフォルト数で処理可能
LRU が最も優れたオンラインアルゴリズムの一つ
LRU (Least Recently Used)：
replace the page whose most recent access is earliest
MIN：
最適なオフラインアルゴリズム
18
3
最適性の証明（１）

メモリの初期状態は LRU，MIN とも同じ
メモリの最初の k ページがどんなものであったとしても，すべ
ての入力σに対して， CLRU (σ ) ≤ k ⋅ CMIN (σ ) である
σ = σ 1 ,σ 2 ,L, σ{i , [σ i +1 ,Lσ j ], [σ j +1 ,L,σ l ],L
14243 14243
phase 1

ある一つのphaseを考える
定義より，LRUはこのphaseで k 回のPFが起きる
以下の２つの場合：
（Case 1）
このphaseでLRUが，あるページpに対して２回ＰＦを起こす
ある入力σに対する LRU の動作を考える
σを次のように phase に分けて考える
最初のPF

最適性の証明（２）
（Case 2）
このphaseではLRUは異なるkページに対してＰＦを起こす
ここで，MINのPFの回数を見積もる
MINは，このphaseで１回以上PFを起こすことを示す
phase 2
ただし，各phaseは正確にk個の page fault (PF)を含む
と仮定
19
20
最適性の証明（３）
最適性の証明（４）
（Case 2）今考えているphaseの前のphaseの最後のPFが
ページpの要求で起こったとする
（Case 1）
このphaseでLRUが，あるページpに対して２回ＰＦを起こす
L, [σ i+1 ,L, σ p1 = p,LL, σ p1 = p,L, σ j ],L
L, σ i = p, [σ i+1 ,LL, σ j ],L
144244
3
current phase
LRUの動作より
σp1 とσp2 の間にpと異なるk個以上のページ要求がある
（σp2 が要求されたときには，pがメモリに無いから）
（Case 2a）このphaseでページpのPFが起きる
L, σ i = p, [σ i+1 ,L, p,L, σ j ],L
1442443
current phase

このphaseでは，合計で k+1 個以上のページ要求がある
σi と p の間に異なるkページの要求がある
このphaseで異なる k+1 ページの要求がある
MINでも１回以上PFがある
MINでも最低１回のPFがある
21
22
Optimal Off-line Algorithm
最適性の証明（５）
（Case 2b）このphaseでページpのPFが起きない
ただし，LRUについてもMINについても，このphase開始時
点ではメモリ中にpが含まれている

定理 LFDアルゴリズムは，最適なオフラインアルゴリズム

定義より，このphaseではLRUではk個の異なるページに対
して，PFが起こっている
p以外のkページへの要求が生じる
どんなにうまくMINが動作したとしても，phase開始時にpがメ
モリに含まれているなら，必ず１回はPFが起こる
LRUがk回PFを起こす間に，MINは最低１回はＰＦを起こす
つまり，LRUは k-competitive （ CLRU (σ ) ≤ k ⋅ CMIN (σ ) ）
[Q.E.D]
23
LFD (Longest Forward Distance)
replace the page among the pages currently in
memory, whose next request comes last
証明：
LFDより良いアルゴリズムMINが存在すると仮定して矛盾を
導く（背理法，proof by contradiction）
¾
仮定：
C LFD (σ ) > C MIN (σ ) となる入力列が存在する
σ = σ 1σ 2 Lσ n
24
4
証明の続き（１）
¾
¾

¾
¾

証明の続き（２）
MINとLFDの動作が初めて異なる時刻：時刻 i
σi までのメモリ内容は全く同じ

「i < j < t の間，MIN*とMINは共通の k – 1 ページをメモリに
持つ」ことを示す
時刻iでは必ずMIN，LFD両方でPFが起きている
⇒ MIN，LFDがそれぞれ p，q をメモリから削除したとする
時刻i以降で，MINが初めてqを削除する時刻をtとする
MINの動作を，時刻i∼時刻tの間だけLFDと同じになるよう
に変更したMIN*が， CMIN * ≤ C MIN (σ ) となることを示す
LFDの定義より，次のページpの要求σa は，次のページqの
要求σb より先に生じる
(Case 1): i < t < b

MIN*が持っていて，MINが持っていないページを e で表す
（MINが持っていてMIN*が持っていないものは q）
induction on j
σj ≠ e:

MIN*がPF ⇔ MINがPF
MIN*はMINと同じページを削除する
σ = σ 1σ 2 Lσ i Lσ a (= p )LLσ b (= q )Lσ n
25
26
証明の続き（３）
証明の続き（４）
(Case 2): t õ b
σj = e:

MIN は PF，しかし MIN* はPFでない
MIN: { …，δ，q} → { …，e，q }
MIN*: { …，δ，e} → { …，δ，e}

LFDの定義より q (=σb)の要求がある前に，pの要求がある
(Case 1)の σj = e のケースが最低1回は起きている．
CMIN * (σ 1 Lσ b−1 ) < CMIN (σ 1 Lσ b−1 )
また，j = t では，MINはqを削除し，MIN*はeをすてることにする
MIN: { …，q } → { …，σt }
MIN*: { …，e } → { …，σt }
となり，結局，またMINとMIN*は同じ動作を続けることになる．

時刻bでは，MINはPFを起こさないが，MIN*はPFを起こすので，e と
q と入れ換える．よって，
CMIN * (σ ) < CMIN (σ )
(Case 1)と(Case 2)より， CMIN * (σ ) < C MIN (σ )
よって，この場合，
であるが，
C LFD (σ 1 Lσ t ) = CMIN * (σ 1 Lσ t ) < CMIN (σ 1 Lσ t )
CMIN * (σ ) ≤ CMIN (σ )
⇒ tのinductionにより， C LFD (σ ) < CMIN (σ ) となり仮定と矛盾
27
28
オンラインアルゴリズムの下限
補題の証明
A
A
定理全てのアルゴリズムAに対して， CA (σ ) ≥ k ⋅ CLFD (σ )
となる要求列 σ A = σ 1A , σ 2A ,L, σ nA が存在
補題
k+1ページから選ばれた有限列σに対して， k ⋅ C LFD (σ ) ≤ σ
証明：
全体で k+1 種類のページしかないとする
Aの動作にとって都合の悪い例を作る（adversary）
A
A
Aに対して， σ 1 Lσ i −1 を与えたときにメモリ中のkページ
に含まれていない残りのページを σ iA とする
C A (σ ) = σ
Aは各ページ要求毎にPFを起こす ⇒

補題： k+1ページから選ばれた全ての有限列σに対して，
k ⋅ C LFD (σ ) ≤ σ
C A (σ ) / C LFD (σ ) ≥ k
LFDがσiに対してPFを起こしたとする．このとき，メモリから
削除されたページをpとする

[Q.E.D]
29
LFDの定義より，次にpの要求が来る前に他のkページの要求が来る
σiまで終わった時点でメモリには，p以外のページ全てが含まれる
次にPFが起こるのは，σi+k-1 以降になり，そのときに要求さ
れるページはp
PFの起こる間隔は，k – 1 であり，高々k回に１回しかPFは
起きない
30
5
Metric Space
Kyushu Institute of Technology
定義：
metric space は，以下のような距離の関数 d : (V × V ) → ℜ
を持つ点集合Ｖである
k-Server Problem

1. d (u , v) ≥ 0, ∀u , v ∈ V
2. d (u , v) = 0 iff u = v
3. d (u , v) = d (v, u ), ∀u , v ∈ V
4. d (u , v) + d (v, w) ≥ d (u, w), ∀u , v, w ∈ V
最も盛んに研究が行われている
あまり結果が知られていない

d は（１）非負，（２）異なる２点間は真に正，（３）三角不等
式を満たす，（４）対称性を持つ
31
32
k-Server Problem
応用（１）
定義：
入力： metric space V，Vの点に置かれたk個のserver，
要求列σ1，σ2，．．．
目的：すべてのserverが移動する距離の総和を小さくする
15
10

Paging Problem
k個のserverをk個のメモリセル，Vを d (u , v ) = 1, u ≠ v
であるようなページの集合とする
あるserverを a から b へ動かす
⇒ ページaを削除して，ページbと入れ換える
20
12
7
9

k-server問題は，より一般的な問題

15
高速なメモリにあるページを持ってくるコストがページサ
イズに依存するような場合に対応する
Claim：オフラインの場合もオンラインの場合も，任意の要求
列に対して，それぞれの要求の際に１つのserverのみ移動
させれば良い
33
34
応用（２）

競合比の下限と上限の予想
Two-headed Disk

同心円状のトラック
2つのディスクヘッドは，トラックからトラックに直線的に移動
2つのヘッドは同じ場所に行くことはなく，交わることはない
定理 (Manasse-McGeoch-Sleator，1990)：

目標：ディスクのI/O要求に対して，2つのヘッドが動く距離の総和を
小さくする

Aを任意のmetric spaceにおける，k-server問題に
対するオンラインアルゴリズムであるとする．
α ≥k
もしAがα-competitiveであるならば，
予想：
k-competitive であるオンラインアルゴリズムが存在
35
36
6
特別なk，特別なMetric Space
既知の結果

特別なkの値に対する既知の結果
k=1
1-competitive algorithm
k=2
2-competitive algorithm
k=|V|–1
|V|–1-competitive algorithm

特別なmetric spaceに対する既知の結果
Paging
k-competitive algorithm
Line, tree
k-competitive algorithm
Circle
k3-competitive algorithm
定理（Fiat-Rabani-Ravid，1990）：

eO ( k log k ) - competitive algorithm
定理（Koutsouplass and Papadimitriou，1994）：

(2k − 1) - competitive algorithm
Open Problem
k-competitive アルゴリズムは存在するか？
37
38
Greedy Algorithm

k-server問題は何故難しいのか？
貪欲戦略Greedy：常に一番近いserverを動かす
定理： Greedyはcompetitiveではない
Sketch
2個のserver，要求列 a, b, a, b, a, b, ．．．を考える
1

Greedyの競合比は∞

一般の場合はかなり難しい
2
a
b
39
7

Download Report