神经网络在平面布线 中的应 用

Hopfield给出N个节点完全图K，中求最短Hamilton圈的神经网络方法，若将无自环图看做K，的子图，不难求出Hamilton图的Hamilton圈.不过当节点数增多时，解神经网络动态方程常得到次优解，和Hamilton圈差一两条边，称为准Hamilton圈.利用Hamilton圈和准Hamilton圈，可以画出一个平面图的平面化图，或者将一个非平面图分解为平面化子图，以便平面布线.

The Application of Neural Netuorks in Plane Routing

Hopfield gives a method for finding the shortest Hamilton cycle using neural networks in N node complete graph Kn. In non-selfloop graph is regarded as the subgraph of KN,it will be easy to Obtain Hamilton cycle of Hamilton graph. But when nodes increase,the solution to the equations of motion of meural networks is frequently under-optimized. Compared with Hamilton cycle there are one or two edges' difference,which is called siwhar Hamilton cycle. Making use of the cycles of Hamilton and similar Hamilton, plane graph can be drawn,on a non-plane graph may be decomposed into subgraph of being plane so that the panne routing is easy.