#author("2020-03-04T16:34:38+09:00","","")
* 過去の卒業論文，修士論文 [#effd7e94]
#author("2020-07-02T01:52:13+09:00","","")
* 学生の研究 [#effd7e94]

注意：これらは学生の研究成果であり，教員 (岡本) が各個別テーマに対して専門性を持っているものではありません．
注意：これらは学生の研究内容・研究成果であり，教員 (岡本) が各個別テーマに対して専門性を持っているものではありません．

**令和元年度 [#a8a3fb73]
**現在の学生の研究 [#f4aadfdd]

***特殊なグラフにおけるハミルトン閉路の一意性 [#h4e947ef]

#ref(sakam_fig.png,nolink,around,left,50%,);
点とそれらを線で結んだものをグラフといい，線をたどってすべての"点"を一度ずつ通ってループを作ることができるかどうかを考えます．このループを我々は「ハミルトン閉路」と呼びます．ハミルトン閉路を含むグラフで，すべての点から出る線の数（次数）が
３であるときには，異なるハミルトン閉路が３つ以上存在するということは1946年に証明
されています(W. T. Tutte)．しかし，図のようにすべての点の次数が４であるときにも
同じようなことがいえるどうかは，45年の間，未解決問題となっています(J. Sheehan, 1975)．あらゆる側面から，この問題を証明，あるいは反証することが本研究の目的です．
#clear

***グラフの木分解 [#ibe4c424]

#ref(452px-Tree_decomposition.svg.png,nolink,around,left,50%,);
グラフには木分解と呼ばれる概念があります．これはグラフを木の形状（閉路を持たないグラフのこと）になるように，グラフの頂点をある程度まとめて一つの頂点にして，辺を
付け加えることを指します．グラフをうまく木分解するとグラフに関する難しいアルゴリズム（NP完全問題）が簡単に解けることがあり，グラフがうまく木分解で来ているかどうか調べる指標の一つに幅という概念があります．幅はグラフの頂点を一つの頂点にまとめた時の頂点に入っている頂点数から1を引いたものです．（左の下側の図の場合幅は2）幅
はなるべく小さい方が良く，小さい幅をもつ木分解を見つけるアルゴリズムで用いられるPMC（potential maximal clique）と呼ばれる概念について研究しています．
(図の出典は [[https://ja.wikipedia.org/wiki/木分解]] です． )

#clear

***離散アルゴリズムを用いた施設警備ゲーム [#iec248b8]

#ref(keibi.png,nolink,around,left,20%,);
近年, 人件費の増大やセンサー技術の進歩により, 効率の良い警備人員や監視カメラ等の配置を行うアルゴリズムが注目されている. ある対象への効率的な警備資源の分配を考える問題を「警備理論」と言い, ある施設への効率的な警備配置を考える問題を「施設警備ゲーム」と言う. 私の行っている研究では, 二次元平面上に設定した施設への効率的な
警備員や警備機械の配置を考える問題のモデル化と, その問題を効率的に解く離散アルゴリズムの考案および実験です. 可能なすべての警備員, 機械の配置を考えると膨大な計算時間がかかってしまう問題でも, 数理計画法と呼ばれる最適化アルゴリズムを用いる事で
効率良く最適解を求めることが出来ます. 図に示した「侵入経路決定問題」では, 二次元平面上での侵入者の侵入方法を考える事で, 警備員の警備配置を評価する問題です.

#clear

***離散ホタルアルゴリズムの改良 [#o1053fa8]

#ref(DFA_fig.png,nolink,around,left,20%,);
離散ホタルアルゴリズムは，オスのホタルが強い光を放っているメスへ飛んでいく求愛行動をモデル化したアルゴリズムです．問題の最適解を計算で求めるのが難しい問題に対して有効で，例を挙げると効率的な生産スケジュールや配送ルートを求める際に用いられます．各ホタルが問題に対する解を持っているとし，評価の高い解を持っているホタルへ解を少しずつ近づけることで最良解を発見します．同種のアルゴリズムと比較すると，解を発見するまでの過程が簡単であることや本実験を行うまでの準備が短いことが特徴です．研究の目的は離散ホタルアルゴリズムの改良を行い，以前のアルゴリズムや同種のアルゴリズムと比較します． 

#clear

***ある長さの経路が必ず出来る頂点数を求める [#o06469d1]

#ref(twoColorsDivision.png,nolink,around,left,50%,);
n個の点が存在し，そのどの2点も線で結ばれているようなものを考えます．図は，nが5の場合です．ここで，線を適当に赤と青で塗り分けることを考えます．このとき，同じ色だけを使い，同じ線を二度以上使わないような経路（小道といいます）を考えてみましょう．図の場合では，赤い線を4本使った経路と，青い線を4本使った経路があります．研究では，線をどのように赤と青で塗り分けたとしても，どちらかの色だけを用いて長さがkの小道が出来てしまうようなnの範囲について考察しています．

#clear

***グラフの複雑さを表すパラメーターの設定の検討 [#l32a67dd]

#ref(param.png,nolink,around,left,30%,);
最短経路を求める問題や、地図の色を塗り分けるのに必要な色の数を求める問題、といったいくつかの問題はグラフを用いて問題を定式化できます。このような問題にはしかし、効率的に解を求めることができる解きやすい問題が存在する一方で、実際に解くには計算時間がかかる難しい問題が多く存在します。そのような難しい問題を効率的に解くための方法の一つとして、解きやすい問題の構造に似ている度合いを表す指標(パラメーター)を用いて、似ている構造をもつ場合には速く解けるような方法があります。そのような問題の構造を表す指標は、これまでにいくつか提示されていますが、より複雑なグラフを表すことができるような指標の表現方法に興味を持っています。

#clear
***花札のこいこいにおける必勝性と計算複雑性 [#s669dc04]

#ref(hanafuda.jpg,nolink,around,left,50%,);
こいこいは、安土・桃山時代の天正かるたに由来すると言われるカード「花札」を使ったゲームです。二人のプレイヤーが順番にカードを取っていき、特定の組が完成した時点で得点を得ることができます。また麻雀のように上がれる状況でも、あがらない「こいこい」を選択できるのが特徴です。私はある時点においてどちらかのプレイヤーが必勝であるか、またはその計算が複雑であるかについて証明しようと考えています。必勝であるとは、相手がどのような行動をとったとしても勝つことができる行動が存在することを言います。

#clear
***提携に重複のある協力ゲームの研究 [#jb03125d]

#ref(kennkyuusyoukai.png,nolink,around,left,30%,);
ゲーム理論とは、人間、会社、コンピュータなどの複数の主体がそれぞれ意思決定をして、自身の利益を大きくしようとする様子を取り扱う分野です。特に、プレイヤ同士が合意のもとで協力関係を結べる状況を協力ゲームといいます。この協力関係を提携と呼び、協力ゲームでは提携ごとに得られる利益が与えられます。

昔から研究されているような協力ゲームでは、1人のプレイヤは2つ以上の提携に参加出来ないものとしています。しかし現実には、1人の人間が2つ以上のチームに参加して仕事をするような場合など、プレイヤが複数の提携に参加するような場合も存在します。提携を構成するプレイヤに重複があるような協力ゲームにおいて、どのように提携を組むと利益が大きくなるのか、得られた利益はどのように分配するのが良いのかという問題の研究をしています。

#clear
***無向グラフの頂点樹化彩色問題 [#c9315a75]

#ref(graph.png,nolink,around,left,30%,);
無向グラフは，いくつかの頂点と，いくつかの辺からなります．1つの辺は異なる2つの頂点を結び，辺の向きはありません．この研究では，「ある1つの色で塗られた頂点からなる閉路が存在しない」という制限を課して各頂点に色を塗ることを考えます．ここで閉路とは，ある頂点から辺でつながれている頂点を1個以上経由して元の頂点に戻ってくるような経路のことです．このような塗り方を頂点樹化彩色といい，その色の数の最小値，もしくは色の数が最小となるような塗り方を求める問題を頂点樹化彩色問題といいます．例えば，図の塗り方は頂点樹化彩色になっています．このグラフには閉路が複数含まれていますが，同一の色のみで塗られた閉路は1つも存在しません．頂点樹化彩色問題はNP困難（つまり，難しい）ということが知られています．この研究では，特別な頂点樹化彩色問題に関して成り立つ定理などを発見しようとしています．




#clear
**過去の卒業論文，修士論文 [#ka1716b1]

***令和元年度 [#a8a3fb73]
-Rook-Fáry Drawingの存在性 (修士論文)
-小道に関するラムゼー数 (卒業論文)
-ペンシルパズル「ぬりみさき」の物理的ゼロ知識証明 (卒業論文)

**平成30年度 [#dfd8c014]
***平成30年度 [#dfd8c014]
-Cops and Robbers gameの研究 (修士論文)
-時間枠付き輸送経路問題に対するハイブリッドアントコロニー最適化法の提案 (修士論文)
-位置情報ゲームIngressにおける制限時間内で得られる経験値の最大化近似アルゴリズム (修士論文)
-多重リスト彩色に対する保証付きアルゴリズム (修士論文)
-排他制約付き厳密被覆問題に対するZDDを用いた解列挙手法 (修士論文)
-数理計画法を用いた施設警備ゲームに関する研究 (卒業論文)
-始点固定ハミルトンパスの唯一存在性に関する研究 (卒業論文)
-変形可能な物体の2次元パッキング問題 (卒業論文)

**平成29年度 [#ma0cf628]
***平成29年度 [#ma0cf628]

-限定記憶を持つプレイヤーのための戦略設計 (修士論文)
-グラフのフィードバック頂点集合問題に対する局所探索法 (修士論文)
-疎性をもつ半正定値計画問題の変換手法における弦拡張に関する研究 (卒業論文)
-rook-straight line drawing が存在するグラフクラスに関する研究 (卒業論文)
-Pyramidの計算複雑性 (卒業論文)

**平成28年度 [#mac4328a]
***平成28年度 [#mac4328a]
- ランダムグラフ上の最長路問題に対する発見的アルゴリズム (修士論文)
- 快適さを最大化する公園の散歩経路設計 (卒業論文)
- 位置情報ゲームIngressにおける制限時間内で得られる経験値の最大化 (卒業論文)
- 弱双対が線型森である外平面的グラフのゲーム染色数 (卒業論文)
- 橋をかけろの解答・問題生成アルゴリズム (卒業論文)

**平成27年度 [#we2ecdda]
***平成27年度 [#we2ecdda]
- 一次元版クロバーの解析 (修士論文)
- 単位円グラフのセパレータ構成問題に対するアルゴリズム的研究 (修士論文)
- A Comparison with an Approximation Algorithm for the Geometric Firefighter Problem (卒業論文)
- '''N'''面サイコロを用いたLiar's DiceおよびBluffにおける最適戦略の導出アルゴリズム (卒業論文)
- 位相幾何学的データ解析を用いたPOSデータの分類 (卒業論文)
- 重み付き木における探索戦略決定問題の研究 (卒業論文)
- 逆算法によるラッシュアワーの盤面の列挙 (卒業論文)

**平成26年度 [#pe7f1bbc]
***平成26年度 [#pe7f1bbc]
- 音楽シミュレーションゲーム「jubeat」に対する運指最適化 (卒業論文)
- 確率的に構成したグラフにおける最長路問題の性質 (卒業論文)
- カードゲーム「チェント」における戦略の解析 (卒業論文)

**平成25年度 [#i931d6e7]
***平成25年度 [#i931d6e7]
- 逐次添加サンプリング方式によるパラメータ自動チューニングに関する研究 (修士論文)
- マルチGPU環境におけるCRS形式疎行列・ベクトル積の入力行列の最適化による高速化 (修士論文)
- 村田法のスレッド並列化によるマルチコアCPU上での実対称帯行列帯幅縮小操作の高速化 (修士論文)
- 自転車詰込み問題 (卒業論文)
- 視聴率とTwitter検索のヒット数に関するデータ分析 (卒業論文)
- スコットランドヤードに対する思考ルーチンの作成 (卒業論文)
- セル・オートマトンモデルによるエスカレータ通行のモデル化 (卒業論文)
- トレーディングカードゲームにおける初手確保基準のモデル (卒業論文)
- Magnus-Derek gameにおける最小の手数 (卒業論文)


RIGHT:(文責：岡本吉央)
トップ   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS