Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (12): 45-46.

• 理论研究 • Previous Articles     Next Articles

Study of window ant colony algorithm of narrow TSP

QIN Shu,WANG Jin-biao   

  1. Computer Science and Technology College,Civil Aviation University of China,Tianjin 300300,China
  • Received:2007-08-07 Revised:2007-11-19 Online:2008-04-21 Published:2008-04-21
  • Contact: QIN Shu

狭义TSP小窗口蚁群算法研究

秦 姝,王锦彪   

  1. 中国民航大学 计算机科学与技术学院,天津 300300
  • 通讯作者: 秦 姝

Abstract: The algorithm of Ant-Window[1] is one of the important improvement of the study about ant colony algorithm.This paper defines big window and small window and points that the classical ant colony algorithm is the ant colony algorithm of big window essentially.The study demonstrates that the statistic average of Ant-Window’s diameter is 5 and that makes calculation complexity of narrow TSP problem down form 1/2(n-1)! to 5n-1.

Key words: Ant-Window, diameter of Ant-Window, big window, small window, narrow TSP

摘要: 蚁窗[1]算法是蚁群算法研究的重要进展之一。定义了大窗口和小窗口,指出经典蚁群算法实质上是大窗口蚁窗算法。研究表明,小窗口蚁窗直径的下限统计平均值约为5,使狭义TSP问题的计算复杂性由1/2(n-1)!降为5n-1

关键词: 蚁窗, 蚁窗直径, 大窗口, 小窗口, 狭义TSP