关键词: 路径搜索, 启发式, 复杂网络, 最小支撑聚类

Abstract: According to the complex network theory, an impedance function based on node degree and infinite incipient percolation cluster and a path-finding heuristic algorithm for urban road network is presented. The heuristic algorithm proposed in this paper can find a path which can avoid the roads where congestion may occur so that the risk of encountering congestion can be reduced, while the total length of the path is close to the theoretical shortest. The algorithm is utilized to implement a simple navigation program and the feasibility of the algorithm is tested through a group of actual road network data.

Key words: path-finding, heuristic, complex network, infinite incipient percolation cluster