パーフェクトサンプリングを用いたマルコフ連鎖モンテカルロ法の構築
【研究分野】社会システム工学・安全システム
【研究キーワード】
OR / 最適化 / マルコフ連鎖 / MCMC 法 / MCMC / サンプリング / パーフェクトサンプリング / CFTP / PERT / クリティカルパス / マルコフ連鎖モンテカルロ法 / パーフェクトサンプリング法
【研究成果の概要】
パーフェクトサンプリングを用いたマルコフ連鎖モンテカルロ法の構築
確率的 PERT ネットワークに対し,クリティカルパスの平均長を計算する,FPRAS の構築に成功した。この解法では,新たに開発した,CFTP 法に基くパーフェクトサンプリング法を用いている.開発したサンプリング法はサンプルを得るまでの推移回数が多項式時間であることが保障されている。これを実装して計算実験を行ったところ,推移回数は経験的には2～3回程度しか必要としない非常に高速な解法であることが分かった.
【研究代表者】
【研究種目】挑戦的萌芽研究
【研究期間】2011 - 2012
【配分額】3,510千円 (直接経費: 2,700千円、間接経費: 810千円)