更新日:2023.09.26
2023年4月から9月にかけて、The Algorithmic Foundations for Social Advancement (AFSA)による国際コンペティション「International Competition on Graph Counting Algorithms(ICGCA)」が開催され、九工大情報工学研究院アルゴリズム研究グループのチーム「KAG-TeamS」が出場しました。本コンペティションでは、グラフ上のパスの数え上げ問題をより効率的に解くプログラムを競います。
KAG-TeamSは、パス分解に基づく動的計画法とハミルトン閉路を計算する動的計画法の2つの手法をゼロサプレス型二分決定グラフと呼ばれるデータ構造を用いたアルゴリズムを開発しました。そのアルゴリズムを実装したソルバー TAG が、150問のインスタンスのうち126問を解くことに成功し、競争部門で3位、アイディア部門で2位を受賞しました。
また、2023年9月7日に大阪公立大学でFIT 2023 のイベント企画として実施されたICGCAシンポジウムにおいて、コンペティションの結果発表および受賞者による記念講演が行われました。
【受賞対象】
| ソルバー | TAG |
| 解説論文タイトル | A Hybrid Method of Two Dynamic Programming Algorithms for Counting Paths using Zero-suppressed Binary Decision Diagrams |
| 受賞者 | 有吉優聖(大学院情報工学府 情報創成工学専攻 博士前期課程1年) 土井朋哉(大学院情報工学府 学際情報工学専攻 博士前期課程(修了)) 藤岡祐太(大学院情報工学府 情報創成工学専攻 博士前期課程2年) 岩崎巧実(大学院情報工学府 情報創成工学専攻 博士前期課程2年) 前田惠太(情報工学部 知能情報工学科 4年) 斎藤寿樹(大学院情報工学研究院 知能情報工学研究系 准教授) 塩田拓海(大学院情報工学府 情報創成工学専攻 博士後期課程1年) 田口直哉(情報工学部 知能情報工学科 4年) |
◇コンペティションサイトはこちら。
◇結果に関するページはこちら。
AFSA領域代表者 湊 真一氏(右)と情報工学部 知能情報工学科4年 ⽥⼝直哉さん(左)
受賞記念講演中の⽥⼝直哉さん
表彰状
