![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#author("2022-03-08T00:51:45+09:00","","") [[学生の研究]] #author("2022-03-09T10:41:19+09:00","","") * 学生の研究 [#effd7e94] 注意：これらは学生の研究内容・研究成果であり，教員 (岡本) が各個別テーマに対して専門性を持っているものではありません． **現在のメンバーの研究 [#f4aadfdd] *** 指定する頂点同士を結ぶ道を見つけるには？ [#r63da248] #ref(mafigure.png,nolink,around,left,50%,); 頂点と頂点同士を辺で結んでできる構造をグラフといいます． 本研究では，いくつかの頂点の組が指定されて，その指定された頂点同士を結ぶ交わらない道が見つかるかという問題を考えています． 例えば，図にある2つのグラフで同色の頂点同士を結ぶ交わらない道が見つかるかを考えます．実は，左のグラフは見つけられますが，右のグラフには見つかりません． このように，同じグラフでも指定する頂点によっては道が見つかったり見つからなかったりします． 本研究では，どんな性質をグラフが満たしていれば，どのように頂点の組を指定しても互いに交わらない道が見つかるのかや， 指定する頂点の組を増やしたらどうなるのかといったことを研究しています． #clear *** 複数の文の圧縮についての研究 [#cf6fcec9] #ref(文からの単語グラフ生成のイメージ.png,nolink,around,left,40%,); ウィキペディアなどのウェブサイトでは、様々な問題に関する情報が提供されています。しかし、それらの文章は長く、情報は多すぎるので自動テキスト要約(ATS)できるアプリがあると便利です。この時、文法的に正しく、形の整った小さな文を生成するためにMSC を用いることがあります。Multi-Sentence Compression (MSC)とは密接に関連する複数の文から新たに文章を生成することです。これはATSよりも情報量の多い要約を生成することがあります。このときにできるだけ情報が落ちないようにすることとできるだけ短い文を生成することが重要です。主要な手法として次のようなものがあります。ラベル付きグラフを用いてK最短経路を生成します。そして、整数線形計画法を用いて生成された最短経路の集合から文を選択します。興味があるのはこの手法を分析してより優れた要約の手法を編み出すことについてです。 #clear *** グラフの特徴を表すような指標を求めるアルゴリズムの検討 [#v0f21ef9] #ref(研究紹介用の図_suzuki.png,nolink,around,left,70%,); 最短経路を求める問題や地図の色を塗り分けるのに必要な色の数を求める問題、といったいくつかの問題は、”グラフ”という頂点と辺からなる問題の表現方法を用いて問題を定式化できます。このような問題にはしかし、効率的に解を求めることができる解きやすい問題が存在する一方で、実際に解くには計算時間がかかる難しい問題が多く存在します。そのような難しい問題を効率的に解くための方法の一つとして、解きやすい問題の入力の構造に似ている度合いを表すようなグラフの指標を用いて、その指標の値が小さい場合には速く解けるような方法があります。しかし、あるグラフが与えられたときにそのグラフの指標の値を求めること自体に計算時間がかかってしまうという問題があります。そこで研究では、グラフの指標を早く計算する方法を考察しています。(図の出典： https://en.wikipedia.org/wiki/Clique-width ） #clear *** SNSにおける影響最大化問題 [#i1dae080] #ref(研究イラスト.jpg,nolink,around,left,30%,); 商品の宣伝や災害情報の周知など，情報の拡散は社会の重要な要素の一つとなっています．そこで，特に情報の収集及び発信が手軽なSNSをモデルにし，発信した情報をより多くのユーザーに届けるように促す手法について研究しています． 研究のテーマである影響最大化問題とは，グラフにおける最適化問題の一つであり，既に多くの研究があります．SNSのモデルにおける影響最大化問題とは，情報の発信源であるユーザーの数を入力として予め定め，その条件の下で最も多くのユーザーに情報を拡散することのできる発信源ユーザーの集合を出力する問題です．本研究では，このような情報源ユーザーの集合の選択以外の手法による影響最大化問題について，問題設定とそれを解くアルゴリズムの提案を目的としています． #clear *** 配送計画問題の研究 [#aba6b0d1] #ref(研究紹介_図_kominami.png,nolink,around,left,20%,); 数学においてグラフとは頂点と辺からなるものを指します。現実の事象をグラフとして単純化することで、様々な問題を解くことが可能です。配送計画問題は場所を頂点、道を辺としてグラフに落とし込むことで、最適な輸送経路を見つけることを目的とします。配送計画問題の内容は多岐に渡りますが、その一例として配達が挙げられます(図参照)。1つの頂点を物流センター、他の頂点を顧客とみなし、物流センターから各顧客(あるいはその逆)への配送を複数のトラックで行う時、各トラックの最適な経路を求めます。そのような経路を求めるアルゴリズムはどのようなものか、そのアルゴリズムはどれほど有用かを調べることが本研究の目的です。 #clear *** 大規模なグラフに対する指標の値の推定 [#aba6b0d1] #ref(shoukai.png,nolink,around,left,50%,); SNSや，Web，peer-to-peerなどのネットワークは，グラフとしてみることができ，それらのグラフの頂点数や辺の数は非常に大きくなります．仮に，頂点と辺の情報をすべて記録することが出来る場合，そのグラフに含まれる頂点数や辺数，ある頂点からある頂点までの最短経路など，多くの指標において正確な値を求めることが可能です．しかしながら，大規模なグラフにおいて，すべての頂点と辺の情報を記録しておくことはメモリの関係上非常に困難です．そこで，本研究では，グラフからランダムに一部の情報を手に入れ，その一部の情報を解析することで元のグラフの指標の値を推定する手法について研究しています． #clear *** 施設レイアウト問題の研究 [#bdddc534] #ref(flp.png,nolink,around,left,80%,); 化学プラントや工場では反応炉や加工機など複数の設備が配置され、その間を配管や搬送機器によって原料や仕掛品が流れていきます。スマートフォンやPC等の電子機器の中では複数の記憶装置や演算装置が接続され、互いに信号を送り合って動いています。施設レイアウト問題は、このような複数の要素から構成されるシステムにおいて要素間の輸送コストが最小になるような装置の配置を考える問題です。数十～数千個の要素から構成されるようなシステムに対して、効率的な配置を求める高速なアルゴリズムを研究しています。 #clear *** グラフ上におけるゲームの数理 [#oa075f80] #ref(fujimori.png,nolink,around,left,35%,); グラフ上におけるゲームは複数存在し，例えば以下のようなものが考えられます． - ①白または黒で彩色されている，異なる色の頂点を重ねることで頂点を消し，可能な限り頂点を少なくする1人用ゲーム - ②与えられたグラフに対して，限られた色数を用いて隣り合った頂点が同じ色を使わないように彩色していく二人用ゲームで，先手はすべての頂点が塗れたとき，後手はいずれか1頂点の周囲にすべての色が出現させるような状態にした時，勝利する これらのゲームを最善の手順で行うとどちらが勝つのか，頂点はどれだけ少なくできるのか，そのためのグラフの条件は何であるか 等といったことを数理的に研究します． #clear *** 無三角グラフの頂点樹化数 [#ha8a3389] #ref(arboric_coloring.png,nolink,around,left,50%,); 無向グラフは，いくつかの頂点と，いくつかの辺からなります．1つの辺は異な る2つの頂点を結び，辺の向きはありません．この研究では，「ある1つの色で塗 られた頂点からなる閉路が存在しない」という制限を課して各頂点に色を塗るこ とを考えます．ここで閉路とは，ある頂点から辺でつながれている頂点を1個以 上経由して元の頂点に戻ってくるような経路のことです．このような塗り方に必 要な最小の色の数をグラフの頂点樹化数といいます．また，頂点数3の閉路を含 まない無向グラフを無三角グラフといいます．例えば，図のグラフは無三角グラフであり，頂点樹化数は2となります．なぜなら，このグラフは閉路を含むので1 色では塗ることができず，また，2色で塗ることができたからです．この研究で は，無三角グラフの頂点樹化数について考察しています． #clear *** 提携に重複を許したロバストな提携構造形成問題の研究 [#r930d9e1] #ref(Yoshizawa.jpg,nolink,around,left,50%,); 提携構造形成問題とは、協力ゲーム理論の研究分野の１つで、 与えられたエージェントの集合を社会的余剰が最大化されるように分割する問題です。 エージェントの集合の部分集合を提携、分割を提携構造といいます。 エージェントが何らかの理由で離脱してしまうことがあるような場合にも 社会的余剰をなるべく大きく保てるような提携構造を探す問題として、 離脱に対してロバスト（頑健）な提携構造形成問題が研究されています。 また、一般に提携構造形成問題では１人のエージェントは１つの提携にしか 所属できませんが、拡張として、提携に重複のあるゲームが研究されています。 この研究では、提携に重複を許す場合のロバストな提携構造形成問題の特性や、 その求解手法を研究しています。 #clear *** 道幅を求めるアルゴリズムの研究 [#q120fd65] #ref(pwd.png,nolink,around,left,50%,); 点と線から成る数学的な事象をグラフと呼びます．グラフには道分解と呼ばれる変換が存在し，その中で道幅と呼ばれるパラメーターを求めるアルゴリズムの研究をしています．道幅が分かるとNP困難と呼ばれる難しい問題が簡単に解けたり，特殊なグラフの描画に役に立ちます．道幅はグラフから直接分かるものではなく，グラフから計算をして求める必要があります．道幅に似た概念に木幅と呼ばれるパラメーターがあり，道幅に比べて研究が盛んです．そのため，木幅を求めるアルゴリズムを道幅に応用することで高速に道幅を求めるアルゴリズムを開発することについて研究しています． (図の出典： http://dopal.cs.uec.ac.jp/okamotoy/lect/2016/treewidth/handout03.pdf ） #clear **過去の卒業論文，修士論文 [#ka1716b1] ***令和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:(文責：岡本吉央)
