3 0 0 0 コンピュータ大貧民におけるローカルルールの効果に関する研究
- 著者
- 門 裕太 大久保 誠也 若月 光夫 西野 哲朗
- 雑誌
- 研究報告ゲーム情報学(GI) (ISSN:21888736)
- 巻号頁・発行日
- vol.2019-GI-41, no.12, pp.1-6, 2019-03-01
コンピュータ大貧民の研究がUEC標準ルールに基づいて行われている.しかし,ローカルルールの効果に関する研究は,ほとんど行われていない.本研究では,ローカルルールが各種指標にどのような影響を与えるかについて検討を行った.特に,平均終了手数や平均合法手数といった指標について検討した.また,UEC標準ルールに基づいた大貧民は,戦略的複雑さが,他の現代のゲームと比べて非常に単純であることが示されている.そこで,ローカルルールによって複雑にすることができるかについて検討した.さらに,大貧民は,交換ルールによる順位の格差が大きいことや,席順によって得点に差があることも知られている.そこで,各種ローカルルールが席順と得点に与える影響について調査した.具体的には,代表的な大貧民プログラムを11バックや5飛び,6リバースに対応させ,それらを用いた計算機実験によりデータを収集し,その分析を行った.その結果,11バックは,階級の格差を改善するが,平均合法手数や戦略的複雑さは変化させないこと.また,5飛びや6リバースは,席順に応じた得点の差に影響を与えることがわかった.
- 著者
- 富田 悦次 今松 憲一 木幡 康弘 若月 光夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)
- 巻号頁・発行日
- vol.79, no.1, pp.1-8, 1996-01-25
- 被引用文献数
- 13
本論文では, 無向グラフ中の最大クリークを抽出するための単純で効率の良い分枝限定アルゴリズムを提唱する. ここで, いかにして分枝の制限を強力に働かせて解の探索領域を小さくするかが, アルゴリズムの効率化の重要な指標となる. しかし, その分校制限実現のために要する処理時間をできるだけ小さく抑える必要がある. そこで本論文では, その両者の兼合いを適切に達成した, 非常に単純で巧妙な逐次近似彩色-整列法を考案し, それにより探索の各段階において見出し得る最大クリークの上界を得て分技制限を効果的に実現し, 総実行時間も小さく抑えることに成功した. 本アルゴリズムは, 他のいくつかの代表的アルゴリズムと直接実験的比較, あるいは論文上の数値比較により, それらに対して600節点以内の広い範囲の多くのランダムグラフおよび1000節点のいくつかのランダムグラフについて, より高速であることを確認した.
1 0 0 0 最大クリーク問題の多項式時間的可解性の拡張の更なる改良
- 著者
- 中西 裕陽 富田 悦次 若月 光夫 西野 哲朗
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 研究報告アルゴリズム(AL) (ISSN:09135685)
- 巻号頁・発行日
- vol.2014, no.14, pp.1-8, 2014-06-06
NP 完全である最大クリーク問題に対し,"節点数 n≧1 のグラフにおいて,グラフ中の任意の隣接 2 節点 vi,vj∈V, (vi,vj)∈E が min{deg(vi), deg(vj)}≦3.486d lg n (d ≧0: 定数) を満たすならば,最大クリーク問題は O(n2+max{d,1}) 時間で解決可能である." ことを示す.これは,先に発表した結果 (信学論 (D),vol.J97-D,no.6,June 2014) の定量的改良である.This paper presents a further improved extended result for polynomial-time solvability of the maximum clique problem, that is: for any adjacent pair of vertices p and q where the degree of p is less than or equal to that of q in a graph with n vertices, if the degree of p is less than or equal to 3.486d lg n (d≧0: a constant), then the maximum clique problem is solvable in the polynomial time of O(n2+max{d,1}). This result is obtained by more detailed analysis and the corresponding detailed algorithm.
1 0 0 0 学習ゲームを用いた発達障害児向け文字学習支援システム
- 著者
- 金山 貴泰 浅野 久美子 西野 哲朗 若月 光夫
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 研究報告数理モデル化と問題解決(MPS) (ISSN:09196072)
- 巻号頁・発行日
- vol.2013, no.8, pp.1-6, 2013-05-16
発達障害児教育においては,児童の学習に関する動機の喚起・維持が困難な場合が多い.この問題を解決するために,近年,発達障害児教育の現場において,ICT(情報通信技術)を用いた教育支援システムの活用が注目されている.本研究では,発達障害児の興味を引くように,学習ゲームの仕組みを取り入れた,文字学習支援システム『おとかな!』を開発した.その際,教員とのディスカッションを通して,本システムに難易度設定,問題設定,学習記録の自動化といった機能も組み込んだ.本システムの有効性を検証するために,開発したシステムを特別支援学校の授業で実際に使用した.その結果,本システムは,発達障害児の興味を引き出し,学習への集中時間を増加させる効果があることがわかった.さらに,ICT教材の機能を活用することで,教材の準備にかかる教員の負担を大幅に軽減できることもわかった.In this study, we developed a learning support system for children with physical or mental disabilities. In order to reduce the burden of supervisors in education of these children. Educating these children is a burden for teachers. Because these children difficult to maintain the motivation for learning Therefore we developed this system to apply learning game for pull these child's interest. Through discussions with teachers, I incorporated the function difficulty settings, question setting, and automatic recording. In order to verify the validity of this system, it experimented in the special support school. As a result, this system which pull these child's interest and concentration time was increased. Furthermore, it turned out that the burden placed on preparation of teaching materials is mitigable by employing the feature of ICT teaching materials efficiently.
1 0 0 0 OA 形式言語の効率的学習アルゴリズムの開発及びその応用システムの構築
決定性プッシュダウン変換器のスタック記号を1種類に限定した決定性限定1カウンタ変換器について,それが最終状態受理式の場合,より一般的なε-推移を持つ場合についてもその等価性判定及び包含性判定が多項式時間で行えることを明らかにした.また,実時間最終状態受理式決定性限定1カウンタ変換器に対して,所属性質問及び等価性質問を用いた多項式時間の学習アルゴリズムを開発した.更に,正則言語の部分クラスに対する正例からの極限同定を組み込んだジュウシマツの歌構造解析ツールEUREKAを利用することによって,コンピュータ上でトランプゲームの大貧民の対戦を行うプログラムの挙動の規則性が抽出可能なことを示した.
- 著者
- 但馬 康宏 富田 悦次 若月 光夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. COMP, コンピュテーション
- 巻号頁・発行日
- vol.97, no.356, pp.111-118, 1997-10-31
- 参考文献数
- 4
- 被引用文献数
- 1
単純決定性言語の多項式時間MAT学習に関する新たな結果を示す。一般に等価性質問は、仮説文法の入力に対して学習対象の言語との等価性を出力とし、さらに非等価の場合には、その根拠となる反例も出力となる。ここで、反例が正の反例の場合、さらに学習対象における導出構造を出力する質問を構造反例付き等価性質問と新たに定義する。このとき、任意の単純決定性言語は、単純決定性言語の族を用いて、所属性質問および構造反例付き等価性質問から多項式時間で厳密学習可能であることを示す。この学習アルゴリズムの基本的な考え方はAngluin (1987) によるアルゴリズムの拡張である。