理化学研究所 計算科学研究センター

メニュー
メニュー
Events/Documents イベント・広報

Graph Golf 2018 で中尾 昌広 研究員がダブル受賞

盾を手にした中尾研究員の写真

プログラミング環境研究チームの中尾昌広 研究員が Graph Golf 2018 において「Widest Improvement Award」・「Deepest Improvement Award」の2つの賞を受賞し、11月27日、岐⾩県⾼⼭市で開催された国際シンポジウム 「CANDAR '18」で表彰されました。

Graph Golf では、ある「頂点数」と「次数(1つの頂点から出る辺の数 )」を持つグラフがいくつか出題され、「1つの頂点から最も離れた頂点までのホップ数」と「全頂点間のホップ数の平均値」が最も小さいグラフの設計を競います。

中尾研究員は、Simulated Annealing(SA)と呼ばれる汎用的な最適化アルゴリズムと、出題されているグラフに対称性を持たせることで、SAの解探索性能と高速化の両方を達成できるアルゴリズムの開発を行いました。特に高速化については、MPIとOpenMPを用いたハイブリッド並列を行うことにより、アルゴリズムの工夫とを組合せて最大2,000,000倍の高速化を達成しました。

中尾研究員が受賞した盾の写真

「Widest Improvement Award」は、最良解を最も多く設計した人に、「Deepest Improvement Award」は、理論的な下界に最も近いグラフを設計した人に与えられます。
前者はアルゴリズムの汎用性の高さを評価するのに対し、後者は問題に特化したアルゴリズムの性能の高さを評価します。

Widest/Deepest をダブル受賞した今回のアルゴリズムは、汎用性と性能を兼ね備えた、非常に有用なアルゴリズムだと言えます。

関連情報