2024年4月から9月にかけて、The Algorithmic Foundations for Social Advancement (AFSA)による国際コンペティション「International Competition on Graph Counting Algorithms2024(ICGCA2024)」が開催され、九工大情報工学研究院アルゴリズム研究グループのチーム「KAG-TeamS」が出場しました。本コンペティションでは、グラフ上のパスの数え上げ問題をより効率的に解くプログラムを競います。
KAG-TeamSは、ソルバー KAGを開発し、競技4部門のうち2部門で2位、残りの2部門で3位を獲得するとともに、ソルバーの解説論文「Effective Preprocessing and Dynamic Programming Algorithms using Zero-suppressed Binary Decision Diagrams」が論文賞を受賞しました。
KAG-TeamSは、昨年度のコンテストでパス分解に基づく動的計画法とハミルトン閉路を計算する動的計画法の2つの手法をゼロサプレス型二分決定グラフと呼ばれるデータ構造を用いたアルゴリズム を実装しました。今年のコンテストでは有向グラフおよび重み付きグラフに対応するように拡張するとともに、グラフ縮小アルゴリズムを強化したソルバー KAGを開発しました。ソルバー KAG は、競技4部門のうち2部門で2位、残りの2部門で3位を獲得し、またソルバーの解説論文「Effective Preprocessing and Dynamic Programming Algorithms using Zero-suppressed Binary Decision Diagrams」が論文賞を受賞しました。
また、2024年12月21日に慶應義塾大学日吉キャンパスで、人工知能学会合同研究会における第130回人工知能基本問題研究会(SIG-FPAI)が開催され、コンペティションの結果発表および受賞者による記念講演が行われました。
【受賞対象】
| ソルバー | KAG |
| 解説論文タイトル | Effective Preprocessing and Dynamic Programming Algorithms using Zero-suppressed Binary Decision Diagrams |
| 受賞者 | 前田 惠太(大学院情報工学府 博士前期課程情報創成工学専攻(知能情報) 1年) 野間 隆眞(情報工学部 知能情報工学科人工知能コース 4年) 齋藤 寿樹(大学院情報工学研究院 知能情報工学研究系 教授) 塩田 拓海(大学院情報工学府 博士後期課程情報創成工学専攻(知能情報) 2年) 立花 真龍(情報工学部 知能情報工学科人工知能コース 4年) 田口 直哉(大学院情報工学府 博士前期課程情報創成工学専攻(知能情報) 1年) 高雄 奏摩(情報工学部 知能情報工学科メディア情報学コース 4年) |
◇コンペティションサイトはこちら。
◇結果に関するページはこちら。
AFSA領域代表者 湊 真一氏(左)と前田 惠太さん(右)
受賞記念講演中の前田 惠太さん
賞状
