杜瀚玉人工智能讲义.docx
- 文档编号:4832307
- 上传时间:2023-05-07
- 格式:DOCX
- 页数:28
- 大小:136.91KB
杜瀚玉人工智能讲义.docx
《杜瀚玉人工智能讲义.docx》由会员分享,可在线阅读,更多相关《杜瀚玉人工智能讲义.docx(28页珍藏版)》请在冰点文库上搜索。
杜瀚玉人工智能讲义
哈尔滨师范大学
课程论文
课程名称
人工智能
任课教师
赵丽
题
目
旅行商问题的求解方法
姓
名
杜瀚玉
学
号
2013040385
学
院
计算机科学与信息工程学院
论文评语(由任课教师填写):
成绩
旅行商问题的求解方法
杜瀚玉
摘要:
旅行商问题(TSP问题)时是指旅行家要旅行n个城市然后回到出发城市,要求各个城市经历且仅经历一次,并要求所走的路程最短。
该问题又称为货郎担问题、邮递员问题、售货员问题,是图问题中最广为人知的问题。
本文主要介绍用蛮力法、动态规划法、贪心法
和分支限界法求解TSP问题,其中重点讨论动态规划法和贪心法,并给出相应求解程序。
关键词:
旅行商问题;动态规划法;贪心法;分支限界法
旅行商问题(TSP)是组合优化问题中典型的NP-完全问题,是许多领域内复杂工程优化
问题的抽象形式。
研究TSP的求解方法对解决复杂工程优化问题具有重要的参考价值。
关于
TSP的完全有效的算法目前尚未找到,这促使人们长期以来不断地探索并积累了大量的算法。
归纳起来,目前主要算法可分成传统优化算法和现代优化算法。
在传统优化算法中又可分为:
最优解算法和近似方法。
最优解算法虽然可以得到精确解,但计算时间无法忍受,因此就产
生了各种近似方法,这些近似算法虽然可以较快地求得接近最优解的可行解,但其接近最优
解的程度不能令人满意。
但限于所学知识和时间限制,本文重点只讨论传统优化算法中的动态规划法、贪心法和分支限界法,并对蛮力法做简单介绍,用以比较。
需求分析
旅行商问题(TravelingSalesmanProblem,TSF)又译为旅行推销员问题、货郎担问
题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过
所有给定的需求点之后,最后再回到原点的最小路径成本。
最早的旅行商问题的数学规划是由Dantzig(1959)等人提出。
“旅行商问题”常被称为“旅行推销员问题”,是指一名推销员要拜访多个地点时,如
何找到在拜访每个地TSP问题点一次后再回到起点的最短路径。
规则虽然简单,但在地点数
目增多后求解却极为复杂。
以42个地点为例,如果要列举所有路径后再确定最佳行程,那
么总路径数量之大,几乎难以计算出来。
多年来全球数学家绞尽脑汁,试图找到一个高效的算法TSP问题在物流中的描述是对应一个物流配送公司,欲将n个客户的订货沿最短路线全
部送到。
如何确定最短路线。
旅行商问题要从图G的所有周游路线中求取最小成本的周游路线,而从初始点出发的周
游路线一共有(n-1)!
条,即等于除初始结点外的n-1个结点的排列数,因此旅行商问题是一个排列问题。
排列问题比子集合的选择问题通常要难于求解得多,这是因为n个物体有n!
种排列,只有个子集合(n!
>0())。
通过枚举(n-1)!
条周游路线,从中找出一条具有最小成
本的周游路线的算法,其计算时间显然为O(n!
)。
总体设计
1最早的旅行商问题的数学规划是由Dantzig(1959)等人提出,TSP问题在物流中的描述是对应一个物流配送公司,欲将n个客户的订货沿最短路线全部送到。
如何确定最短路线。
2、TSP问题最简单的求解方法是枚举法。
它的解是多维的、多局部极值的、趋于无穷
大的复杂解的空间,搜索空间是n个点的所有排列的集合,大小为(n-1)。
可以形象地把解空间看成是一个无穷大的丘陵地带,各山峰或山谷的高度即是问题的极值。
求解TSP,则是
在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。
3、旅行商问题字面上的理解是:
有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的具有最短路程的环路。
4、TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋
棋盘中的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点。
TSP由美国RAND公司于1948年引入,该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名
且流行的问题。
蜜蜂试验
1、英国伦敦大学皇家霍洛韦学院等机构研究人员报告说,小蜜蜂显示出了轻而易举破
解这个问题的能力。
他们利用人工控制的假花进行了实验,结果显示不管怎样改变花的位置,
蜜蜂在稍加探索后,很快就可以找到在不同花朵间飞行的最短路径。
这可是首次发现能解决
这个问题的动物,研究报告即将发表在《美国博物学家》杂志上。
2、进行研究的奈杰尔•雷恩博士说,蜜蜂每天都要在蜂巢和花朵间飞来飞去,为了采蜜而在不同花朵间飞行是一件很耗精力的事情,因此实际上蜜蜂每天都在解决“旅行商问
题”。
尽管蜜蜂的大脑只有草籽那么大,也没有电脑的帮助,但它已经进化出了一套很好的
解决方案,如果能理解蜜蜂怎样做到这一点,对人类的生产、生活将有很大帮助。
1.蛮力法
蛮力法的设计思想:
蛮力法所依赖的基本技术是扫描技术,即采用一定的策略将待求解
问题的所有元素一次处理一次,从而找出问题的解。
一次处理所有元素的是蛮力法的关键,为了避免陷入重复试探,应保证处理过的元素不再被处理。
在基本的数据结构中,一次处理
每个元素的方法是遍历。
2.动态规划法
动态规划法设计思想:
动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问
题对应决策过程的一个阶段,一般来说,子问题的重叠关系表现在对给定问题求解的递推关系(也就是动态规划函数)中,将子问题的解求解一次并填入表中,当需要再次求解此子问
题时,可以通过查表获得该子问题的解而不用再次求解,从而避免了大量重复计算。
旅行商问题(TSP问题)其实就是一个最优化问题,这类问题会有多种可能的解,
每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解•若存在若干个取最优值
的解的话,它只取其中的一个•在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解
一次,并将结果保存起来,避免每次碰到时都要重复计算•
关于旅行商的问题,状态变量是gk(i,S),表示从0出发经过k个城市到达i的最短距离,S为包含k个城市的可能集合,动态规划的递推关系为:
gk(i,S)=min[gk-1(j,S\{j})+dji]j属于S,dji表示j-i的距离•
或者我们可以用:
f(S,v)表示从v出发,经过S中每个城市一次且一次,最短的路
径.f(S,v)=min{f(S-{u},u)+dist(v,u)}uinS
f(V,1)即为所求
3.贪心法
贪心法:
贪心法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,而且一
旦做出了选择,不管将来有什么结果,这个选择都不会改变。
换言之,贪心法并不是从整体
最优考虑,它所做出的选择只是在某种意义上的局部最优。
这种局部最优选择并不总能获得
整体最优解,但通常能获得近似最优解。
从问题的某一个初始解触发逐步逼近给定的目标,以尽可能快地求得更好的解。
当达到某算法中的某一步不能再继续前进时,算法停止。
大致步骤如下:
1)建立数学模型来描述问题;
2)把求解的问题分成若干个子问题
3)对每一个子问题求解,得到子问题的局部最优解
4)把子问题的局部最优解合成原问题的一个解
贪心算法没有固定的算法框架,算法设计的关键是贪心策略的选择,而贪心策略
适用的前提是:
局部最优策略能导致产生全局最优解。
从问题的某一初始解出发;
while(能朝给定总目标前进一步)
{
利用可行的决策,求出可行解的一个解元素;
}
由所有解元素组合成问题的一个可行解;
4.分支限界法
分支限界法:
假设求解最大化问题,解向量为X(Xi,X2,…,Xn),其中,Xi的取值范围为
某个有穷集合S,|Si|ri(1in)。
在使用分支限界法搜索问题的解空间树时,首先根据限界函数估算目标函数的界[down,up],然后从根结点出发,扩展根结点的ri个孩子结点,从而构成分量X1的r1种可能的取值方式。
对这r1个孩子结点分别估算可能取得的目标函数值bound(xj,其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于bound(xj,
也就是部分解应满足:
bound(X1)bound(X1,X2)...bound(X1,X2,...,Xk)...bound(X1,X2,...,Xn)
三、实现方法
1.蛮力法
用蛮力法解决TSP问题,可以找出所有可能的旅行路线,从中选取路径长度最短的简单
回路。
如对于图1,我们求解过程如下:
(1)
路径
1->2->3->4->1;路径长度
18;
(2)
路径
1->2->4->3->1;路径长度
11;
(3)
路径
1->3->2->4->1;路径长度
23;
(4)
路径
1->3->4->2->1;路径长度
11;
(5)
路径
1->4->2->3->1;路径长度
18;
(6)
路径
1->4->3->2->1;路径长度
18;
从中,我们可以知道,路径
(2)和
(4)路径长度最短。
我们还应注意到,图1中,有3对不同的路径,对每对路径来说,不同只是路径的方向,因此,可以将这个数量减半,则可能的解有(n-1)!
/2个。
这是一个非常大的数,随着n
的增长,TSP问题的可能解也在迅速增长。
如:
一个10城市的TSP问题有大约有180,000个可能解。
一个20城市的TSP问题有大约有60,000,000,000,000,000个可能解。
一个50城市的TSP问题有大约1062个可能解,而一个行星上也只有1021升水。
因此,我们可以知道用蛮力法求解TSP问题,只能解决问题规模很小的实例。
2.动态规划法
假设从顶点i出发,令d(i,V)表示从顶点i出发经过V'中各个顶点一次且仅一次,最
I
后回到出发点i的最短路径长度,开始时,VVI,于是,tsp问题的动态规划函数
为:
d(i,V')mincikd(k,Vk)(kV')
d(k,)cki(ki)
算法讨论:
(1)for(i=1;i d[i][0]=c[i][0]; 2 n-1-1;j++) for(i=1;i if(子集V[j]中不包含i) 对V[j]中的每个元素k,计算V[m]==V[j]-k;d[i][j]=min(c[i][k]+d[k][m]); n-1n-1 (3)对V[2-1]中的每一个元素k,计算V[m]==V[2-1]-k; 2 n-1 n-1-1]=min(c[0][k]+d[k][m]); (4)输出最短路径长度d[0][2n-1-1]; 时间复杂性: T(n)O(n2n) 和蛮力法相比,动态规划法求解TSP问题,把原来的时间复杂性是0(n! )的排列问题, 转化为组合问题,从而降低了算法的时间复杂性,但它仍需要指数时间。 3.贪心法 贪心法求解TSP问题的贪心策略是显然的,至少有两种贪心策略是合理的: 最近邻点策 略和最短链接策略。 本文仅重点讨论最近邻点策略及其求解过程。 最近邻点策略: 从任意城市出发,每次在没有到过的城市中选择距离已选择的城市中最近的一个,直到经过了所有的城市,最后回到出发城市。 算法讨论 1.P={}; 2.V=V-{u0};u=u0;//从顶点u0出发 3.循环直到集合P中包含n-1条边 3.1查找与顶点u邻接的最小代价边(u,v)并且v属于集合V; 3.2P=P+{(u,v)}; 3.3V=V-{v}; 3.4u=v;//从顶点v出发继续求解 时间复杂性 TO(n2) 但需注意,用最近邻点贪心策略求解TSP问题所得的结果不一定是最优解。 当图中顶点 个数较多并且各边的代价值分布比较均匀时,最近邻点策略可以给出较好的近似解,不过, 这个近似解以何种程度近似于最优解,却难以保证。 4.分支限界法 假设求解最大化问题,解向量为X(Xi,X2,…,Xn),其中,Xi的取值范围为某个有穷 集合s,IS|ri(1in)。 在使用分支限界法搜索问题的解空间树时,首先根据限界函数估算目标函数的界[down,up],然后从根结点出发,扩展根结点的r1个孩子结点,从而构 成分量X1的*种可能的取值方式。 对这*个孩子结点分别估算可能取得的目标函数值 bound(x1),其含义是以该孩子结点为根的子树所可能取得的目标函数值不大于bound(x1), 也就是部分解应满足: bound(x1)bound(x-i,x2)...bound(x1,x2,...,xk)...bound(x1,x2,...,xn) 本文本欲详细讨论该算法,但无奈在编程问题中,尚有问题有待解决,时间所限,不得 已放弃。 本人编程过程中所用算法思想与老师课上所教略有不同,在寻找下界时,是首先把 每个结点所能到达的各个结点及其可能的路径算出来,并添加到PT表中,但最后,不知是 何原因,在还有一个城市尚未加入时,PT表的添加出现了问题,思忖良久,仍未解决,时 间所限,迫不得已,留待以后有时间再另行研究,本文就只给出动态规划法和贪心法的具体求解过程。 四、总结 本文主要重点讨论了动态规划法和贪心法求解TSP问题算法,并附录给出了相应程序。 1.动态规划法思想动态规划法中对于顶点元素生成的子集本文中用字符串形式存储,然后再用递归方法按照子集中元素个数从小到大开始赋值。 因为后面元素个数较多的子集与前面比其元素个数少1的子集间有一定对应关系,所以用递归方式,可以简便很多。 个人觉得这算本文的一大特色。 另,在计算d[i][j]=min(c[i][k]+d[k][j-1])时,获得d[k][j-1]的过程比较困难, 运用字符串后,我们就可以首先找到指定字符,然后去掉该字符,返回剩余字符串,在与 V[]逐个比较,找到与其相等的V[]中元素对应下标,此下标即为j-1;具体求解过程可参考附录源程序,有详细说明。 在求解最佳路径所经过城市顺序时,本文是通过边查找d[i][j] 边记录路径的,这样可以省掉很多麻烦,另,路径也是采用字符串形式的数组,数组规模与存储城市间距离的c[][]数组相同,由于很多元素均不需赋值,这样做可能会浪费内存空间,但是目前还没找到更好地求解方法。 2.贪心法思想 贪心法中,由于贪心法相对动态规划法要简单很多,每次在查找最近城市时所得的顶点均为最后该法最佳路径所经过的城市编号,规模相对较小,容易确定,操作相对简单,所以本文用数组V[]存放最佳路径所经过的城市编号顺序相对来说方便很多。 另外,本文用path[]整型数组存放所经路径的长度,最后相加即可得最短路径。 3.两者比较 动态规划法相对贪心法来说虽然要精确些,但代码相对繁杂很多,对时间和空间要求很多,仅适用于城市数量较小的情况。 贪心法虽然比较简单,实现起来比较容易,但不是很 精确,当图中顶点个数较多并且各边的代价值分布比较均匀时,贪心法可以给出较好的近似 解,不过,这个近似解以何种程度近似于最优解,却难以保证。 另外,动态规划法有一个明显的缺点,就是出发城市只能是第0个城市(城市从0开 始编号),若出发城市改变,则必须以该城市为第0个城市顺序给其他城市编号,输入城市间距离。 由于若出发城市任意,编码的难度大大增加,所以最后不得已放弃,但这大大地限制了程序的通用性。 而对于贪心法,本文很好地避免了这个问题,一旦城市编号确定,可以从任意城市出发,这也是本文中贪心法优于动态规划法的一点。 4.优点 本文程序优点,各个子函数功能分隔很明显,没有大量集中在一个函数里面,而是分成了几个不同功能的小函数,这样程序可阅读性提高。 另外,程序中有详细注释,程序中变 量取名都是根据变量的性质和所代表的含义命名的,也相应提高了程序的可读性。 对于动态规划法,城市个数可以在算法时间允许的范围内任意,于这点来说,通用性较好;对于贪心法,出发城市可以任意,城市个数也可以任意,通用性较好。 5.建议 当城市个数较少时,用动态规划法求出最优解;当城市个数较多并且各边的代价值分布比较均匀时,贪心法可以给出较好的近似解。 参考文献: 1)《计算机算法分析与设计》第二版,王晓东编著,电子工业出版社 2)Java语言与面向对象程序设计(第2版)印旻、王行言编著,清华大学出版社 (3)求解TSP算法,周康、强小利、同小军、许进,计算机工程与应用 4)XX文库 5)XX百科 附录: 源代码 动态规划法: packageexp2; importjava.util.Scanner; String[]V;//顶点生成的子集,这里把每一个子集用一个字符串表示 int[][]c;//顶点间距离 int[][]d;//存放迭代结果 intN;//城市个数 String[][]path;//用于存放每种选择下经过的城市 staticintIFINITE=99999;//无穷大距离表示城市自己到达自己时,距离无穷大,不作为考虑因素 //构造函数 publicTSPDynamic(){ initialC(); initialV1(); } //初始化数组c[],即顶点间距离 publicvoidinitialC(){ Scannerin=newScanner(System.in); System.out.println("请输入城市个数: (注意根据实际情况城市个数不可小于1! ) ); N=in.nextInt(); if(N<=1){ System.out.println("不符合要求,请认真核对! "); System.exit(0);//输入错误,结束! } System.out.println("请输入城市相邻城市间距离(城市从0开始编号,且出发城市 为第0个城市! ): "); c=newint[N][N];// 为c分配空间 for(inti=0;i< N;i++) for(intj=0;j< N;j++){ c[i][j]=in.nextInt();//输入时,按城市编号从小到大,如若两城市间没有公路相连,则距离为无穷大。 本城市与本城市间距离也为无穷大。 } } //初始化顶点生成的子集的对外调用函数 publicvoidinitialV1(){ V=newString[(int)Math.pow(2,N-1)];//为V分配空间 initialV(0,0); } //具体的初始化顶点生成的子集 //本程序使用递归调用方法初始化V,并按照数字大小顺序排序。 。 另,子集使用字符型形 式存放的 //我们是按照子集中元素个数从小到大逐个添加的,后面的子集是前面对应子集加上一个元素组成的,故用递归 publicvoidinitialV(intm,intlen) {//m代表下一个即将初始化的V数组的元素的下标;len是最后一个初始化的元素的长度 if(m>(int)Math.pow(2,N-1)-1)return;//如果全部顶点已初始化完成,则返回。 if(m==0)V[m++]="";//初始化岀发顶点,即V[0] else{ inti=m-1; while(i>=0&&V[i].length()==len)//找与最后一个初始化的V[m-1]子集内 元素个数相同的集合,把指针i指向满足条件的集合 i--; i++;//把指针i指向满足条件的第一个集合 while(i intch;//用于表示下一个即将加入子集的数字 if(i==0)ch=0;//如果i指向V中第一个元素 else{ StringchStr=""+V[i].charAt(V[i].length()-1);//找岀V[i] 中最后一个数字 ch=Integer.parseInt(chStr);//转换成整型 } //比ch大而又比N-1(因为这里顶点是从0开始的)小的数字应该加在子集中 while(ch V[m++]=V[i]+(++ch); i++;//对已存在的自己逐个扫描添加 } } initialV(m,V[m-1].length());//递归调用 } //判断自己V[j]中是否存在指定元素,即行号i booleanexclude(inti,intj){ Stringstr=""+i;//把i转换成字符串 if(V[j].contains(str)) //{System.out.println(i+"i"); returnfalse;//如若存在,则返回falseelsereturntrue; } intk,intj){ return"";//如果子集中只有一个元素,则返回空串 V[j].substring(1,V[j].length());//如果k是第一个 else if(k==V[j].length()-1) returnV[j].substring(0. V[j].length()-1); //如果k是最后一个兀素,则返回其前面的兀素 else return(V[j].substring(0,k)+ V[j].substring(k+1, V[j].length())); } //返回除k外的元素 } //找岀V[]中与str相同元素的下标号,即找岀上一个子集 publicintstringEqual(Stringstr){ 〃if(str.equals(""))return0; inti=0; while(i if(V[i].equals(str)) returni; i++; } return-1;//如若没找到,则返回错误符号-1 } //求最小距离 publicintmin(inti,intj){ intk=0;//用于记录V[j]中元素个数 StringvStr=""+V[j].charAt(k);//铭记V[j].charAt(k)得
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 杜瀚玉 人工智能 讲义