项目来源

日本学术振兴会基金(JSPS)

项目主持人

伊藤 健洋

项目受资助机构

東北大学

项目编号

24H00686

立项年度

2024

立项时间

未公开

研究期限

未知 / 未知

项目级别

国家级

受资助金额

47450000.00日元

学科

情報科学、情報工学およびその関連分野

学科代码

未公开

基金类别

基盤研究(A)

关键词

組合せ遷移 ; アルゴリズム ;

参与者

宋剛秀；小林靖明；野崎雄太

参与机构

東北大学，情報科学研究科；神戸大学,DX・情報統括本部；北海道大学，情報科学研究院；横浜国立大学，大学院環境情報研究院

项目标书摘要：独立集合の遷移問題は,組合せ遷移の研究において中心的な問題であり,本研究課題でも研究対象の一つとして計画していた.「手法ベース」と「問題ベース」の両アプローチから,それぞれの視点を生かした研究解析が進められており,本研究課題はおおむね順調に進展していると判断している.本年度は,5月と11月の2回，研究代表者・分担者が対面で集まる打合せの場を持つことができた.特に5月に打合せを行ったことで,本研究課題の目的と研究方針を再共有することができ,スムーズに研究が開始できた.本研究課題では「手法ベース」と「問題ベース」という2つのアプローチから,解空間の形状の解析を進めている.両アプローチの知見を共有しながら,本年度は独立集合の遷移問題に関する研究に取り組んだ.特に,入力グラフの構造に着目して,それが解空間の形状に与える影響について解析を進めている.手法ベースのアプローチとして,独立集合の遷移問題を解くソルバーにおいて,遷移ルールの緩和が与える影響を解析・考察した.既存ソルバーには,解空間の直径が長くなるにつれて,性能が低下し得るという課題があった.そこで,遷移ルールを緩和することで,見かけの遷移長を短くするアプローチを検証した.ベンチマーク問題を用いて評価したところ,改善が得られた.問題ベースのアプローチとして,独立集合の遷移ルールの変更が,解空間の形状と計算困難性に与える影響を解析した.既存研究では主に2つの遷移ルールが知られているが,本研究では,それらを一般化する遷移ルールを新たに提唱した.これにより,既存研究と本研究を統一的に扱えるようになり,計算困難性への影響を理論的に解析することができた.また本年度は,九州大学マス・フォア・インダストリ研究所との共催で,組合せ遷移に関する国際ワークショップを福岡市で開催した.本ワークショップは,これまでも日本,カナダ,フランスで開催されており,今回が5回目の開催であった.国内外から集まった参加者らが,組合せ遷移に関連する最新の研究成果を発表し,未解決問題にも一緒に取り組むことができた.独立集合の遷移問題に関しては,今後も継続して研究を進める.特に注目しているのは,遷移ルールの緩和や変更,または,入力グラフの構造および独立集合の解サイズが,解空間の形状に与える影響を解析することである.また,これらの解析を通して得られた知見は,関連が深い他の組合せ遷移問題や様々な未解決問題にも適用を試みて,研究対象を広げていく予定である.Reason:独立集合の遷移問題は,組合せ遷移の研究において中心的な問題であり,本研究課題でも研究対象の一つとして計画していた.「手法ベース」と「問題ベース」の両アプローチから,それぞれの視点を生かした研究解析が進められており,本研究課題はおおむね順調に進展していると判断している。Outline of Research at the Start:「組合せ遷移」とは,可用性を担保しながら最適化するためのアルゴリズム理論である.15年以上にわたり,アルゴリズムと計算量の理論研究が盛んに行われている.また最近では,様々な手法に基づく組合せ遷移のソルバーが開発され,一般には計算困難である組合せ遷移問題であっても,高速に解ける事例が散見され始めている.本研究では「解空間の形状」という組合せ遷移ならではの新しい概念を導入し,そのような事例群の理論的な解析に取り組む。