A*算法在TSP中的应用

下载PDF

导出

摘要旅行商问题(TSP)是组合优化中最典型的NP完全问题之一。目前有不少用于求解旅行商问题的算法,可将这些算法分为智能计算和盲目搜索两种,这些算法均有自己的优缺点,分析了这些算法在求解TSP时的不足。从理论上分析了影响算法性能的因素,对A*算法的数据结构、排序方法和估价函数进行改进从而得到一种新的算法。通过对测试数据的比较,表明算法的效率得到很大的提高。

作者郭强

机构地区郑州大学西亚斯国际学院网络管理中心

出处《黑龙江科技信息》 2013年第28期167-167,56,共2页 Heilongjiang Science and Technology Information

关键词 A^＊算法 TSP 最优路径 DIJKSTRA HOPFIELD

分类号 TP18 [自动化与计算机技术—控制理论与控制工程]

引文网络
相关文献

参考文献11

1王海梅,周献中.一种限制搜索区域的最短路径改进算法[J].南京理工大学学报,2009,33(5):638-642. 被引量：20
2陈萍,郭金锋.对Hopfield神经网络求解TSP的研究[J].北京邮电大学学报,1999,22(2):58-61. 被引量：14
3程明,刘琴.神经网络TSP问题仿真分析[J].郑州大学学报（理学版）,2004,36(1):45-48. 被引量：5
4张林广,方金云,申排伟.基于配对堆改进的Dijkstra算法[J].中国图象图形学报,2007,12(5):922-926. 被引量：16
5P.E.Hart,N.J.Nilsson,B.Raphael. A formal Basis for the heuristic determination of Minimum cost paths in graphs[J].IEEE Transactions,1968,(02):100-107. 被引量：1
6姜国均.Hopfield网络解TSP的改进算法[J].浙江大学学报（理学版）,2001,28(2):160-163. 被引量：13
7陆锋,卢冬梅,崔伟宏.交通网络限制搜索区域时间最短路径算法[J].中国图象图形学报（A辑）,1999,4(10):849-853. 被引量：74
8张宇翔,黄力宇.Hopfield网络求解TSP两种改进算法的仿真研究[J].电子设计工程,2009,17(10):119-121. 被引量：9
9王凌,郑大钟.TSP及其基于Hopfield网络优化的研究[J].控制与决策,1999,14(6):669-674. 被引量：27
10赵建明,姚念民.Hopfield网络求解旅行商问题有效性的研究[J].科学技术与工程,2009,9(2):437-440. 被引量：2

二级参考文献46

1姚亚锋,方贤进,陈代梅.Dijkstra算法的一种高效率实现[J].计算机与数字工程,2007,35(7):21-22. 被引量：7
2孙守宇,郑君里.Hopfield网络求解TSP的一种改进算法和理论证明[J].电子学报,1995,23(1):73-78. 被引量：45
3徐凤生.求最短路径的新算法[J].计算机工程与科学,2006,28(2):83-85. 被引量：15
4陈行星,崔伟宏.城市快速反应系统实验研究[J].环境遥感,1996,11(3):227-233. 被引量：10
5王海梅,周献中.网络系统中的最短路径分析及其应用研究[J].兵工学报,2006,27(3):515-518. 被引量：15
6杨秀梅,陈洪亮,董得义.利用Hopfield神经网络求解旅行商问题研究[J].微型电脑应用,2006,22(11):1-3. 被引量：8
7张林广,方金云,申排伟.基于配对堆改进的Dijkstra算法[J].中国图象图形学报,2007,12(5):922-926. 被引量：16
8李政.基于存储结构的Dijkstra算法优化[J].桂林师范高等专科学校学报,2007,21(2):129-131. 被引量：4
9靳藩范俊波等.神经网络和神经计算机[M].西安:西安交通大学出版社,1991.. 被引量：3
10Hart P, Nilsson N, Paphael B. A formal basis for the heuristic determination of minimum cost path [ J ]. IEEE Transactions on Systems Science and Cybernetics, 1968, 4(2) : 100 -107. 被引量：1

共引文献188

1王飞,袁涛,王蒙.一种联通网的随机生成方法在改进Floyd算法中的研究与实现[J].玉溪师范学院学报,2020(3):78-85.
2杨辉,徐德天.墙体模板台车在倒虹吸施工中的应用[J].中国西部科技,2007,6(17):9-10.
3马东岭.城市公交网络的最短路径算法研究[J].科技信息,2008(26):15-16. 被引量：3
4王秀利,吴惕华.工业生产调度优化问题的研究[J].燕山大学学报,2001,25(z1):160-165.
5李国富,叶飞帆.具有动态阈值的人工神经网络[J].宁波大学学报（理工版）,2001,14(3):33-36.
6崔铁军,许志海,夏启兵.数字地图与AVLN系统[J].信息工程大学学报,2000,1(3):9-14. 被引量：1
7杜立智,张晓龙.一个高效的3SAT到Hamilton环转化方法[J].南京理工大学学报,2013,37(4):506-510. 被引量：1
8尉斌,胡斌,孟巍.近邻策略Hopfield神经网络的TSP求解[J].计算机工程,2011,37(S1):220-222.
9SHAW ShihLung.Modeling of taxi drivers’ experience for routing applications[J].Science China(Technological Sciences),2010,53(S1):44-51. 被引量：2
10于德新,杨兆升,高鹏.动态限制搜索区域的带约束K则最优路径算法[J].吉林大学学报（工学版）,2009,39(S2):172-176. 被引量：5

1樊莉,孙继银,王勇.人工智能中的A^＊算法应用及编程[J].微机发展,2003,13(5):33-35. 被引量：26
2何怡刚,邱光源.HopfieldA/D转换器研究综述[J].现代通信技术,1994(4):19-23.
3郑金成,帅建伟,王仁智,陈振湘.Hopfield神经网络的存储容量[J].自然杂志,1996,18(4):245-246.
4贾磊,孙优贤.神经网络与自动控制[J].山东轻工业学院学报（自然科学版）,1991,5(2):1-7.
5张晓玲.经典Dijkstra算法及其改进的分析比较[J].科技信息,2009(27):170-171. 被引量：4
6张海涛,程荫杭.基于A*算法的全局路径搜索[J].微计算机信息,2007,23(17):238-239. 被引量：38
7王琳琳,丁尧.无线网络下的AGV路径规划[J].自动化应用,2017(3):59-61.
8田中.人工智能中搜索策略的探讨[J].福建电脑,2004,20(8):30-31. 被引量：3
9叶剑平.HOPFIELD神经网络模型的几种学习算法[J].模式识别与人工智能,1992,5(3):215-220. 被引量：2
10梁学斌.离散Hopfield神经网络的统一描述[J].安徽大学学报（自然科学版）,1993,17(2):6-10.

黑龙江科技信息

2013年第28期

浏览历史

内容加载中请稍等...

A*算法在TSP中的应用

参考文献11

二级参考文献46

共引文献188

相关作者

相关机构

相关主题

浏览历史