学生の研究 (2022年度版) の履歴の現在との差分(No.9)

• 履歴一覧
• 差分 を表示
• ソース を表示
• 履歴 を表示
• 学生の研究 (2022年度版) へ行く。
  • 1 (2016-02-22 (月) 15:00:00)
  • 2 (2017-02-16 (木) 16:54:20)
  • 3 (2017-03-21 (火) 15:11:35)
  • 4 (2018-04-02 (月) 15:14:42)
  • 5 (2019-03-29 (金) 14:27:00)
  • 6 (2020-03-04 (水) 16:34:38)
  • 7 (2020-07-02 (木) 01:52:28)
  • 8 (2020-07-03 (金) 18:16:37)
  • 9 (2021-04-02 (金) 11:45:33)
  • 10 (2021-05-14 (金) 15:47:59)
  • 11 (2021-05-14 (金) 21:13:50)
  • 12 (2021-05-21 (金) 21:16:34)
  • 13 (2022-04-03 (日) 17:55:00)
  • 14 (2022-10-21 (金) 13:25:17)

• 追加された行はこの色です。
• 削除された行はこの色です。

#author("2021-04-02T11:45:33+09:00","","")
* 学生の研究 [#effd7e94]
#freeze
#author("2022-10-21T13:40:42+09:00","","")
* 学生の研究 (2022年度版) [#effd7e94]

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

**現在の学生の研究 [#f4aadfdd]
**現在のメンバーの研究 [#f4aadfdd]

***特殊なグラフにおけるハミルトン閉路の一意性 [#h4e947ef]
*** 辺追加による影響最大化 [#v673b626]

#ref(sakam_fig.png,nolink,around,left,50%,);
点とそれらを線で結んだものをグラフといい，線をたどってすべての"点"を一度ずつ通ってループを作ることができるかどうかを考えます．このループを我々は「ハミルトン閉路」と呼びます．ハミルトン閉路を含むグラフで，すべての点から出る線の数（次数）が
３であるときには，異なるハミルトン閉路が３つ以上存在するということは1946年に証明
されています(W. T. Tutte)．しかし，図のようにすべての点の次数が４であるときにも
同じようなことがいえるかどうかは，45年の間，未解決問題となっています(J. Sheehan, 1975)．あらゆる側面から，この問題を証明，あるいは反証することが本研究の目的です．
#clear
#ref(hentsuika.png,nolink,left,50%,);
バイラルマーケティングとは，SNSや口コミを利用して不特定多数の人に情報を拡散する手法です．これを効率的に行うために，SNSをグラフでモデル化し，より多くの人に情報を届ける手法の研究が盛んに行われています．グラフの頂点にあたる"情報の発信源"に着目した研究が既に多く存在しますが，私の研究ではグラフの辺にあたる，ユーザー同士のフォローといった"関係性"に着目し，情報拡散を促すアルゴリズムの開発を目指します．

***グラフの木分解 [#ibe4c424]
*** ボロノイ図とディグフォーメーション [#t24e4c55]

#ref(452px-Tree_decomposition.svg.png,nolink,around,left,50%,);
グラフには木分解と呼ばれる概念があります．これはグラフを木の形状（閉路を持たないグラフのこと）になるように，グラフの頂点をある程度まとめて一つの頂点にして，辺を
付け加えることを指します．グラフをうまく木分解するとグラフに関する難しいアルゴリズム（NP完全問題）が簡単に解けることがあり，グラフがうまく木分解で来ているかどうか調べる指標の一つに幅という概念があります．幅はグラフの頂点を一つの頂点にまとめた時の頂点に入っている頂点数から1を引いたものです．（左の下側の図の場合幅は2）幅
はなるべく小さい方が良く，小さい幅をもつ木分解を見つけるアルゴリズムで用いられるPMC（potential maximal clique）と呼ばれる概念について研究しています．
(図の出典は [[https://ja.wikipedia.org/wiki/木分解]] です． )
#ref(vbv.png,nolink,left,50%,);
ボロノイ図とは，与えられたいくつかの点に対し，どの点に一番近いかによって領域を分けた図です．一方，バレーボールにおいて，スパイクをレシーブすることをディグと呼び，その際のフォーメーションをどのように設定するかは重要な戦略の一つとなっています．ディグフォーメーションをボロノイ図で表現することで，フォーメーションの数学的な分析を行うことを目指します．

#clear
*** マッチングKneserグラフのハミルトン閉路 [#q9c91409]

***離散アルゴリズムを用いた施設警備ゲーム [#iec248b8]
#ref(mkg.png,nolink,left,50%,);
グラフ理論において，ある頂点から，すべての頂点を一度だけ通って元の頂点に戻ってくる道のことをハミルトン閉路といいます．与えられたグラフがハミルトン閉路をもつかどうかを判定することは難しい問題として知られています．私の研究では，入力としてグラフと自然数が1つずつ必要なマッチングKneserグラフというグラフについて，どのような入力であればマッチングKneserグラフはハミルトン閉路をもつのかを調べています．

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

#clear
#ref(sgm.png,nolink,left,50%,);
「元のグラフ」から，頂点や辺を削除したり，いくつかの隣り合った頂点を一つの頂点とみなしたりして，「別のグラフ」を得ることを考えます．このとき，「別のグラフ」は「元のグラフ」の「マイナー」であると言います．研究では，「元のグラフ」と「マイナー」が与えられたとき，「マイナー」を得るために必要な「元のグラフ」の最小の部分はどこか，与えられたグラフの性質からその部分が最小であることが示せるのか，といったことを明らかにすることを目標にしています．

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

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

#clear
#ref(vrp.png,nolink,left,50%,);
配送中であるにも関わらず次々に配送先が増えていくとき，最適な配送経路を探索することを目指します．既存の研究では車両が配送先を訪問すればよいとされていたところを，この研究では各荷物が確かに配送先に届けられることまで想定します．
この問題を配送計画問題という配送に関する最適化問題をもちいてモデル化し，それを解くための効率的なアルゴリズムを研究しています．

***ある長さの経路が必ず出来る頂点数を求める [#o06469d1]
*** 仲裁コアの非空性 [#m3879399]

#ref(twoColorsDivision.png,nolink,around,left,50%,);
n個の点が存在し，そのどの2点も線で結ばれているようなものを考えます．図は，nが5の場合です．ここで，線を適当に赤と青で塗り分けることを考えます．このとき，同じ色だけを使い，同じ線を二度以上使わないような経路（小道といいます）を考えてみましょう．図の場合では，赤い線を4本使った経路と，青い線を4本使った経路があります．研究では，線をどのように赤と青で塗り分けたとしても，どちらかの色だけを用いて長さがkの小道が出来てしまうようなnの範囲について考察しています．
#ref(ocfg.png,nolink,left,50%,);
Overlapping Coalition Formation ゲーム(OCFゲーム)は、協力ゲームの拡張であり、複数の主体がリソースを分割して協力できる場合をモデル化しています．協力関係による利益は参加者で分配され、誰からも不満が出ないような協力関係と分配の仕方のペアの集合を仲裁コアといいます．この仲裁コアが空集合ではなくなるのはどんなときかについて研究しています．

#clear
*** マインスイーパーの難易度 [#rfe32642]

***グラフの複雑さを表すパラメーターの設定の検討 [#l32a67dd]
#ref(minesweeper.png,nolink,left,50%,);
マインスイーパーは,数百個のマス目からなる地雷原から地雷のあるマスを特定し，地雷が埋まっていないマスを全て開けるゲームです．地雷の埋まっていないマスを開けると，その周囲の8マスにある地雷の数を示す数字が表れます．この情報を用いて，どのマスに地雷が埋まっているかを推測します．私の研究では,マインスイーパーの難易度に関する新しい指標を考案することを目標とします．

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

#clear
***花札のこいこいにおける必勝性と計算複雑性 [#s669dc04]
#ref(violin.png,nolink,left,50%,);
4弦からなる弦楽器の一種であるヴァイオリンには1つの音高に対して複数の押弦パターンが存在します．また楽譜に指示がないとき，奏者は押弦パターンを自ら選択する必要があります．
私の研究では押弦に用いる4本の指の運動量に着目し，楽譜の情報から奏者にとって負担の少ない運指を導出することを目標としています．

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

#clear
***提携に重複のある協力ゲームの研究 [#jb03125d]
*** 無三角グラフの頂点樹化彩色 [#i15a4a3f]

#ref(kennkyuusyoukai.png,nolink,around,left,30%,);
ゲーム理論とは、人間、会社、コンピュータなどの複数の主体がそれぞれ意思決定をして、自身の利益を大きくしようとする様子を取り扱う分野です。特に、プレイヤ同士が合意のもとで協力関係を結べる状況を協力ゲームといいます。この協力関係を提携と呼び、協力ゲームでは提携ごとに得られる利益が与えられます。
#ref(arbcol.png,nolink,left,50%,);
グラフの頂点に色を塗ることを考えます．ただし，単色閉路があってはいけません．このような塗り方に必要な最小の色数を求める問題を頂点樹化彩色問題といいます．一般のグラフに対して頂点樹化彩色問題は難しいことが知られています．本研究では，無三角グラフというグラフに対して頂点樹化彩色問題を解くことを目指します．

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

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

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




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

***令和2年度 [#vc6bcc63]
***令和3年度 [#ub72a703]
-対数空間による非切断辺数の推定と木判定 (修士論文)
-道分解における潜在極大クリークの研究 (修士論文)
-クリーク幅の構成表現に対するグラフ分解手法の適用の検討  (修士論文)
-部分当日配送計画問題の提案とLin-Kernighan-Helsgaun法を用いたアルゴリズムの実装 (卒業論文)
-頂点数9の完全グラフの非反復辺染色数の特定 (卒業論文)
-グラフ上のSolitaire Clobber Gameとcorreducibilityに対する連結度からの考察 (卒業論文)

***令和2年度 [#vc6bcc63]
-カバー関数を用いた施設警備ゲームのモデル化 (修士論文)
-4正則一意的ハミルトニアングラフの存在性 (修士論文)
-フレキシブルジョブショップスケジューリング問題に対する離散ホタルアルゴリズム (修士論文)
-花札のこいこいにおける必勝戦略計算可能性 (卒業論文)
-頂点数12以下の無三角グラフの頂点樹化数 (卒業論文)
-提携に重複を許したロバストな提携構造形成問題の研究 (卒業論文)

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

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

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

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

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

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

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

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


RIGHT:(文責：岡本吉央)