譚教授が「情報とマネジメント分野のアルゴリズムに関する国際会議」で最優秀賞論文賞を受賞しました

情報理工学部コンピュータ応用工学科の譚学厚教授が、8月10日から12日まで中国金華市で開催された「情報とマネジメント分野のアルゴリズムに関する国際会議」で「射線巡回および関連問題に対する多項式時間アルゴリズムの開発」に関する研究論文をオンラインで発表。その内容が評価され、最優秀賞論文賞を受賞しました。

計算幾何学を専門とする譚教授は、「巡回セールスマン問題」や「警備員巡回路問題」と呼ばれる、決められた地点を最短経路で回るルートの最適解を求めるアルゴリズム研究に取り組んでいます。巡回セールスマン問題は、セールスマンがいくつかの都市をすべて訪問して出発点に戻る際に移動距離が最小になる経路を求めるもので、回る地点が少ないときには組み合わせも少ないため、すぐに解を求めることができますが、地点が増えれば増えるほど組み合わせが増え、高性能なコンピュータを用いても最適解を求めることが困難になっています。警備員巡回路問題は与えられた多角形領域P(例えば、美術館や工場など)に対し、Pの任意の点が巡回路上の少なくとも1点から見えるような最短の巡回路を計算するものですが、P内の直線線分の集合を訪れる最短経路を求めることに帰着されることができるため、多項式時間のアルゴリズムは譚教授の研究グループによって初めて提案されていました。譚教授は、今回の国際会議では「射線集合を対象にした巡回セールスマン問題」と「与えられた線分集合のどの線分も少なくとも1点を含む境界最短の凸多角形の計算問題」に関する研究論文を発表しました。

最優秀論文賞受賞について、「今回の学会は新型コロナウイルス感染拡大の影響を受け、オンラインでの参加となりましたが、これまでの研究成果が評価され大変光栄です」と語り、「一見すると私たちの生活と関係のない問題も、解決の積み重ねで大きな研究成果につながります。世界中の誰も解けていない問題や解法が見つからないと決めつけられている問いに対して、何度も何度も試行錯誤を重ねる行為は決して楽しいことばかりではありません。しかし、難題であればあるほど答えが見つかったときの喜びは大きい。今回の受賞が多くの人に伝わり、学生たちにもこの研究の魅力が伝わるきっかけになればうれしい」と話しています。