和佐州洋
膨大かつ複雑なデータから有用な情報を抽出
グラフで記述された複雑なデータから有用な情報を抽出する重要性が,SNSや生命科学など分野を問わずに増している.列挙アルゴリズム,すなわち,与えられたデータから,制約を満たす部分構造を全て出力するアルゴリズムは,このような要請を実現するための基盤技術の一つである.本稿では,列挙アルゴリズムに関する評価方法,困難性の判定,及び,代表的な技法について,現在の状況を解説する.
膨大かつ複雑なデータから有用な情報を抽出
グラフで記述された複雑なデータから有用な情報を抽出する重要性が,SNSや生命科学など分野を問わずに増している.列挙アルゴリズム,すなわち,与えられたデータから,制約を満たす部分構造を全て出力するアルゴリズムは,このような要請を実現するための基盤技術の一つである.本稿では,列挙アルゴリズムに関する評価方法,困難性の判定,及び,代表的な技法について,現在の状況を解説する.
制約条件を満たすグラフを全て列挙する
本稿では,ZDDと呼ばれる圧縮データ構造と,フロンティア法というグラフ列挙アルゴリズムを紹介し,最適化や故障解析などへの応用例を述べる.ZDDは,四半世紀前にVLSI論理設計分野で生まれた.現在では人工知能の知識コンパイル分野などを中心に研究されており,フロンティア法との出会いによってグラフ問題への有望なアプローチの一つとなっている.本稿で紹介する電力網最適化のように扱いにくい制約条件を持つ問題であっても,実行可能な部分グラフを圧縮データ構造として「列挙」していくことで解空間を構造化し,最適化を行える.また,グラフ列挙に関する多くの問題は#P完全であることが知られており,そのような問題への挑戦は計算機科学の観点から興味深い.本稿はZDDとフロンティア法の基礎を解説するとともに,実問題への適用事例を幾つか紹介する.
シニアにできる科学の未来に向けて!
日本の高度成長を支えた企業の技術者が,定年後手持ち無沙汰に毎日を過ごし,生きがいや楽しみが感じられる機会を失っている.そこで,子供の科学離れ,理工系離れの解決策の一助とすべく,ボランティアで子供科学教室の開催の機会を得たことで,多くの感動を得,楽しい時間を過ごすことができたので報告する.子供が興味を持って工作しているときの真剣な目,自分で物を作り,作ったものが動いたときの喜びの顔は格別であり,忘れられない.また科学教室後に開催した懇親会での,ボランティア参加の学生とのおしゃべりも楽しい一時である.
一人でも多くの子供が科学に興味を持って育っていき,日本の科学技術の発展に貢献する人材を輩出できるよう,一人でも多くのシニアの方が科学教室を開催して,非日常の感動を得ることを願ってやまない.
距離空間によるモデリング,解法と最適化理論
CAT(0)空間と呼ばれるユークリッド空間や双曲空間を一般化した距離空間がある.CAT(0)とは,「曲率が非正」ということを意味している.この空間は,ユークリッド空間で成り立つ様々な良い性質を引き継いでいる.特に,任意の2点を結ぶ測地線(≃最短路)が一意に定まる.このことから凸関数なども自然に定義される.最近になって,CAT(0)空間を利用したモデリングやその上でのアルゴリズム・最適化理論が展開され始めている.本稿では,そのような試みの一端を紹介する.
複雑なネットワーク設計問題に近似解を与える解析法とその適用例
所望の制約を満たすネットワークの中でできるだけ低コストのものを求めるネットワーク設計問題は,典型的なグラフ最適化問題の一つである.故障に強い通信ネットワークを構築するのに役立つだけではなく,計算機科学の多岐にわたる分野に応用を持つ.本稿では,ネットワーク設計問題に対する手法の一つであるスパイダ被覆アルゴリズムの基礎と最新の研究動向を紹介する.
パズルの背景にある数学から,持続的システムへの応用まで
組合せ遷移とは,パズルや持続的システムといった動的な状況を定式化することに適し,最近10年ほどで急速に研究が発展・深化した研究トピックである.実行可能解が一つでも存在するか判定する従来の問題に比べ,組合せ遷移では実行可能解が形成する解空間での到達可能性が問われる.本稿ではまず,組合せ遷移の枠組みと研究背景を紹介する.次に,最近の研究動向を解説するとともに,組合せ遷移におけるアルゴリズム開発を紹介する.