四色和K色图着色问题的瞬态混沌神经网络解法

首先给出了用神经网络求解四色图着色问题的神经网络结构和能量函数 ,然后采用了具有瞬态混沌特性的神经网络 ( TCNN)来解四色图着色问题 .由于引入具有复杂动态特性的瞬态混沌使得该法具有很强的搜索全局最优解的能力 .仿真结果表明 ,用该法解四色图着色问题总能保证使能量函数收敛到最优解 ,有效避免了用传统的 Hopfield人工神经网络 ( HNN)解此问题时极易陷入局部极小的缺陷 ,并且收敛速度更快 .另外我们还用此法求解了属于 NP-完全问题的 K色图着色问题.

Artificial Neural Network with Transient Chaos for Four-Coloring Map Problems and K-Colorability Problems

Neural network and computational energy are presented for solving four-coloring map problem. Then, the four-coloring map problems are solved by a neural network model with transient chaos (TCNN) which have higher ability of quickly searching for the globally optimal solution because of its complicated chaotic dynamics. Numerical simulations of four-coloring map problem show that TCNN would not be stuck into local minima like the conventional Hopfield neural network (HNN) and always guaranteed that computational energy converged to the globally optimal solution. The TCNN is extended for solving $K$-colorability problem which is one of NP-complete problems.