著者

寺田 実

雑誌

情報処理学会論文誌 (ISSN:18827764)

巻号頁・発行日

vol.56, no.7, pp.1541-1548, 2015-07-15

---

筆者は過去に大きな探索木に対する計数問題を推定するため,乱数による選択と深さ優先探索を組み合わせた手法「複合モンテカルロ法」を考案し,箱詰パズルhexominoの解総数を推定した.今回,その手法に基づき長時間の計算を行った結果,推定値の収束が安定しないという問題点が明らかになった.分析の結果,その原因は推定に用いる分岐数の積のばらつきにあることが分かった.それを軽減するために,分岐数の積に閾値を設けて全探索に入るという手法を新たに考案して計算を行ったところ,従来よりも安定した推定を行うことが可能になった.またこの手法をN-Queens問題についても適用したところ,一定の成果が得られた.