スライド 1

オンライン追跡問題
藤原 洋志
関西学院大学 理工学研究科・ヒューマンメディア研究センター・博士研究員
ルール：
„ 各時点でロボットは領域内に
„ 次時点の領域がどこか不明
„ 目的：総移動距離を小さく
2
貪欲アルゴリズム
現時点から最短で追跡
常に現時点から最短で
5
…
1
神様のアルゴリズム
未来を見通して最短で追跡
常に現時点から最短で追跡
4
3
本研究で証明した定理
貪欲アルゴリズムの総移動距離は、必ず
神様のアルゴリズムの総移動距離の2倍以下である
オンラインアルゴリズムとは…
正ｎ角形の場合、
ｎが奇数なら 1/sin(π/(2n))倍以下、
ｎが偶数なら 1/sin(π/n)倍以下
„ 現時点で不明な情報を入力とするアルゴリズム
このオンライン追跡問題のアルゴリズム
コンピュータ上のキャッシュメモリのページング
‡ かな漢字変換候補リスト管理
‡ 株取引・通貨交換
‡
次はどこ?
‡
6
6
2
„ 良いオンラインアルゴリズムの基準は？
性能基準の変遷: 利得期待値から競合比へ
1.41
3.24
2
正方形については貪欲アルゴリズムが最適
（これ以上改良不可能）
利得期待値 = E[アルゴリズムの利得]
‡
‡
‡
入力に確率分布を仮定した平均評価
古典的手法
弱点： 確率分布や入力生成に大きく依存
この問題の応用例
„ 移動無線中継車
„ 兵站計画
競合比 = max(神様のアルゴリズムの利得 / アルゴリズムの利得)
最悪評価
未来を見通す「神様のアルゴリズム」にどれだけ近づけるか？
‡ 1万円の利得を得るアルゴリズムAとBがあったとする。Aはうまくや
っても2万円。Bは、うまくやれば10万円儲けることができたはず。
→ Bのアルゴリズムがマズかったのでは？こういったことを評価可能
‡
‡
競合比を用いた種々の結果
„ ページング：LRUアルゴリズムの最適性[Sleator, Tarjan]
„ リスト管理：MTFアルゴリズムの最適性[Sleator, Tarjan]
„ 株取引・通貨交換：脅威原理アルゴリズム[El-Yaniv et al.]
シンポジウム 「ヒューマンメディアの未来」
アルゴリズム改良に向けて
„ 貪欲アルゴリズムはｎが大きくなると性能悪化
„ そこで仕事関数アルゴリズム
‡
‡
‡
アイデア：現時点までの最短経路を計算
幾つかの特徴的な領域出現パターンについて解析
一般の領域出現パターンについては未解決
HUMAN CENTERED MEDIA FOR FUTURE SOCIETY
関西学院大学