Development and Evaluations of Efficient Algorithms for Finding a Maximum Clique Based upon Nueral Networks

基于神经网络寻找最大团的高效算法的开发和评估

• 批准号: 02650261
• 负责人: TOMITA Etsuji
• 金额: $ 1.79万
• 依托单位: The Univesity of Electro-Communications
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for General Scientific Research (C)
• 财政年份: 1990
• 资助国家: 日本
• 起止时间: 1990 至 1991
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/grant/KAKENHI-PROJECT-02650261/
• 关键词: Neural network; Graph; Clique; Boltzmann machine; Randamized algorithm; N-queen problem; 近似アルゴリズム; アルゴリズム; nークィ-ン問題

1. Given a graph of n nodes, we have devised an 0(n^3)-time algorithm NMCLIQ for finding a near-maximum clique. We have confirmed in experiments for several graphs with up to 400 nodes that the orders of maximal c)iques found by NMCLIQ are almost more than 85% of the maximum orders.2. We have developed an 0(n^3)-time algorithm RACLIQUE for finding a near-maximum clique in a given graph of n nodes. While the algorithm is based upon the notion of Boltzmann machines, it employs no simulated annealing and hence is simple to control its execution. We have confirmed in experiments for several random and nonrandom graphs with up to 400 nodes that almost optimum solutions can be found very efficiently. In addition, further improvements and variations are considered and verified to be very useful.3. We have devised two non-searching algorithms for the n-queen problem which are based upon the former resuit for finding a near-maximum clique. We have confirmed in experiments for up to 50, 000 queens that they are extremly efficient.

1。给定n个节点的图，我们设计了一个0（n^3）-Time算法NMCliq，用于查找接近最大的最小值。我们已经在实验中确认了几个图表的最多400个节点，即最大c）NMCliq发现的IQUE的命令几乎超过最大订单的85％以上。2。我们已经开发了一个0（n^3） - 时间算法raclique，用于在给定的n个节点图中找到接近最大的集合。尽管该算法基于Boltzmann机器的概念，但它没有模拟退火，因此可以易于控制其执行。我们已经在实验中确认了几个随机图和非随机图，最多可以非常有效地发现了几乎最佳的解决方案。另外，考虑进一步的改进和变化非常有用3。我们已经为N-Queen问题设计了两种非搜索算法，这些算法基于以前的重新构建，用于查找接近最大的集团。我们已经在实验中确认了多达50 000皇后的实验，它们的效率非常高。

项目成果

本村 陽一: "連続関数の領域区分近似を実現するネットワ-ク" 電子情報通信学会非線形問題研究会技術研究報告. NLPー91. 1-8 (1991)

本村阳一：“实现连续函数的域分割近似的网络”电子信息通信技术研究所非线性问题研究组的技术研究报告1-8（1991）。

山田 義朗: "非探索アルゴリズムによるnーqueen問題の解法" 電子情報通信学会コンピュテ-ション研究会技術研究報告. COMPー90. 87-92 (1990)

Yoshiro Yamada：“使用非搜索算法解决 n 皇后问题”IEICE 计算研究组技术研究报告（1990 年）。

YAMADA, Yoshiaki: ""Applying the notion of Boltzmann machines to have an algorithm for finding a near-maximum clique and its experimental evaluations"" IEICE Technical Report. COMP91. 63-68 (1991)

YAMADA、Yoshiaki：“应用玻尔兹曼机的概念来建立一种寻找接近最大团的算法及其实验评估””IEICE 技术报告。

山田 義朗: "ボルツマンマシンの概念を応用した近似最大クリ-ク抽出アルゴリズムの実験的評価" 電子情報通信学会コンピュテ-ション研究会技術研究報告. COMPー91. 63-68 (1991)

Yoshiro Yamada：“应用玻尔兹曼机概念的近似最大团提取算法的实验评估”IEICE 计算研究组技术研究报告（1991）。

山田 義明: "ボルツマンマシンの概念に基づいた近似最大クリ-ク抽出アルゴリズムとその実験的評価" 電子情報通信学会論文誌DーI.

Yoshiaki Yamada：“基于玻尔兹曼机概念的近似最大派系提取算法及其实验评估”IEICE Transactions DI。