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

《图同构问题的决策神经网络模型》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、《计算机学报》2010年第2期，2010，33（2）图同构问题的决策神经网络模型南晋华，齐欢(华中科技大学控制科学与工程系武汉430074)摘要图的同构问题是研究两个图之间相互关系范畴。这对图表面上似乎不同，但本质上完全相同。由于图的同构问题在以系统建模、电路布线等众多问题中有直接的应用，因而，吸引了不少的学者从事这方面的研究。本文意在建立一种局域连接的、模拟人脑决策思维模式的、可用于优化信息处理的神经网络模型。文中在过去建立求解图的同构问题人工神经网络模型的基础上，拟应用人脑决策局域化的思想，提出了一种新的用于图的同构问题的人工神经网络模型。该模型中增加了一

2、个自然的约束条件，加快了运算速度。关键词图；同构；决策；神经网络中图分类号TP301Thedecision-makingneuralnetworksmodelforsolvingthegraphisomorphismproblemNANJin-Hua1)QIHuan1)1)(DepartmentofControlScienceandEngineering，HuazhongUniversityofScienceandTechnology，Wuhan430074)AbstractThegraphisomorphismproblemistostudytherelat

3、ionshipbetweentwographswhichseemtobedifferent,butessentiallyidentical.Thisproblemcanbewidelyusedinthesystemmodeling,circuitwiringandmanyotherissues.Therefore,thispaperisaimedtoestablishakindofneuralnetworksmodelthatareoflocal-connection,simulationhuman’sdecision-makingthinking,andal

4、socanbeappliedtosolvetheoptimizationforinformation.Onthisbasis,weuseanaturalconstraintinthismodelinordertospeeduptheoperations,andthenanewartificialneuralnetworkmodelisproposedtosolvethegraphisomorphismproblem.KeywordsGraph;Isomorphism;Decision-making;Neuralnetworksmodel《计算机学报》2010年

5、第2期，2010，33（2）1引言图的同构问题不仅是数学，特别是图论自身学科研究中的一个核心内容，而且具有良好的应用背景，在工程技术领域，特别是大系统建模、电路设计、机械设计、模式识别以及系统建模中有着广泛的应用。对于系统建模，如果能够证明需建模型与已知模型同构，则可以节省大量人力物力财力。多数学者认为图的同构判定问题属于NP-完全问题。但至今没有定论，即它究竟是问题还是NP问题？目前关于图的同构问题的判定性算法不少，有诸如经典判定算法[1-8]、对在实际工程中有着广泛应用的图的拟同构问题算法[9-12]、进化计算方法[13]、人工神经网络求解算法[14-18

6、]以及最新的DNA计算模型[19-20]等。在经典的图同构算法中，在此主要介绍两种算法，一种是所谓的矢量列表法，另一种是回溯算法。《计算机学报》2010年第2期，2010，33（2）研究图的同构问题，一个重要的环节是如何表示图的信息。在这个问题上，Comeil与Hffman等人曾引入“模块”这一概念来表示各个顶点及其邻接顶点信息。在此基础上Riaz提出一种有效的判定图同构问题的算法-矢量列表法，即把各顶点所代表的信息用模块表示，所有模块组合在一起构成矢量列表。设计算法依次比较各模块，最终得到同构信息。并在此基础上建立了判定图同构的矢量列表法。图同构的回溯算法是

7、一种利用K-算子表示图结构，然后通过比对序列求解图同构映射的方法。K-算子这一概念最初由Kride等人提出，文献[11-12]对这一算法进行深入的探讨改进，并对这一方法进行了系统的论述，并给出了适合计算机求解的算法。虽然通过仿真结果证明了这种回溯算法的可行性，但是要严格地给出时间复杂度估计不是很容易的事情，尽管如此，这种试图从图的结构上来判定同构性的思想无疑是值得借鉴的，它通过引入算子，把给定图表示成字符串的形式，然后通过回溯模式识别，逐步求得可能的同构序列，最终得到两图是否同构。遗传算法由JohnHolland等人于20世纪60年代末提出，模拟生化机制进行优

8、化计算[21]。图的同构问题稍加扩充，