Path-finding algorithm based on node degree and infinite incipient percolation cluster

Abstract

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

摘要： 在复杂网络的理论基础上，基于节点度和最小支撑聚类构造了一个阻抗函数，利用该阻抗函数提出了一种可应用于城市路网的启发式路径搜索算法，该算法搜索到的路径可以在总路径长度接近理论最短的同时，通过避免取径可能发生拥堵的路段，从而降低遭遇拥堵情况的风险；根据该算法编程实现了一个简易导航程序，通过实际路网数据验证了算法的有效性。

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

ZHOU Yang, FAN Jianhua, WANG Zhiqin, ZHANG Jiehua. Path-finding algorithm based on node degree and infinite incipient percolation cluster[J]. Computer Engineering and Applications, 2013, 49(9): 164-167.

周阳，樊建华，王志芹，张洁华. 基于节点度和最小支撑聚类的路径搜索算法[J]. 计算机工程与应用, 2013, 49(9): 164-167.

[1]	MA Xianghua, ZHANG Qian. Research on Improved Ant Colony Algorithm in Robots Path Planning [J]. Computer Engineering and Applications, 2021, 57(5): 210-215.
[2]	MA Manfu, GUO Chenbiao, LI Yong, ZHANG Zhongying, ZHANG Qiang, WANG Changqing. Research on Heterogeneity of Attention Flow Network Based on Structural Entropy [J]. Computer Engineering and Applications, 2021, 57(23): 98-105.
[3]	REN Chunhui, LIU Sheng, ZHANG Weikang, ZHANG Weiwei. Optimization and Application of Cauchy Mutation Camel Algorithm [J]. Computer Engineering and Applications, 2021, 57(21): 87-94.
[4]	SHI Yuqiang, TIAN Yongzheng, ZHANG Yuqi, SHI Xiaoqiu. Solving FJSP by Multi-population Genetic Algorithms with Complex Network Structure [J]. Computer Engineering and Applications, 2021, 57(2): 257-266.
[5]	LI Jinhai, HE Youshi, ZHANG Peng. Research of Group Recommendation Based on Contextual Semantics Reasoning and Social Network [J]. Computer Engineering and Applications, 2021, 57(18): 163-171.
[6]	ZHANG Chengling, LI Jinjin, LIN Yidong. Attribute Reduction in Formal Contexts Based on OE-Concept Lattices [J]. Computer Engineering and Applications, 2021, 57(15): 82-89.
[7]	CHEN Jie, CHENG Sheng, XU Meng, SHI Haobin. Visual Multiple Attribute Decision-Making Method for Medical Assistant Diagnosis [J]. Computer Engineering and Applications, 2020, 56(8): 249-255.
[8]	WANG An, GU Yijun. Nodes Importance Ranking Method Based on Community Detection [J]. Computer Engineering and Applications, 2020, 56(8): 42-48.
[9]	XIAO Chenglong, NIE Ziyang, WANG Shanshan. Correlation Heuristics Based on ParetoHeu and Instantiation Failure Statistics [J]. Computer Engineering and Applications, 2020, 56(5): 57-64.
[10]	ZHAO Liang, ZHU Zhengyu. Overlapping Community Discovery Algorithm with K-Kernel Iteration Factor [J]. Computer Engineering and Applications, 2020, 56(3): 61-67.
[11]	MOU En, ZHANG Xianyong, YAO Yuesong, DENG Qie. Class-Specific Attribute Reduct and Its Heuristic Algorithm of Neighborhood Approximation Condition-Entropy [J]. Computer Engineering and Applications, 2020, 56(24): 175-180.
[12]	MENG Xin, YANG Qin, HAO Tingting, ZHANG Jie, CAO Cejun. Optimized Combination of Picking Path in Different Distributions and Algorithms [J]. Computer Engineering and Applications, 2020, 56(23): 229-236.
[13]	LI Yali, WANG Shuqin, CHEN Qianru, WANG Xiaogang. Comparative Study of Several New Swarm Intelligence Optimization Algorithms [J]. Computer Engineering and Applications, 2020, 56(22): 1-12.
[14]	ZHANG Xiaoli, YANG Yaxin, XIE Yongcheng. Application of Improved Ant Colony Algorithm in Robot Path Planning [J]. Computer Engineering and Applications, 2020, 56(2): 29-34.
[15]	DU Qing, XIN Shouting, LEI Xinyu, YU Haitao. Seizures Identification from EEG Signals Based on Functional Brain Network and TSK Fuzzy System [J]. Computer Engineering and Applications, 2020, 56(2): 133-140.

Path-finding algorithm based on node degree and infinite incipient percolation cluster

基于节点度和最小支撑聚类的路径搜索算法

PDF

Knowledge

Abstract

Cite this article

share this article

References

Related Articles 15

Recommended Articles

Metrics