Shrivastava Y, Dasgupta S, Reddy S M
Dept. of Electr. and Comput. Eng., Iowa Univ., Iowa City, IA.
IEEE Trans Neural Netw. 1992;3(6):951-61. doi: 10.1109/72.165596.
A class of symmetric Hopfield networks with nonpositive synapses and zero threshold is analyzed in detail. It is shown that all stationary points have a one-to-one correspondence with the minimal vertex covers of certain undirected graphs, that the sequential Hopfield algorithm as applied to this class of networks converges in at most 2n steps (n being the number of neurons), and that the parallel Hopfield algorithm either converges in one step or enters a two-cycle in one step. The necessary and sufficient condition on the initial iterate for the parallel algorithm to converge in one step are given. A modified parallel algorithm which is guaranteed to converge in [3n/2] steps ([x] being the integer part of x) for an n-neuron network of this particular class is also given. By way of application, it is shown that this class naturally solves the vertex cover problem. Simulations confirm that the solution provided by this method is better than those provided by other known methods.
详细分析了一类具有非正突触和零阈值的对称霍普菲尔德网络。结果表明，所有稳定点与某些无向图的最小顶点覆盖一一对应，应用于这类网络的顺序霍普菲尔德算法最多在2n步内收敛（n为神经元数量），并且并行霍普菲尔德算法要么在一步内收敛，要么在一步内进入双周期。给出了并行算法在一步内收敛的初始迭代的充要条件。还给出了一种改进的并行算法，对于这类特定的n神经元网络，该算法保证在[3n/2]步内收敛（[x]为x的整数部分）。作为应用示例，表明这类网络自然地解决了顶点覆盖问题。仿真结果证实，该方法提供的解决方案优于其他已知方法。
