关于TSP的骨架算法综述
The Review of Backbone Algorithm about TSP
DOI: 10.12677/CSA.2013.38065, PDF, HTML, XML,  被引量 下载: 2,998  浏览: 9,731  国家自然科学基金支持
作者: 王锦彪, 马发民：中国民航大学计算机科学与技术学院，天津
关键词: TSP；骨架算法；大坑现象；TSP边识别；融合；TSP; Backbone Algorithm; The Hole Phenomenon; TSP Edge Recognition; Fusion
摘要: 当TSP的哈密顿回路计算算法研究止步于局部最优陷阱时，1995年Boese教授发现了大坑现象，使骨架算法悄然进入了TSP研究领域。骨架算法在TSP边识别方面正在取得进展。预言了骨架算法与脂肪算法相融合的必然趋势。
>When the Hamiltonian circuit calculation algorithms of TSP stopped at local optimum trap, professor Boese discovered the hole phenomenon in 1995, and made backbone algorithm into TSP research filed. The backbone algorithm in TSP edge recognition is making progress. The paper predicts that the fusion of backbone algorithm and fat algorithm is inevitable trend.
文章引用：王锦彪, 马发民. 关于TSP的骨架算法综述[J]. 计算机科学与应用, 2013, 3(8): 374-380. http://dx.doi.org/10.12677/CSA.2013.38065

参考文献

[1] Blum, H. (1967) A transformation for extracting new descriptors of shape. In: Walthen-Dunn, W., ed., Models for the Perception of Speech and Visual Form, Cambridge: M1T Press, 362-380.
[2] Ma, C.M. and Sonka, M. (1996) A fully parallel 3D thinning algorithm and its applications. Computer Vision and Image Un- derstanding, 64, 420-433.
[3] Pudney, C. (1998) Distance-ordered homotopic thinning: A ske- letonization algorithm for 3D digital images. Computer Vision and Image Understanding, 72, 404-413.
[4] 车武军, 杨勋年, 汪国昭 (2003) 动态骨架算法. 软件学报, 14, 818-823.
[5] Leymarie, F. and Levin, M.D. (1992) Simulating the grass fire transform using an active. Contour model. IEEE Transactions on Pattern Analysis and Machine Intelligence, 14, 56-75.
[6] Golland, P. and Grimson, W.E.L. (2000) Fixed topology skele- tons. Proceedings of the IEEE Computer Society Conference on Computer Vision and Pattern Recognition, 1, 10-17.
[7] Niblack, C.W., Gibbon, P.B. and Capson, D.W. (1992) Generat- ing skeletons and center lines from the distance transform. CVGIP: Graphical Models and Image Processing, 54, 420-437.
[8] Ge, Y. and Fitzpatrick, J.M. (1996) On the generation of skele- tons from discrete euclidean distance maps. IEEE Transactions on Pattern Analysis and Machine Intelligence, 18, 1055-1066.
[9] Bitter, I., Kaufman, A.E. and Sato, M. (2001) Penalized-distance volumetric skeleton algorithm. IEEE Transactions on Visualiza- tion and Computer Graphics, 7, 195-206.
[10] Zhou, Y. and Toga, A.W. (1999) Efficient skeletonization of volumetric objects. IEEE Transactions on Visualization and Computer Graphics, 5, 196-209.
[11] Choi, W.P., Lam, K.M. and Siu, W.C. (2003) Extraction of the euclidean skeleton based on a connectivity criterion. Pattern Recognition, 36, 721-729.
[12] 张琳波, 肖柏华, 王枫等 (2013) 图像内容表示模型综述. 计算机科学, 7, 1-8.
[13] Ogniewicz, R.L. and Kubler, O. (1995) Hierarchic Voronoi skeleton. Pattern Recognition, 28, 343-359.
[14] Reddy, J.M. and Turkiyyah, G.M. (1995) Computation of 3D skeletons using a generalized Delaunay triangulation technique. Computer Aided Design, 27, 677-694.
[15] Boese, K.D. (1995) Cost versus distance in the traveling sales- man problem. Technical Report CSD-950018.
[16] Monasson, R., Zecchina, R., Kirkpatrick, S., et al. (1998) Deter- mining computational complexity for characte-ristic phase transi- tion. Nature, 400, 133-137.
[17] Zhang, W.X. (2004) Configuration landscape analysis and back- bone guided local search: Part I: Satisifiability and maximum satisfiability. Artificial Intelligence, 158, 1-26.
[18] Dubois, O. and Seymour, P.A. (2001) Backbone-search heuristic for efficient solving of hard 3-SAT formula. Proceedings of the 17th International Joint Conference on Artificial Intelligence (IJCAI-01), San Francisco: Morgan Kaufmann Publishers, 248- 253.
[19] Valnir, F.J. (2006) Backbone guided dynamic local search for propositional satisfiability. Proceedings of the 9th International Symposium on Artificial Intelligence and Mathematics (AI&Math- 06). New York: Springer, 100-108.
[20] Zou, P., Zhou, Z., Chen, G.L., et al. (2005) Approximate-back- bone guided fast ant algorithms to QAP. Journal of Statistical Software, 16, 1691-1698.
[21] Schneider, J. (2003) Searching for backbones: A high-perfor- mance parallel algorithm for solving combinatorial optimization problems. Future Generation Computer Systems, 19, 121-131.
[22] 邹鹏, 周智, 陈国良等 (2003) 求解TSP问题的多级归约算法. 软件学报, 1, 35-42.
[23] Zhang, W.X. (2004) Phase transition and backbones of the asymmetric traveling salesman problem. Journal of Artificial Intelligence Research, 21, 471-497.
[24] Zhang, W.X. and Looks, M. (2005) A novel local search algo- rithm for the traveling salesman problem that exploit backbones. Proceedings of the 19th International Joint Conference on Arti- ficial Intelligence, 343-350
[25] Wang, J.B. and Wang, K.C. (2010) Union-intersection any sys- tem. 5th International 2010 Conference on Bio-Inspired Com- puting: Theories and Applications, 364-371.
[26] Sharlee, C.and Zhang, W.X. (2002) Search for backbones and fat: A limit-crossing approach with application. Proceedings of the 18th National Conference on Artificial Intelligence (AAAI 2002), Menlo Park: AAAI Press, 707-712.
[27] 江贺, 胡燕, 李强, 于红 (2009) TSP问题的脂肪计算复杂性与启发式算法设计. 软件学报, 9, 2344-2351.