加藤 直樹

構造体の動きが元々の構造体の合同変換のみである場合,その構造体は剛であるとする.剛な棒材(bar)とピン接合(joint)で構成される構造体をbar-jointフレームワークとよぶ.剛な構造体からどの棒材を1つ取り除いた場合にも,剛ではなくなる(柔軟となる)フレームワークのことを極小剛とよぶ.本研究では,空間充填立体のbar-jointフレームワークに対して,最小本数のブレースを追加することで極小剛とする手法を示す.

各頂点が整数格子上にある,2次元bar-jointフレームワーク(グリッドフレームワーク)に対して筋交いを入れ,極小剛にする問題を考える.グリッドフレームワークの概形が長方形の場合の組合せ的な特徴付けは既に知られているが,本論文では概形がrectilinear polygonである場合にもその特徴付けが拡張できることを示した.また内部の頂点をいくつか取り除いた,より一般的なグリッドフレームワークに対して,それを極小剛にするアルゴリズムを提案した.

e-サイエンスとは,計算機,データ,実験装置などを高速ネットワークを介して共有しながら行う科学の新しい方法論を指すが,高速通信網の整備,計算機速度の飛躍的向上に伴い,e-サイエンス時代は既に始まっている.本稿では,その時代に向けたアルゴリズムはどうあるべきかという観点から,筆者が中心になって提案し,学術会議大型施設計画・大規模研究計画マスタープラン2011に採択された「e-サイエンスに向けた革新的アルゴリズム基盤」のプランの概要を紹介する.また,サイエンスデータの巨大さゆえに従来のアルゴリズムの高速化を実現する必要があり,そのためにはアルゴリズム設計のパラダイムの変革が求められている.本稿では,この点についての基本的考え方を提案する.

本研究では、優れた避難所割り当てを発見する手法の提案を目的とする。しかし、避難所割り当てを優れていると評価するためには、多様な評価基準が存在し、一義的にそれを定めることは難しい。そこで、多目的最適化手法を用いて、パレート最適解となるような避難所の割り当てパターンを探索する。また、可能な避難所割り当てパターンを全て列挙したのちに、個々の解を評価して優れた避難所割り当ての抽出を行う列挙-評価手法を用いる。以上の二つの手法を用いて、大阪市住吉区における優れた避難所割り当ての発見を試み、手法の検討を行う。

頑健な防災計画を実現するには、冗長性を持った設備計画とともに、考えうるシナリオすべてにおいて実際に計画を策定・検証できなければならない。しかし避難計画において、「1 秒でも早く多くの人が避難完了をするUniversally Quickest Flow(UQF)を求めるための計算は対象となる時間×空間に依存するネットワークに対する計算が必要になるため、多数のシナリオに対する繰り返し計算は困難であるという問題があった。本研究では動的ネットワークの計算に用いられるtime-expanded networkを用いずにUQF近似解を計算するアルゴリズムを提案する。提案手法の計算時間は対象となる空間の範囲のみに依存するため、南海トラフ地震の津波被害が懸念される大阪市のような大規模な都市においても高速にUQF の近似解を求めることが可能になる。

最速輸送問題は,動的ネットワークの点上に配置された供給のすべてをできるだけ早く到達点のいずれかに,到達点の容量を超えないように輸送する問題である.本稿では避難計画におけるモデル化では最速避難の方針として避難完了時間の最小化,移動時間総和の最小化,各時刻の避難完了者数を時間昇順で最大化する,の3つが考えられることを説明し,3番目の方針が緊急避難のモデル化として適していること,及びその計算の高速なヒューリスティックを紹介する.

本研究では,凸多面体をpanel-hingeフレームワークとみなしたとき,端点を共有しない辺(マッチング辺)のヒンジを全て取り除いても,フレームワークが無限小剛のままであることを証明する.また,同様のフレームワークから互いに頂点を共有しないパネルを全て取り除いても無限小剛のままであるための十分条件を示す.ただし本研究はヒンジが一般的な配置,すなわち各ヒンジを表す直線間に代数的な依存関係がない状態を前提としている.

本研究では、直交する 3 種類の長方形パネルに限定した剛な panel-hinge フレームワークを実現する問題を考察する。Higashikawa らは最近、極小剛な panel-hinge graph をすべて導出するアルゴリズムを提案しているが、われわれが考察するフレームワークは generic ではないので、このアルゴリズムは適用できない。そこで、panel-hinge framework を導出する新たな操作を捉案し、それにもとづき、直交するパネルによるフレームワーク生成法を構築する。

本論文では,動的パスネットワークにおけるk-施設配置問題を扱う.本モデルにおいて動的パスネットワークは,正のサプライ(避難者数)が与えられた頂点及び正の辺長と一様な辺容量をもつ辺からなるパス状の無向グラフによって構成される.あるk-避難施設配置xが与えられたとき,xに対する最適避難においては各避難者の動線が交差する事は無い.さらに本論文では,同一頂点に与えられたすべての避難者は同一施設に避難することを仮定している.したがって各隣接施設の間には,ある点より左側の避難者は左の最寄り施設へ,右側の避難者は右の最寄り施設へ避難するような境界点が必ず1つ存在し,それらを表すk-1次元ベクトルをdとする.このとき問題の目的は,k個の避難施設配置x及びk-1個の境界点配置dによって定まる避難完了時間を最小化するようなx及びdを決定することである.本論文では,以上の問題に対してO(kn log n)時間アルゴリズムを提案した.ここでnはネットワークの頂点数である.

本論文では,body-hingeグラフGがk-辺連結(k≧3)であることは,Gが(k-1)-edge-rigidであるための必要十分条件であることを示す.ここで,任意の(k-1)本の辺をbody-hingeグラフGから取り除いてできるグラフが剛であるとき,Gはk-edge-rigidであるとする.さらに,body-hingeグラフGがk-vertex-rigidであるとき,Gはk-連結であり,Gが(k+2)-連結であるとき,hを0≦h≦k-1として,Gが(k-h,h+2)-rigidであることを示す(k≧1).ここで,任意の(k-1)個の頂点をbody-hingeグラフGから取り除いてできるグラフが剛であるとき,Gはk-vertex-rigidであるとし,任意の(i-1)個の頂点をGから取り除いてできるグラフがj-edge-rigidであるとき,Gは(i,j)-rigidであるとする.

1-D-4

本論文では,最大後悔値最小化を目的とする,動的パスネットワーク上における施設配置問題を扱う.動的パスネットワークは,正の辺長と一様な辺容量をもつ無向パスによって構成される.各頂点においてはサプライ(避難者)のインターバルが与えられており,各頂点に対してインターバルを満たすような供給の割り当てをシナリオと呼ぶ.あるシナリオsの下で1つの施設(避難所)の位置をxと決定したとき,シナリオsにおける施設配置飢のコストを,sの与えるネットワーク上のすべてのサプライがxへの避難を完了するために必要な最小時間として定義する.このとき,sにおけるxの後悔値を,sのコストからsにおける最適配置のコストを引いたものと定義する.さらに,sの最大後悔値を,sの後悔値のすべての可能なシナリオに対する最大値と定義するとき,問題の目的は最大後悔値を最小化する施設配置を求めることである.本論文では,以上の問題に対して0 log n)時間アルゴリズムを提案した.ここでnはネットワークの頂点数である.この結果は[6]によって提案されたアルゴリズムの計算時間を改善している.

本論文は極小剛なbody-hingeグラフの列挙問題を扱っている．3次元bar-jointフレームワークの剛性に対する組合せ的特徴付けは知られていないが，その特殊構造であるbody-hingeフレームワークに対しては組合せ的特徴づけが知られている．剛体(body)を頂点，剛体どうしをつなぐヒンジを辺で表したグラフをbody-hingeグラフとよぶ．本研究では極小剛なbody-hingeフレームワークを表すbody-hingeグラフをすべて列挙する問題を考察する．まず，所与のbody-hingeグラフからより大きなサイズのbody-hingeグラフを生成する4つの操作を提案し，この操作によりすべてのbody-hingeグラフが生成可能であることを証明する．これにより，すべてのbody-hingeグラフを生成するアルゴリズムを提案する．計算時間は一つのbody-hingeグラフあたり多項式時間で済む．

本論文は極小剛なbody-hingeグラフの列挙問題を扱っている.3次元bar-jointフレームワークの剛性に対する組合せ的特徴付けは知られていないが,その特殊構造であるbody-hingeフレームワークに対しては組合せ的特徴づけが知られている.剛体(body)を頂点,剛体どうしをつなぐヒンジを辺で表したグラフをbody-hingeグラフとよぶ.本研究では極小剛なbody-hingeフレームワークを表すbody-hingeグラフをすべて列挙する問題を考察する.まず,所与のbody-hingeグラフからより大きなサイズのbody-hingeグラフを生成する4つの操作を提案し,この操作によりすべてのbody-hingeグラフが生成可能であることを証明する.これにより,すべてのbody-hingeグラフを生成するアルゴリズムを提案する.計算時間は一つのbody-hingeグラフあたり多項式時間で済む.

平面上の点集合に対して,剛性を持った構造物を表す基本的な構造として静定グラフ(ラマングラフ)というものが知られている.本稿では,制限付き静定グラフを列挙するアルゴリズムを設計し,そのアルゴリズムを広範なコンプライアントメカニズム生成の初期解として利用した結果を解説する.