効率的な最大および極大クリーク抽出アルゴリズムの開発と応用

高效最大派系提取算法的开发与应用

• 批准号: 17K00006
• 负责人: 富田 悦次
• 金额: $ 2.91万
• 依托单位: The University of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Scientific Research (C)
• 财政年份: 2017
• 资助国家: 日本
• 起止时间: 2017 至 2021
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-17K00006/
• 关键词: 最大クリーク; 極大クリーク; 深さ優先探索; 分枝限定アルゴリズム; 列挙; 近似アルゴリズム; 時間計算量; 符号理論; 分枝限定; アルゴリズム; 遅延; 多項式時間; 最大独立節点集合; 厳密解法; 近似解法; 実働評価; NP完全問題; 時間計算量解析; 多項式時間的可解性; 実働化評価; 分枝限定法

最大クリーク抽出は多くの実応用問題解決に対して有用であるがNP困難問題であり，一般的には求解に非常に長時間を要する．最大クリーク厳密解抽出の分枝限定アルゴリズムに対するこれまでの研究により，最大クリークの近似解が非常に有効に活用出来ることを明らかにしてきた．その近似精度が良くなれば分枝限定はより有効に働く．しかし，近似解抽出のために時間を要すると，総実行時間としては必ずしも短縮とはならず，近似精度と時間との兼ね合いが重要となる．そこで先ず，最大クリーク近似解の抽出を一層高速化し，その上で精度を向上させることにより，総合的に最大クリーク厳密解抽出を効率化した．続いて，分枝限定のために近似彩色だけでなくMaxSATも用いることにより分枝限定がより強力化されることをこれまでに確認してきたが，MaxSATあるいはその簡略形実行のためのオーバーヘッドの大きさが最大クリーク厳密解抽出総実行時間短縮の妨げとなっていた．これに対しては，MaxSATの簡略形と従来提唱してきていた再番号付け（再彩色）との類似性に着目して両者を融合させることにより，これまでよりも少ないオーバーヘッドによって，有効な分枝限定効果を発揮出来るようにした．さらに，分枝限定アルゴリズムの内部動作は入力グラフの特徴に応じて効率が左右されるため，出来る限り効率がより発揮されるようにと内部動作を適応的に切り替えるようにした．以上を総合することにより，最大クリーク厳密解抽出のための従来の分枝限定アルゴリズムを有意に高速化することに成功した．このような最大クリーク厳密解抽出アルゴリズムは，容易に最大クリーク全列挙アルゴリズムへと拡張出来る．これにより，符号理論における最良な多元単一削除訂正符号の構成に関しての新たな知見を得ることが出来た．また，極大クリーク全列挙問題についても理論的，実験的に検討を行い，有効な進展結果を得た．

Maximal extraction of multiple-use problem solving is useful for NP-hard problems, and general problem solving is time-consuming. The branch restriction of maximum solution extraction is studied. The approximate solution of maximum solution extraction is used in the study. Approximation accuracy is good, branching is limited, and approximation accuracy is good. Approximate solution extraction time is important, travel time is important, approximate accuracy is important, and time is important. In the first place, the extraction of the maximum approximation solution is a layer of high speed, the upper accuracy is an upward step, and the maximum approximation solution extraction of the total solution is an efficiency. In the middle of the branch limit, the approximate color is divided into two parts: MaxSAT, MaxSAT and MaxSAT. In this case, MaxSAT's simplified form is used to refer to the second color, and the similarity is used to refer to the fusion of the first color. In addition, the internal action of the branch limit is to enter the force of the characteristics of the branch limit. The internal action of the branch limit is to enter the force of the characteristics of the branch limit. The above is a combination of the following: The maximum number of entries in the list is easy to find. The theory of symbols is the best way to eliminate and correct the composition of symbols. The maximum number of problems in the whole series is calculated theoretically, and the actual results are obtained.

项目成果

最大クリーク問題に対する探索頻度情報にもとづく反復k-opt局所探索法の性能

基于搜索频率信息的迭代k-opt局部搜索方法求解最大团问题的性能

• 发表时间: 2019
• 期刊: 人工知能学会研究会資料
• 作者: 金原一歩;片山謙吾;富田悦次;松崎空良
• 通讯作者: 松崎空良

Speeding-Up of Construction Algorithms for the Graph Coloring Problem

图着色问题的构造算法加速

• 发表时间: 2020
• 作者: Kazuho Kanahara;Kengo Katayama;Takafumi Miyake;Etsuji Tomita
• 通讯作者: Etsuji Tomita

Enumeration of maximum cliques and its application to coding theory

最大团的枚举及其在编码理论中的应用

• 发表时间: 2019
• 作者: 金原一歩;片山謙吾;富田悦次;松崎空良;Etsuji Tomita
• 通讯作者: Etsuji Tomita

Efficient algorithms for finding maximum and maximal cliques

寻找最大和最大派系的有效算法

• 发表时间: 2017
• 作者: 長尾篤樹;松崎空良;富田悦次;伊藤大雄;若月光夫;西野哲朗;光武 朗，野崎隆之，富田悦次;Etsuji Tomita
• 通讯作者: Etsuji Tomita

富田悦次研究室 ホームページ

富田悦二实验室主页