電子情報通信学会総合大会チュートリアル講演

「計算限界の中心で解法をさけぶ」

第一部講演要旨

杉原厚吉（東京大学大学院情報理工学系研究科）
	「幾何計算駆け込み寺住職体験記」
		私のウエブページで「幾何計算でお困りの方の相談に乗ります」というメッセージを発信して７，８年になります。この間、いろいろな相談を受けましたが、その経験から、適切に相談に乗ることの難しさを痛感しています。もっとも難しいのは、相談する方とされる方で、問題を共通に理解するまでのところです。共通の理解に達することができれば、あとは解法を考えるだけで、それは楽しい作業です。失敗例と成功例をお話しして、どうすれば問題を共有できるかを考えてみたいと思います。
徳山豪（東北大学大学院情報科学研究科）
	「計算理論の先端的手法による実用分野開拓 −データマイニングを例にして」
		計算理論やアルゴリズム理論の教科書では、さまざまな数学的手法が紹介されており、複雑な計算階層や巧みなデータ構造を見ると、専門的で近づき難い印象さえ与えている。　実際、これらの手法を駆使して多くの既存問題の改良が日々行われている。しかしながら一方、第一線の計算理論の研究者は常に新たな開拓的研究を模索しており、そこで必要なのは、「現実に与えられた問題をどのように計算理論の俎上にのせるか」あるいは，「どのような数学的道具が現実問題を解くために必要であるか」という異なった趣の思考法である。すなわち、物理学や化学で現実世界の現象を解明するために実験装置や理論モデルを構築していくのと類似したセンスである。ここでは、「データマイニング」という比較的新しい実用分野の開拓における計算理論の利用を例にして、講演者自身の経験を中心にして、計算理論の研究と実用の現場を紹介する。
玉木久夫（明治大学理工学部）
	「組合せ最適化に対する巨大近傍アプローチ」
		組合せ最適化問題に対する実用的解法として局所探索法はよく用いられるが、局所的な最適解に陥りやすいという問題を持っている。この問題を克服するためのひとつのアプローチである巨大近傍アプローチについて、巡回セールスマン問題やグラフ描画問題などの実例を用いながら解説する。
柳浦睦憲（京都大学大学院情報学研究科）
	「メタヒューリスティクスに基づく問題解決エンジン」
		メタヒューリスティクスは、組合せ最適化問題をはじめとする種々の問題に対する強力な手法の一つとして定着してきている。しかし、そのアイデアに基づいて実際に良いアルゴリズムを作るには大きな労力が必要であり、解きたい問題のそれぞれに対して一からアルゴリズムを開発するのは効率的でない。そこで、我々は、広いクラスの問題をカバーできる標準問題をいくつか選び、それらに対するアルゴリズムを用意しておくことで、応用上重要な多くの問題に対する問題解決エンジンを提供することを目指して研究を進めている。この試みの成果の一端を紹介する。