复杂网络中简单路径搜索算法及其应用研究  

Research on Algorithm for Detecting Simple Path in Complex Network and Its Application

作　　者：刘夫云[1] 祁国宁[1] 车宏安[2] 

机构地区：[1]浙江大学现代制造工程研究所 [2]上海理工大学管理学院系统工程研究所,上海200093

出　　处：《系统工程理论与实践》2006年第4期9-13,84,共6页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(60374057;50575204)

摘　　要：将复杂网络理论应用于制造业中的产品族零部件关系领域,构建了产品族零部件关系网络.为进一步深入研究零部件关系网络,需要搜索零部件关系网络中的简单路径.提出了一种有向无环网络中任意两节点间所有简单路径的通用搜索算法.编制程序实现了该算法,对算法效率进行了分析.将算法应用于产品族零部件关系网络,对零部件关系网络进行了分析,对算法进行了验证.Applying complex network theory to parts relation field of product family in manufacturing, a kind of parts relation network of product family was constructed. In order to research parts relation network of product family deeply, it is necessary to detect simple paths in parts relation network. A universal algorithm for detecting all simple paths between any two nodes in weighted directed acyclic network was presented. The algorithm was realized through program, the efficiency of the algorithm was analyzed. Applying the algorithm to parts relation network, the network was analyzed and the algorithm was validated.

关 键 词：有向无环网络 复杂网络 简单路径 搜索算法 

分 类 号：N94[自然科学总论—系统科学] TP14[自动化与计算机技术—控制理论与控制工程]