わたしの研究

この文章は,"市大広報"のために執筆した文章です.

私の研究‐並列分枝限定法‐

学術情報総合センター
ネットワーク部門担当助手
大西克実

今回,この紙面をお借りして「私の研究」という事で記 事を書かせて頂く事になりました.わかりやすい説明を 心掛けますので,是非最後までおつき合い下さい.私の 研究をひとことで言いますと,『大規模な組合せ最適化 問題を並列化した分枝限定法で効率良く解く』ことを目 標としています.まず,組合せ最適化問題とは? とい うところからお話しします.

組合せ最適化問題には,細かく分けるとたくさんの問題 が含まれていますが,私が特に対象としているのは,巡 回セールスマン問題(TSP:Traveling Salseman Problem) です.紙の上に適当に好きなだけ点を書き,その中から 出発点を選びます.紙の上にあるすべての点を,一筆書 きの要領でどの点も一度ずつ通って出発点に戻る道を考 えて下さい.

そのような道は,点の数が増えるとたくさん考える事が 出来ます.TSP は,このたくさんの道の中で,長さが最 も短い道を見つけ出すことを目的としています.点の数 がそれほど多くなければ,目で見て一番短そうな道を考 えるのも難しくないでしょう.

ところが,点の数が100個とか1000個等になったら,目 で見て一番短い道を調べるという事は出来ません.そこ で計算機に調べさせる事を考えて見ます.ところが,今 の計算機には,目で見て直観で答えを出すような芸当は 出来ませんので,すべての道の長さを数え上げるという 方法を考えます.

道の数は,点の数を n とすると(n-1)*(n-2)*…*1 のよ うな組合せの数になりますので,単純に数え上げるだけ では,点の数が多くなるとたとえ計算機でも時間がかか ります.そこで,単純に数え上げるのではなく,数え上 げる途中で見つけた答えをとりあえず記憶しておきます. 次に,これから数え上げてようとしている道に見込みが あるかどうかをあらかじめ考えるなどの方法を使って無 駄を出来るだけ省くようにした解法が分枝限定法という 事になります.

この分枝限定法を使ってもなかなか解けない問題に対し ては,1台の計算機ではなく,たくさんの計算機を利用 して,速く答えを得られないかということが考えられて います.

インターネットに代表されるように,今では遠くにある コンピュータであっても実際の距離を気にする事無く利 用できる環境が整っています.以前は,1台ではなかな か解きにくい場合,専用に設計された並列計算機を利用 するしか方法がありませんでしたが,ネットワーク技術 を使ってお互いに接続されたさまざまな計算機を利用で きるようになりました.

ネットワークを利用して互いに接続された計算機を利用 する場合,各々の計算機の能力に応じて各計算機の間で 無駄なく仕事を分ける必要があります.なにもせずに遊 んでいる計算機がたくさんあるような状態になることは 好ましくありません.

あらかじめ全体での仕事の大きさがわかっていれば,最 初に適切な割当を考える事も出来るのですが,TSP の場 合はそうもいきません.さらに,専用の並列計算機とは 異なり,いろいろな計算機を利用できますので,各々の 計算機の能力や忙しさは,時々刻々変化する事もありま す.

そこで,問題を解いている途中で各計算機の忙しさを考 慮する等して,仕事の割当を適宜考え直す事になります. 複雑な方法を考えて,本来の数え上げのための時間を圧 迫するようでもいけません.ある問題に対して有効だっ た方法が,他の問題に対しても必ず有効であるとも限り ません.

こんな事を考慮しながら,より速く,より大きな問題を たくさんの計算機を使って効率良く解ける方法を考える と言う事が私の研究と言う事になります.

(1997年4月)
ご質問の宛先: onisi@media.osaka-cu.ac.jp


前のページ


onisi@media.osaka-cu.ac.jp
Last modified: Thu Apr 3 19:47:29 JST 1997