Yang Fan, Qiu Zhi-liang, Li Zhi-bing, Liu Zeng-ji, Chang Yue-e. Research on Shared Path First Heuristic Algorithm[J]. Journal of Electronics & Information Technology, 2007, 29(3): 716-718. doi: 10.3724/SP.J.1146.2005.00874
Citation:
Yang Fan, Qiu Zhi-liang, Li Zhi-bing, Liu Zeng-ji, Chang Yue-e. Research on Shared Path First Heuristic Algorithm[J]. Journal of Electronics & Information Technology, 2007, 29(3): 716-718. doi: 10.3724/SP.J.1146.2005.00874
Yang Fan, Qiu Zhi-liang, Li Zhi-bing, Liu Zeng-ji, Chang Yue-e. Research on Shared Path First Heuristic Algorithm[J]. Journal of Electronics & Information Technology, 2007, 29(3): 716-718. doi: 10.3724/SP.J.1146.2005.00874
Citation:
Yang Fan, Qiu Zhi-liang, Li Zhi-bing, Liu Zeng-ji, Chang Yue-e. Research on Shared Path First Heuristic Algorithm[J]. Journal of Electronics & Information Technology, 2007, 29(3): 716-718. doi: 10.3724/SP.J.1146.2005.00874
The minimum cost multicast tree may boil down to Steiner tree problem which is NP-Complete. In multicast applications, heuristic algorithms are commonly used to calculate the suboptimal tree. In this paper, a new heuristic algorithm named Shared Path First Heuristic (SPFH) is proposed. In this algorithm, when destination nodes are joined into the multicast tree, two factors are considered. One is the distance between the destination nodes and the multicast tree, the other is the influence of earlier joined nodes to the later joined nodes. Among the nearest nodes to the constructing multicast tree, the node which can reduce the joining cost of other nodes are first chosen to join the tree. The simulation result shows that SPFH achieves the preferable performance.
[1] Karp R M. Reducibility among combinatorial problems[A]. In Miller and Thatcher(Eds), Complexity of Computer Computations[C]. New York, Plenum Press, 1972: 85-103. [2] Pawel Winter. Steiner problem in networks: A survey[J].Networks.1987, 17:129-167 [3] 余燕平. 组播路由算法的研究[D]. [博士论文]. 浙江: 浙江大学, 2002年11月. [4] Rayward-Smith V J and Clare A. On finding steiner vertices[J].Networks.1986, 16:283-294 [5] Vob S. Steiners problem in graphs: Heuristic methods. Discrete Applied Mathematics, 1992, 40(1): 43-72.