WEKO3
アイテム
Hexomino解総数推定の解析と改善の提案
https://ipsj.ixsq.nii.ac.jp/records/144117
https://ipsj.ixsq.nii.ac.jp/records/14411768475fd3-71d4-44e6-90d8-429f3d7753e4
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
IPSJ-JNL5607003.pdf (1.2 MB)
|
Copyright (c) 2015 by the Information Processing Society of Japan
|
|
| オープンアクセス | ||
| Item type | Journal(1) | |||||||
|---|---|---|---|---|---|---|---|---|
| 公開日 | 2015-07-15 | |||||||
| タイトル | ||||||||
| タイトル | Hexomino解総数推定の解析と改善の提案 | |||||||
| タイトル | ||||||||
| 言語 | en | |||||||
| タイトル | Estimation of the Number of Solutions of the Hexomino Puzzle and Its Improvement | |||||||
| 言語 | ||||||||
| 言語 | jpn | |||||||
| キーワード | ||||||||
| 主題Scheme | Other | |||||||
| 主題 | [一般論文] 箱詰パズル，計数問題，乱択アルゴリズム | |||||||
| 資源タイプ | ||||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||||
| 資源タイプ | journal article | |||||||
| 著者所属 | ||||||||
| 電気通信大学 | ||||||||
| 著者所属(英) | ||||||||
| en | ||||||||
| University of Electro-Communications | ||||||||
| 著者名 |
寺田, 実
× 寺田, 実
|
|||||||
| 著者名(英) |
Minoru, Terada
× Minoru, Terada
|
|||||||
| 論文抄録 | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | 筆者は過去に大きな探索木に対する計数問題を推定するため，乱数による選択と深さ優先探索を組み合わせた手法「複合モンテカルロ法」を考案し，箱詰パズルhexominoの解総数を推定した．今回，その手法に基づき長時間の計算を行った結果，推定値の収束が安定しないという問題点が明らかになった．分析の結果，その原因は推定に用いる分岐数の積のばらつきにあることが分かった．それを軽減するために，分岐数の積に閾値を設けて全探索に入るという手法を新たに考案して計算を行ったところ，従来よりも安定した推定を行うことが可能になった．またこの手法をN-Queens問題についても適用したところ，一定の成果が得られた． | |||||||
| 論文抄録(英) | ||||||||
| 内容記述タイプ | Other | |||||||
| 内容記述 | We have proposed a randomized algorithm which estimates the number of certain nodes in large trees by combining conventional Monte Carlo method and depth-first search of subtrees. However the application of the algorithm to the hexomino puzzle shows an unstable behavior. We examined the result and devised a modification to the algorithm in which the product of branch factors along the path controls the start point of the depth-first search. We evaluated the revised algorithm in the hexomino and the N-Queen problem. | |||||||
| 書誌レコードID | ||||||||
| 収録物識別子タイプ | NCID | |||||||
| 収録物識別子 | AN00116647 | |||||||
| 書誌情報 |
情報処理学会論文誌 巻 56, 号 7, p. 1541-1548, 発行日 2015-07-15 |
|||||||
| ISSN | ||||||||
| 収録物識別子タイプ | ISSN | |||||||
| 収録物識別子 | 1882-7764 | |||||||
