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）时间算法NMCLIQ来寻找一个近最大团。我们已经在实验中证实了几个多达400个节点的图，NMCLIQ发现的最大c）iques的阶数几乎超过最大阶数的85%。我们已经开发了一个0（n^3）-时间算法RACLIQUE寻找一个近最大团在一个给定的图的n个节点。虽然该算法是基于玻尔兹曼机的概念，但它不采用模拟退火，因此易于控制其执行。我们已经证实，在实验中的几个随机和非随机图与多达400个节点，几乎最优的解决方案可以非常有效地找到。此外，进一步的改进和变化被认为是非常有用的。我们设计了两个非搜索算法的n皇后问题的基础上，前resuit找到一个接近最大集团。我们已经在多达50000只蚁后的实验中证实，它们是非常有效的。

项目成果

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 技术报告。

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

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

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

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

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

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

TAKAHASHI, Haruhisa: ""Biological plausibility of backpropagation"" IEICE Technical Report. NC90. 31-38 (1990)

TAKAHASHI、Haruhisa：“反向传播的生物学合理性”IEICE 技术报告。