文献

J-GLOBAL ID：201502202426677336   整理番号：15A0865442

Hexomino解総数推定の解析と改善の提案

Estimation of the Number of Solutions of the Hexomino Puzzle and Its Improvement

著者 (1件)： 寺田実 (電通大)
資料名： 情報処理学会論文誌ジャーナル(Web)
巻： 56  号： 7  ページ： 1541-1548 (WEB ONLY)  発行年： 2015年07月15日 
JST資料番号： U0452A  ISSN： 1882-7764  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 日本語 (JA)

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

シソーラス用語： *探索理論 ,  探索問題 ,  計数法 ,  *モンテカルロ法 ,  収束 ,  閾値 ,  アルゴリズム ,  *擬似乱数 ,  *探索木 ,  *理論
準シソーラス用語： *乱択アルゴリズム

分類 (1件)： 人工知能  (JE08000Z)

引用文献 (7件)：

• 寺田実:複合モンテカルロ法による探索木の解総数の見積り,情報処理学会論文誌,Vol.38,No.8,pp.1492-1497(1997).
• 中村将人,小川重義:計数問題における複合モンテカルロ法について,数理解析研究所講究録,Vol.1351,pp.134-142(2004).
• 玉木久夫:乱択アルゴリズム,アルゴリズム・サイエンスシリーズ,共立出版(2008).
• 津田孝夫:モンテカルロ法とシミュレーション(三訂版),培風館(1995).
• Motwani, R. and Raghavan, P.: Randomized Algorithms, Cambridge University Press (1995).

タイトルに関連する用語 (4件)： 解 ,  推定 ,  解析 ,  提案