最小遅延パス問題に対する近似アルゴリズムの研究

1/4

中野 慎太郎

最小遅延パス問題に対する近似アルゴリズムの研究

A Study of Approximation Algorithms for the Minimum Latency Path Problem

情報工学専攻 中 野 慎 太 郎

NAKANO Shintaro

概要 無向グラフにおいて, 与えられた始点から終点 まで, 与えられた点数以上の点を通るようなパスで長 さ最小のものを求める問題を最小遅延パス問題という.

本研究では,この問題に対し

Chaudhuri, Godfrey, Rao and Talwar [1]

が

2003

年に提案した近似アルゴリズム を 実装し, 計算機実験を通してその近似性能を評価す る. さらに,近似性能や計算時間などの観点から

2

つの 改善手法を提案し,各々の実験的性能評価を行った.

1

序論

メトリック空間上の無向グラフにおいて,各点におけ

る遅延

(latency)

を最小にするようなパスを求める問

題を最小遅延パス問題

(Minimum Latency Path prob-

lem, MLP)

という. この問題は

NP-困難で,

一般的な

グラフに対しては

MaxSNP-困難であることがそれぞ

れ証明されている. また,類似の問題として巡回修理工 問題

(Traveling Repairman Problem, TRP),

スクール バスドライバー問題

(school-bus driver problem),

配 達人問題

(delivery man problem)

が挙げられ,現実的 な問題への応用も模索されている.

この問題に対して, Chauduri, Godfrey, Rao and Tal-

war [1]

は

2003

年に同期的プライマルデュアル法

(syn- chronized primal-dual algorithm)

を用いた近似アルゴ リズムを提案した. その内容は

MLP

に対するラグラ ンジュ緩和問題

(Lagrangian relaxation)

を解いていく というものである. そこで本研究ではそのアルゴリズ ムを実装し, 計算機実験を通してその近似性能を評価 した. さらに,近似性能や計算時間などの観点からより 効率的なアルゴリズムを目指し, 2つの改善手法を提案 し,各々について実験的性能評価を行った.

2

問題定義

重みつき無向グラフ

G = (V, E, c)

に対してパス

P = (v

1

, ..., v n )

を考える.

V

は点集合,

E

は辺集合,

c

はコストをそれぞれ表している. パス

P

における点

v i ∈ P

の遅延

(latency) l v

_i

,P

とは,点

v i

に到達するま でのパス

P

のコスト, すなわち

l v

_i

,P = c((v

1

, ..., v i ))

と表すことができる. MLP の目的は, グラフ

G

にお いて, 各ノードの遅延の総和が最小になるようなパス を求めることである. 本稿で扱う問題は,

k-

パス問題

(k-path problem)

と呼ばれるものであり,始点

s

から 終点

t

まで, 少なくとも

k

個以上のノードを通るパス のうち,最短のものを求める問題である.

図

1

は

C++クラスライブラリ LEDA

を用いて

100

個の点, 200個の辺を入力として与えたときの様子を図 示したものである. なお,始点

s

は緑色,終点

t

は赤色

でそれぞれ表現されている.

図

1

のようなグラフに対して,例として

k = 50

とし た場合には図

2

のようなパスが出力される. この場合 は

74

個の点を通るようなパスが出力されている. なお,

s, t

を除いて, 辺が奇数本の点, すなわち, 次数が奇数 の点においては, 接続する辺のうちちょうど

1

本がパ スによって

2

回辿られるものとする.

図

1

入力例 図

2

出力例

3 Chaudhuri

らのアルゴリズム

[1]

3.1

線形緩和問題

Chaudhuri

らのアルゴリズムは,

s

から

t

までの

k-

パス問題に対する線形緩和問題とその双対問題を用い ている. 以下に線形緩和問題

(主問題)

を記す.

min ∑

e

∈

E

c _e x _e (1)

s.t. ∑

e

∈

δ(S)

x _e ≥ 2x _v ∀ S ⊆ V \{ s, t } , ∀ v ∈ S

∑

e

∈

δ(U)

x e ≥ 1 ∀ U ⊆ V : t ∈ U, s 6∈ U

∑

v

∈

V

\{

s,t

}

x v ≥ k − 2

0 ≤ x _v ≤ 1 ∀ v ∈ V \{ s, t } x e ≥ 0 ∀ e ∈ E

x e

は辺

e

がパスに含まれるなら

1,

そうでなければ

0

をとる変数で,

x _v

はパス上の

s, t

を除く

(k − 2)

個以 上の点で

1,

それ以外では

0

をとる変数を表している.

δ(S)

は一方の端点のみが点集合

S

に含まれるような辺 の集合を示している.

2/4

中野 慎太郎

主問題

(1)

に対する双対問題を以下に記す.

max (k − 2)p − ∑

v

∈

V

\{

s,t

}

p v + ∑

U

:t∈

U,s

6∈

U

y t,U (2)

s.t. 2 ∑

S

3

v

y v,S + p v ≥ p ∀ v 6 = t

∑

S:e

∈

δ(S)

∑

v

∈

S

y v,S

+ ∑

U:t

∈

U,e

∈

δ(U)

y t,U ≤ c e ∀ e ∈ E

p _v ≤ 0 ∀ v ∈ V

y v,S ≥ 0 ∀ S ⊆ V \{ s, t } , ∀ v ∈ S y t,U ≥ 0 ∀ U ⊆ V \{ s } : t ∈ U 3.2

アルゴリズム

入力としてグラフ

G = (V, E),

始点

s ∈ V ,

終点

t ∈ V

及びパラメータ

λ

が与えられる. アルゴリズム は

2

つのフェイズ, 反復を繰り返し辺を追加していき 木を求める

Growth Phase

と木から余分な辺を除去す る

Delete Phase

より構成されている.

Growth Phase

アルゴリズムにおいて, グラフは活性集合

(active component)

か 不活性集合

(inactive component),

ど ちらかに分割されるものとする. 各点

v

は非負の予算

(budget) b _v

を持ち,

v

が含まれる集合の成長に寄与す る. 正の予算を持つ点を含み, かつ

s

を含まない集合, もしくは

t

を含む集合が活性集合となり, すべての点 が予算

0,

もしくは

s

を含む集合が不活性となる. 初期 状態においては,各点はそれぞれ集合を構成しており,

s

は予算

0, t

は予算

∞ ,

その他すべての点は予算

λ

を それぞれ持つ. なお,変数

y v,S

は各点

v

が集合

S

に含 まれているときに,どれだけ「支払った」かを表してお り,その初期値は

0

である.

以下にアルゴリズムを記す.

1.

小さな値

²

と各活性集合

S

から点

v S

を選ぶ.

2. ²

だけすべての点の

λ

を減らす.

²

だけ各

v _S

に対応する

y _v,S

を増やす.

このとき,

²

は以下の

1

か

2

どちらかを満たすよう に選ばれるものとする.

1. b v

_S

= 0

となるように

²

を選ぶ. なお,

b v

_S

= 0

と なったときは, 他の

b _v > 0

の点

v ∈ S

が選ばれ る. そのような点がなければ

S

は不活性となる.

2. y v,S

が辺

e ∈ E

に「支払う」ことで集合

C

1と

C

2が併合できるように

²

を選ぶ. このとき併合 した集合に

s

が含まれるなら不活性となる.

Growth Phase

は以上の操作を繰り返し, 各段階で

選ばれた辺を記憶しておき, すべての集合が不活性と なった時点で終了する.

Delete Phase

Growth Phase

により得られた

s

を含む集合を

T

と する. 得られた

T

は木となっている. ここで, Growth

Phase

の中で不活性集合を形成したことのあるすべて

の部分木

S ⊆ T \{ s }

を除去する. 除去することで得ら れた木

T _k

_λ と

y _v,S

を返して終了する.

4

提案手法

(1)

Chauduri

らのアルゴリズムは

s

と

t

以外のすべての

点に対して一律に同じ予算

λ

を与えている. そこで,

λ

を一律ではなく, 距離などの条件を与えて変化させる ことにより,解の改善及び計算時間の短縮化を図った.

λ

を一律に与えるのではなく,各辺のコストを距離とし て考え,始点

s

と終点

t

双方からある距離

d

以上の点を

「遠い」点と呼び,その集合を

V _F

と定義する. また,

s, t

双方から

d

以内の点集合を「近い」と呼び

V N

と書く ことにする. 与えられた点集合を

V N

と

V F

に分割し, それぞれに異なる予算

λ

を与えることにする.

5

実験的性能評価

(1)

実験にあたって, 本研究では配送計画問題

(Vehicle Routing Problem, VRP)

に対する著名な例題である,

Solomon

のベンチマーク¹を入力データとして用いた.

顧客が密集している配置の

C

タイプ,ランダムな配置 の

R

タイプの

2

タイプの例題をそれぞれ入力とした 実験を行った. 図

3

は

C

タイプの問題

“C101”

の入力 を,図

4

は

R

タイプの問題

“R101”

の入力をそれぞれ

(x, y)

座標上に示したものである.

0 10 20 30 40 50 60 70 80 90

0 20 40 60 80 100

x座標 座y

標

図

3 C101

0 10 20 30 40 50 60 70 80 90

0 20 40 60 80

x座標 y

座 標

図

4 R101 V _N

と

V _F

への

λ

の与え方に差異をつけ,それぞれの 集合の個数を変化させ実験を行い, パスの長さ及び計 算時間の計測を行った.

V _N

の個数,

V _F

の個数はそれぞれ個数の比率が約

1 : 1, 2 : 8, 8 : 2

となるように

s

と

t

からの距離を与え た. また, 点の予算は入力

λ

に対し,

V _N , V _F

の点そ れぞれに定数倍したものを組合せることにする. 表

1

は各データタイプとその番号を示している. 例として

“n*1.25 f/1.75”

であれば

V _N

に予算

λ × 1.25, V _F

に予 算

λ ÷ 1.75

をそれぞれ与えることになる.

図

5,

図

6

にそれぞれ

C101, R101

に対して距離

d

を 変化させ,

V N , V F

の個数比を変化させたときの各デー タタイプに対するパスの長さの変化を示している.

始点・終点に「近い」

V _N

に多く予算を与えることに よって

V N

に属する点ばかりで構成された,短いパスが 得られるものと期待していたが, 必要以上に多くの点 を取り込みすぎる結果となった. これは,アルゴリズム の各段階において, 与えられた

λ

に対して所望の

k

を 得ることができなかった場合には

λ

の値を増やして繰 り返すという操作が原因だと考えられる.

| V _N | : | V _F |

の比率を約

(1)2 : 8, (2)1 : 1, (3)8 : 2

ととり実験を行ってきたが,実際には同じ反復回数

(同

1

M. M. Solomon http://w.cba.neu.edu/ msolomon/home.htm

3/4

中野 慎太郎

じ

λ)

で得られた木の長さを比較してみるとその長さ は

(1)<(2)<(3)

という順序になっていることがわか る. 表

2

は, R101においてデータ

(22)

を適用した際 に,

λ = 3

によって得られた解のパスの長さを比較した ものである.

これらの結果から,得られた木の点数をできるだけ抑 えることが解の改善に繋がることになると考えられる.

表

1

データタイプ

番号 データタイプ 番号 データタイプ

1 n*1.0 f/1.0 12 f*1.0 n/1.75 2 n*1.25 f/1.25 13 f*1.0 n/2.0 3 n*1.5 f/1.5 14 f*1.25 n/1.25 4 n*1.75 f/1.75 15 f*1.5 n/1.5 5 n*2.0 f/2.0 16 f*1.75 n/1.75 6 n*1.25 f*1.0 17 f*2.0 n/2.0 7 n*1.5 f*1.0 18 n*1.0 f*0 8 n*1.75 f*1.0 19 n*1.25 f*0 9 n*2.0 f*1.0 20 n*1.5 f*0 10 f*1.0 n/1.25 21 n*1.75 f*0 11 f*1.0 n/1.5 22 n*2.0 f*0

0 500 1000 1500 2000 2500

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 データ番号

パス の長 さ

d=10 d=30 d=50

図

5

実験結果: C101

表

2 R101:

データ

(22)

の同じ反復回数での比較

d

パスの点数 パスの長さ

20 43 888.370339

30 50 1024.328474

40 70 1362.730144

6

提案手法

(2)

入力

R101

に対して,

d = 20

と設定した場合のデー タ

(9)

に対してアルゴリズムを適用したとき,

λ = 3

か ら開始した場合,

λ = 4.5

となったときに

71

個の点数 をもつパスが得られて解が返された.

λ

は各反復で

0.5

ずつ増加させているため, アルゴリズムは

4

個の

λ

に ついて計算を行ったことになる. その各反復ごとで求 められたパスの点数とパスの長さを比較したものが表

3

となっている.

0 200 400 600 800 1000 1200 1400 1600 1800 2000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 データ番号

パス の長 さ

d=20 d=30 d=40

図

6

実験結果: R101

このような前章の実験結果でみられた,最終的な解の 木の点数が多くなってしまうようなデータについては,

k

が得られる直前の

λ

による解

(表 3

の例では

λ = 4

のとき)は,

k

に近い点数の木を得ることができている 場合が多い.

表

3 R101:

データ

(9) (d = 20)

の異なる

λ

での比較

λ

パスの点数 パスの長さ

3 43 881.053313

3.5 43 881.053313

4 44 883.19111

4.5 71 1402.599017

このような入力データに対して, 解の点数を極力抑 えるために,その直前の反復で得られた解を利用する.

具体的な流れは以下のようになる. まず,アルゴリズム の各段階で

1

つ前の

λ

によって得られた木

T

⁰を記憶 しておく. そして,アルゴリズムの反復が終了した際に 木

T

⁰に,点数が

k

になるまで

T

⁰に含まれる点に付随 する辺のうち,

T

⁰を構成しない辺の中から長さが短い 辺を選択し,

T

⁰に追加していく. こうして得られた

T

⁰ のコストを求め,本来の

λ

により得られた木のコスト と比較し, コストのより低い方を解として返してアル ゴリズムを終了する.

表

3

の例では

λ = 4

に対する解が記憶されており,

これに

50 − 44 = 6

個の点を追加し,そうしてできた木

のコストを

λ = 4.5

によって得られた木と比較すると いった流れになる.

7

実験的性能評価

(2)

7.1 C101

に対する実験結果

図

7

は, C101に対して実験を行ったときの,

d

の変 化とパスの長さの関係を表したグラフである.

d

を

10, 30, 50

としたいずれの場合にも,解を改善す ることができたのはデータ

(1), (10)〜(13)

のみであり, 得られたパスはいずれも同じものとなった.

改善することのできなかったデータタイプは, いず れも最初に入力した

λ

によって解がすぐに得られてい ることがその原因と考えられる.

4/4

中野 慎太郎

0 500 1000 1500 2000 2500

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 データ番号

パス の長

さ d=10

d=30 d=50 提案(2)

図

7 C101: d

の変化とパスの長さの関係

7.2 R101

に対する実験結果

図

8,

図

9,

図

10

は, それぞれ

d = 20, 30, 40

の場合 における, 各データタイプについての提案手法

(1)

と

(2)

のパスの長さを比較したグラフである.

R101

に対しては, C101を入力としたときとは逆に,

V _N

に多く予算を与えたときのみ,いずれの

d

において も提案手法

(1)

による解からの改善ができていること がわかる.

d = 20, d = 30

の場合は, いずれもデータ

(2)

と

(6)

以外はデータ

(1)

よりも短いパスが得られて いる. 一方,

d = 40

では, パスの長さを改善すること のできたデータ数は減少した. しかし,

V _N

と

V _F

に与 える予算の差を大きく設定した場合にはパスの長さは さらに短いものとなっている. これは当初の狙い通り,

V _N

の個数の比率を多く,予算も多く与えることで多く の

V N

の点を取り込み,

V F

への辺は減らすということ に成功しているからである.

8

結論

提案手法

(1)

では

Chaudhuri

らの手法をすべての場

合で改善することはできず,求めたパスの点数が多くな りすぎてしまうことが原因でパスの長さが長くなって しまうケースもあった. 一方,提案手法

(2)

は入力デー タに依存してしまうという側面はあるものの, R101の ようなランダムな入力に対しては

V N

の個数を多くと

0 200 400 600 800 1000 1200 1400 1600 1800 2000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 データ番号

パス の長 さ

提案(1) 提案(2)

図

8 R101: d = 20

でのパスの長さの変化

0 200 400 600 800 1000 1200 1400 1600 1800 2000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 データ番号

パス の長 さ

提案(1) 提案(2)

図

9 R101: d = 30

でのパスの長さの変化

0 200 400 600 800 1000 1200 1400 1600 1800 2000

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 データ番号

パス の長 さ

提案(1) 提案(2)

図

10 R101: d = 40

でのパスの長さの変化

り, さらに予算を多く与えることでパスの長さを大幅 に短くすることができた.

今後の課題としては, どのような入力に対しても良 質な解を求めることのできるアルゴリズムの提案, 大 規模なデータに対しても適用するための計算時間の大 幅改善などが挙げられる.

謝辞

本研究を進めるにあたり，適切なご指導・ご指摘を 頂きました浅野孝夫教授に心から感謝致します．

参考文献

[1] K. Chaudhuri, B. Godfrey, S. Rao, K. Talwar: Paths,

Trees, and Minimum Latency Tours. In Proceedings of

the 44th Annual IEEE Symposium on Foundations of

Computer Science, Massachusetts, 2003, pp.36-45.