用启发式算法求解最短路径问题

提出了一种带有启发信息的邻接表结点存储结构模型,给出了结点间权值计算的具体评判函数,依据评判函数值优化邻接表中节点的相对位置.基于最短路径问题提出了带有启发信息的遗传算法思想,将启发信息加入到了初始种群生成过程中,提出了新的交叉方法.通过模拟仿真得到了算法的性能参数,并将本文算法和Dijkstra算法进行比较,结果表明...

Problem for shortest path problem based on heuristic algorithm

An adjacency list storage model with heuristic information is proposed. An evaluation function to calculate the weight among nodes was derived. The relative position of the node in the adjacency list was optimized using the evaluation function. The process of initial population with heuristic information and chromosome coding, and the strategy of dynamic adjustment of the fitness function were presented. The main performance parameters were obtained by simulation, and the proposed algorithm was compared with the Dijkstra algorithm. Experiment results show that the proposed algorithm possesses higher efficiency when solving the optimization problem of shortest path with high spatial complexity.