图同构问题决策神经网络模型.docVIP

图同构问题的决策神经网络模型本文意建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型在过去建立求解图的同构问题人工神经网络模型的基础上提出了一种新的用于图的同构问题的人工神经网络模型。该模型中增加了一个自然的约束条件，加快了运算速度。图同构决策神经网络TP301 The decision-making neural networks model for solving the graph isomorphism problem NAN Jin-Hua1) QI Huan1) 1) (Department of Control Science and Engineering，Huazhong University of Science and Technology，Wuhan 430074) Abstract The graph isomorphism problem is to study the relationship between two graphs which seem to be different, but essentially identical. This problem can be widely used in the system modeling, circuit wiring and many other issues. Therefore, this paper is aimed to establish a kind of neural networks model that are of local-connection, simulation human’s decision-making thinking, and also can be applied to solve the optimization for information. On this basis, we use a natural constraint in this model in order to speed up the operations, and then a new artificial neural network model is proposed to solve the graph isomorphism problem. Keywords Graph; Isomorphism; Decision-making; Neural networks model 1引言图的同构问题不仅是数学，特别是图论自身学科研究中的一个核心内容，而且具有良好的应用背景，在工程技术领域，特别是大系统建模、电路设计、机械设计、模式识别以及系统建模中有着广泛的应用。对于系统建模，如果能够证明需建模型与已知模型同构，则可以节省大量人力物力财力。多数学者认为图的同构判定问题属于NP-完全问题。但至今没有定论，即它究竟是问题还是NP问题？目前关于图的同构问题的判定性算法不少，有诸如经典判定算法对在实际工程中有着广泛应用的图的拟同构问题算法 [、进化计算方法[]、人工神经网络求解算法[] 以及必威体育精装版的DNA计算模型[]等在经典的图同构算法中，在此主要介绍两种算法，一种是所谓的矢量列表法，另一种是回溯算法。 研究图的同构问题，一个重要的环节是如何表示图的信息。在这个问题上，Comeil与Hffman等人曾引入“模块”这一概念来表示各个顶点及其邻接顶点信息。在此基础上Riaz提出一种有效的判定图同构问题的算法-矢量列表法，即把各顶点所代表的信息用模块表示，所有模块组合在一起构成矢量列表。设计算法依次比较各模块，最终得到同构信息。并在此基础上建立了图同构的矢量列表法。图同构的回溯算法是一种利用K-算子表示图结构，然后通过比对序列求解图同构映射的方法。K-算子这一概念最初由Kride等人提出，文献对这一算法进行深入的探讨改进对这一方法进行了系统的论述，并给出了适合计算机求解的算法。虽然通过仿真结果证明了这种回溯算法的可行性，但是要严格地给出时间复杂度估计不是很容易的事情，尽管如此，这种试图从图的结构上来判定同构性的思想无疑是值得借鉴的，它通过引入算子，把给定图表示成字符串的形式，然后通过回溯模式识别，逐步求可能的同构序列，最终得到两图是否同构。遗传算法由John Holland等人于20世纪60年代末提出，模拟生化机制进行优化计算。图的同构问题稍加扩充，引入成具有一定应用背景的所谓的拟同构的概念。当两个图相近程度达到要求误差范围之内时，称两个图为拟同构图的拟同构的一个很重要的应用就是在模式识别中，通常把事物的特征及其相互作用表示成赋权图。该算法把一个图同构的判定问题分解在GA中进行求解。通过引入初始匹配