求解NP难问题的邻域搜索方法.doc

求解NP难问题的邻域搜索方法Feb.,20052005年2月湖北大学***()湖北大学数学与计算机科学学院,武汉,430062【摘要】本文先通过经典的旅行商问题引出了NP难问题的概念,然后分析求解该类问题的一种通用邻域搜索方法。【关键词】难问题;邻域搜索;TSPNP()【中图分类号】16【文献标识码】301【文章编号】1009-0444200501-0080-02TPA()一、旅行商问题及难问题,将n个城市的任意排列看作一法就是穷举搜索TSPNP(旅行商问题,个有序表,它决定了所访问的城市的顺序,旅行商TravelingSalesmanProblem)简称是一个著名的组合优化问题,该问题从某个城市出发,然后历经所有城市直至到出发TSP易于描述难于解决。假设有个城市,每对城市间城市,每个有序表都对应一个路径长度总耗费,如n()的距离已经给定,要求旅行商以最短路径访问所上例中,,,就是一个有序表,其耗费c1c2c3c4cost()()()()有的城市一次且仅一次并回到出发地,图1给出=,+,+,+,=28,dc1c2dc2c3dc3c4dc4c1个城市的共有多少个不同的有序表呢?由了4个城市的图中每对城市到的距离,nTSPTSPcicj)()(等于到的距离,即,=,,现要求于每一条路径可能用2种不同表示方法,而个cjcidcicjdcjcinn城市排列数为因此搜索空间大小为||=!,旅行商从4个城市中的某个城市出发访问其余所nS(()有城市一次后回到出发地,使得总行程最短。!ƒ2=-1!ƒ2。穷举搜索算法就是计算nnnn)-1!2个不同的有序表的耗费,其中最小耗费ƒ对应的旅行路经就是的解。一个著名难题似TSP乎就这样如此容易的解决了,但是穷举搜索致命的弱点是解空间大得让人无法臵信,当问题规模4时,可能解大约为||?118×10,=20=10nSn1662时,||?10,而时||?10,而对如此巨=50SnS图1大的解空间,即使使用当今世界上最快的计算机下面用形式化语言描述已知有穷个城:TSP在100万年内也无法得到最优解。一般而言,我们将可由多项式时间算法求解市的集合,,,}及其中任意两个城市={的问题看作是易处理的问题,通常称为问题,P))()((之间的距离i,j,且i,j=j,i,1??i而将需要超多项式时间才能求解的问题看作是难使得?要求一组城市序列<,,,>,jnckckck12n处理的问题,通常称为难问题,上述的NPTSP,是1,2,,的臵换且满足k1,k2,knnmin显然是一个难问题。由于难问题的搜索NPNPn-1空间成指数爆炸式扩大,因此求解难问题的NP()())(k,k+k,k。?ii+1n1i=1精确算法如穷举搜索只具有理论可计算性,而不如何求解最直接同时也是最精确的方?TSPΞ[收稿日期]2004-08-29()[作者简介]陈昊1977—,男,湖北大学数计学院教师,华中科技大学计算机学院硕士。〃80〃具有现实可计算性,现实生活中很多需要解决的所示,如果邻域中最短路径′比更好,则用′TTT替换反复进行邻域搜索,直到邻域中找不到比,问题都是难度的,如装填问题、覆盖问题