Rounded Dynamic Programming for Tree-Structured Stochastic Network Design
-
Xiaojian Wu, Daniel Sheldon, Shlomo Zilberstein
-
AAAI 2014
-
Xiaojian WuにはAAAIでお会いした
-
このグループはあくまでStochastic Network Designとして捉えているっぽい(影響最大化も)
概要
-
有向木上の確率的ネットワーク設計に対する丸め動的計画法
-
河のネットワークでの状況を想定できるらしい
-
FPTASでO(n^2/ε^2)だけど実験的にはもう少し速い(し精度も良い)
動機付けとか
-
リバーネットワーク(?)の階層的構造を木構造で表現
-
その応用は障害除去による保全計画
-
頂点に拡散する確率が分かってこれが目的関数
-
O’Hanley and Tomberlin (2005)が主となる先行研究らしい
問題定義
-
fish barrier removal problem (魚の障害除去問題)
-
色々取り除いて魚が通りやすくしたい
-
魚達は木T=(V,E)を辿りソース(海)sを目指す
-
各頂点は障害u⊆Bか合流点u⊆V\B
-
魚は障害uを確率p_uで通れる
-
各頂点にはいくつかの修復行動A_uがあって,aを使うとコストc_uaで確率がp_u|aに上昇
-
行動の方策πが固定され下でのアクセス性P^+_{u|π}(めんどいので以下略)とは
-
もっと一般に$$ P^+_{v \rightarrow u \mid \pi} $$をvからuへの確率
-
頂点には報酬r_uがある
-
目的関数は$$ z(\pi) = \sum_{u \in V}P^+_{u \mid \pi}\cdot r_u $$
-
予算b以内でz(π)を最大化する方策を見つけたい
-
uを根とする部分木については,以下で計算可
-
$$ z_u(\pi) = p_{u \mid \pi}\left( r_u + \sum_{v \in Ch(u)}z_v(\pi) \right) $$
-
live-edge による考え方
-
各頂点を割り当てられた確率で残す
-
sから到達可能な報酬を集めればその期待値がz
-
KKTの影響最大化に当てはめると辺の確率を上げる
提案手法
解析
-
(1-ε)近似でO(n^2/ε^2)時間
-
仮定: r_uの下界と上界を定数としている(・o・)
-
あんまり真面目に読んでないので謎
実験
-
計算時間
-
時間とパラメータの解析もしている
-
適切に設定すると超爆速だけど精度も90%以上とかになってる
-
計算時間がドカッと下がる
-
どうやら実データだとnに対して線形に近い挙動っぽい?
-
実際のネットワークで実験して図を示しているのが面白い
まとめ
-
こういう問題見つけてくるのすごいな
-
問題見つけてくれば後はどうにかなりそう
AAAI ネットワーク設計
2014-09-24 00:32:53 (Wed)
最終更新:2014年09月24日 00:32