題名 | UCTにおけるプレイアウトの効率化について |
著者 | *内田 大貴 (島根大学総合理工学研究科), 小林 康幸, 會澤 邦夫 (島根大学総合理工学部) |
ページ | p. 216 |
キーワード | UCT, Zebla, プレイアウト |
アブストラクト | チェス、オセロ、囲碁のようなゲームにおいてUCTという探索手法がある。UCTはUCB値が高いノードに探索を集中させる、モンテカルロ木探索の1つである。そして、モンテカルロ法では探索開始局面から終局までランダムにプレイする探索法を取り、これをプレイアウトと呼ぶ。 本研究では、UCT探索におけるプレイアウトの割合を局面評価関数を用いることによって変更し効率よく探索できるかを他の手法と比較することで検証する。 |
題名 | DNA計算における冗長2進数表現を用いた素因数分解アルゴリズムの提案 |
著者 | *寺西 敬祐 (島根大学総合理工学部研究科), 藤原 和也 (島根大学総合理工学部), 上野 泰寛 (島根大学総合理工学部研究科), 會澤 邦夫 (島根大学) |
ページ | p. 217 |
キーワード | DNA計算, 冗長2進数表現, 素因数分解問題 |
アブストラクト | DNA計算とは,DNA分子の構造と分子生物学的な操作を活用して計算を行うものである。現在の汎用計算機では計算量的に解を求めることが困難な問題をDNA計算により解く方法が研究されている。そのなかで,DNA 計算を用いた素因数分解アルゴリズムが提案されている。これらの手法は多項式時間で計算できるが、除数の桁数ごとに逐次除算を行うため,分子演算の回数が多くなってしまう。そこで本研究では、冗長2進数表現を導入しさらに分子演算の回数を抑えた素因数分解アルゴリズムを提案する。 |
題名 | 離散時間2値ニューラルネットワークの収束条件に関連するある判定問題のNP完全性 |
著者 | *平田 大貴, 高橋 規一 (岡山大学) |
ページ | pp. 218 - 219 |
キーワード | ニューラルネットワーク, 収束条件, NP完全, ハミルトン路問題 |
アブストラクト | 本研究の目的は,離散時間2値ニューラルネットワークが平衡状態に収束するための十分条件を判定する問題の時間計算量を明らかにすることである.そのための第一段階として,本発表では,この条件を緩和した条件を判定する問題について考察し,この緩和判定問題がNP完全であることを示す. |
題名 | 2次元議席配分実現可能性判定問題の双対化 |
著者 | *三村 祐史, 伊藤 暁 (山口大学) |
ページ | pp. 220 - 221 |
キーワード | 議席配分問題, 線形計画法 |
アブストラクト | 総議席数と等しくかつ,できるだけ理想配分に近いような各議席配分を決定せよ, という問題である. 2次元議席配分問題とは,通常の比例配分問題に各地域の要素を加えて,行と列を用いて表す問題である. この場合,小計配分を1次元の配分問題とみなしてその部分から先に配分し,次にその小計部分の配分に基づいて2次元成分毎の配分を決定する手法が提案されている. この2次元議席配分問題に対する解法としてはシラミつぶしに解候補を列挙し,線形計画法によってそれらが真の解であるかどうかを確認する方法しか知られていない. 本研究では,この解候補を確認する後半の作業の効率化について検討し,この部分問題を双対問題化することにより,線形計画法への入力サイズとなる条件式の個数を従来のO(MN)個からO(M+N)個に削減できることを示す. |