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

1.给定一个有n个结点的图，我们设计了一个0(n^3)次的算法NMCLIQ来寻找一个接近最大的团。我们已经在几个多达400个结点的图的实验中证实，NMCLIQ找到的最大c)的阶几乎超过了最大阶的85%。我们开发了一个0(n^3)时间的算法RACLIQUE，用于在给定的n个结点的图中寻找一个接近最大的团。虽然该算法是基于Boltzmann机器的概念，但它不使用模拟退火法，因此很容易控制其执行。我们已经在实验中证实，对于几个多达400个结点的随机和非随机图，可以非常有效地找到几乎最优解。此外，进一步的改进和变化被认为是非常有用的。我们设计了两种非搜索算法来解决n皇后问题，这两种算法是在前人寻找接近最大团的结果的基础上提出的。我们已经在对多达50,000只蜂王的实验中证实，它们是极其高效的。

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.