网络的粒度存储及在路径搜索中的应用

NETWORK GRANULAR STORAGE AND ITS APPLICATION TO PATH FINDING

网络路径搜索是图论中的经典问题,对于大规模网络的最短路径搜索问题是人工智能领域研究热点问题。应用粒计算方法求解问题的思路实现网络的粒度存储,讨论不同基本类型的网络粒化,提出分层递阶商空间链实现网络的粒度存储。就大规模网络,提出社团作为基本粒的网络快速分割方法,实现网络的粒度存储。并将网络的粒度存储的分层递阶商空间链信息作为路径搜索前的预处理工作,提出一种启发式路径搜索方法。通过实验与启发式算法进行对比,验证了该算法的有效性。

Network path finding is a classical problem in the graph theory. For large scale networks, the shortest path finding problem is a hot issue for researching in the AI field. The thesis applies a problem solving idea of granular computing methods to realize network granular storage, discusses different fundamental types of network granulation, and proposes a hierarchical quotient space chain to realize network grantdar storage. For large scale networks, a network quick partitioning method is put forward that regards communities as basic granules to realize network granular storage. In addition, the paper regards network granular storage hierarchical quotient space chain information as preprocessing work before path finding and proposes a heuristic path finding method. Through comparison between experiments and heuristic path finding methods, the effectiveness of the proposed algorithm is validated.