平成24（2012）年度　共同利用登録実施報告書

課題番号	24−共研−8	分野分類		統計数理研究所内分野分類		f
				主要研究分野分類		1
研究課題名	モンテカルロ法を用いた数独解盤面の近似数え上げ
フリガナ 代表者氏名	サダヒロ タイゾウ 貞廣 泰造		ローマ字		Sadahiro Taizo
所属機関	津田塾大学
所属部局	学芸学部
職　　名	准教授

研究目的と成果の概要

数独解盤面等の複雑な組合せ制約を満たす集合の近似数え上げの研究を統計数理研究所の高性能計算機を用いて行うことを目的としました。
当初は高性能計算機の使用が必要だと考え申請したのですが、インポータンスサンプリングのアルゴリズムを変更することにより、PCでも大幅な精度向上が出来ることが分かり、アルゴリズムの改善に研究の中心が移りました。結局、研究所の高性能計算機を使う時間をとることが出来ませんでした。数独だけでなく、次数列を指定された多重グラフや、完全マッチングなど様々な対象についてインポータンスサンプリングによる近似数え上げアルゴリズムを開発し、実験を行いました。成果は数学セミナー、計算機統計学会シンポジウムなどで報告しました。また副次的な結果ですが、完全マッチングに関する論文(DOI10.1007/s10955-013-0744-6)が学術誌に掲載されることが決まりました。