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