没有合适的资源?快使用搜索试试~ 我知道了~
算法报告-旅行商问题模板汇编.pdf
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 1 下载量 129 浏览量
2023-09-13
12:53:39
上传
评论
收藏 905KB PDF 举报
温馨提示
试读
22页
算法报告-旅行商问题模板汇编.pdf
资源推荐
资源详情
资源评论
《算法设计与课程设计》
题 目: TSP问题多种算法策略
班 级: 计算机技术 14
学 号:
姓 名:
指导老师:
完成日期:
成 绩:
旅行商问题的求解方法
摘要
旅行商问题(TSP 问题)时是指旅行家要旅行 n 个城市然后回到出发城市,
要求各个城市经历且仅经历一次,并要求所走的路程最短。该问题又称为货郎担
问题、邮递员问题、售货员问题,是图问题中最广为人知的问题。本文主要介绍
用动态规划法、贪心法、回溯法和深度优先搜索策略求解 TSP 问题,其中重点
讨论动态规划法和贪心法,并给出相应求解程序。
关键字:旅行商问题;动态规划法;贪心法;回溯法;深度优先搜索策略
1 引言
旅行商问题(TSP)是组合优化问题中典型的 NP-完全问题,是许多领域内复
杂工程优化问题的抽象形式。研究 TSP 的求解方法对解决复杂工程优化问题具
有重要的参考价值。关于 TSP 的完全有效的算法目前尚未找到,这促使人们长
期以来不断地探索并积累了大量的算法。归纳起来,目前主要算法可分成传统优
化算法和现代优化算法。在传统优化算法中又可分为:最优解算法和近似方法。
最优解算法虽然可以得到精确解,但计算时间无法忍受,因此就产生了各种近似
方法,这些近似算法虽然可以较快地求得接近最优解的可行解,但其接近最优解
的程度不能令人满意。但限于所学知识和时间限制,本文重点只讨论传统优化算
法中的动态规划法、贪心法、回溯法和深度优先搜索策略。
2 正文
2.1动态规划法
2.1.1动态规划法的设计思想
动态规划法将待求解问题分解成若干个相互重叠的子问题,每个子问题对应
决策过程的一个阶段,一般来说,子问题的重叠关系表现在对给定问题求解的递
推关系(也就是动态规划函数)中,将子问题的解求解一次并填入表中,当需要
再次求解此子问题时,可以通过查表获得该子问题的解而不用再次求解,从而避
免了大量重复计算。
2.1.2 TSP问题的动态规划函数
假设从顶点 i 出发,令
'
( , )d i V
表示从顶点 i 出发经过
'
V
中各个顶点一次且仅
一次,最后回到出发点 i 的最短路径长度,开始时,
'
V V i
,于是,TSP 问
题的动态规划函数为:
' '
( , ) min ( , ) ( )
( , ) ( )
ik
ki
d i V c d k V k k V
d k c k i
2.1.3算法分析
(1)for (i=1; i<N; i++) //初始化第 0 列
d[i][0]=c[i][0];
(2)for (j=1; j<
n-1
2
-1; j++)
for (i=1; i<n; i++) //依次进行第 i 次迭代
if (子集 V[j]中不包含 i)
对 V[j]中的每个元素 k,计算 V[m] == V[j]-k;
d[i][j]=min(c[i][k]+d[k][m]);
(3)对 V[
n-1
2
-1]中的每一个元素 k,计算 V[m] == V[
n-1
2
-1]-k;
d[0][
n-1
2
-1]=min(c[0][k]+d[k][m]);
(4)输出最短路径长度 d[0][
n-1
2
-1];
2.1.4时间复杂性
T( ) ( 2 )
n
n O n
动态规划法求解 TSP 问题,把原来的时间复杂性是 O(n!)的排列问题,转化
为组合问题,从而降低了算法的时间复杂性,但它仍需要指数时间。
2.2贪心法
2.2.1贪心法的设计思想
贪心法在解决问题的策略上目光短浅,只根据当前已有的信息就做出选择,
而且一旦做出了选择,不管将来有什么结果,这个选择都不会改变。换言之,贪
心法并不是从整体最优考虑,它所做出的选择只是在某种意义上的局部最优。这
种局部最优选择并不总能获得整体最优解,但通常能获得近似最优解。
2.2.2最近邻点策略求解 TSP问题
贪心法求解 TSP 问题的贪心策略是显然的,至少有两种贪心策略是合理的:
最近邻点策略和最短链接策略。本文仅重点讨论最近邻点策略及其求解过程。
最近邻点策略:从任意城市出发,每次在没有到过的城市中选择距离已选择的城
市中最近的一个,直到经过了所有的城市,最后回到出发城市。
2.2.3算法分析
1.P={ };
2.V=V-{u0}; u=u0; //从顶点 u0 出发
3.循环直到集合 P 中包含 n-1 条边
3.1 查找与顶点 u 邻接的最小代价边(u, v)并且 v 属于集合 V;
3.2 P=P+{(u, v)};
3.3 V=V-{v};
3.4 u=v; //从顶点 v 出发继续求解
2.2.4时间复杂性
2
( )T O n
但需注意,用最近邻点贪心策略求解 TSP 问题所得的结果不一定是最优解。
当图中顶点个数较多并且各边的代价值分布比较均匀时,最近邻点策略可以给出
较好的近似解,不过,这个近似解以何种程度近似于最优解,却难以保证。
2.3回溯法
2.3.1回溯法的设计思想
回溯法(探索与回溯法)是一种选优搜索法,按选优条件向前搜索,以达到目
标。但当探索到某一步时,发现原先选择并不优或达不到目标,就退回一步重新
选择,这种走不通就退回再走的技术为回溯法,而满足回溯条件的某个状态的点
称为“回溯点”。
若已有满足约束条件的部分解,不妨设为(x1,x2,x3,……xi),I<n,则添加
x(i+1)属于 s(i+2),检查 (x1,x2,……,xi,x(i+1))是否满足条件,满足了就继续添加
x(i+2)、s(i+2),若所有的 x(i+1)属于 s(i+1)都不能得到 部分解,就去掉 xi,回溯
到(xi,x2,……x(i- 1)),添加那些未考察过的 x1 属于 s1,看其是否满足约束条件,
为此反复进行,直至得到解或证明无解。
2.3.2 算法分析(回溯法+深度优先搜索策略)
因为是采用回溯法来做,肯定是递归,然后还需要现场清理。
要设置一个二维数组来标识矩阵内容,然后回溯还需要设计
一个二维标记数组来剪枝,设定一个目标变量,初始为无穷大,
后续如果有比目标变量值小的就更新。剪枝的条件就是如果走到当前节点的
耗费值>=目标变量,就直接不再往下面走,向上走。
深度优先 = 递归
递归基:如果到达叶子节点的上一个节点,那么就进行是否更新的判断
递归步:如果没有到达叶子节点,就进行剪枝操作,判断能否进入下一个节
点,如果能,更新最优值
2.3.3 关键实现(回溯法+深度优先搜索策略)
1 //递归基:如果已经遍历到叶子节点的上一层节点,i 标识递归深度
if(i == g_n)
{
//判断累加和是否超过最大值,如果有 0,应该排除;满足这个条件,才打印
if((g_iArr[pArr[i-1]][pArr[i]] != 0) && (g_iArr[pArr[g_n]][1] != 0) &&
(g_iCurResult + g_iArr[pArr[i-1]][pArr[i]] + g_iArr[pArr[g_n]][1]
< g_iResult ))
{
g_iResult = g_iCurResult + g_iArr[pArr[i-1]][pArr[i]] +
g_iArr[pArr[g_n]][1];
//用当前最优路径去更新最优路径,防止下一次没有
for(int k = 1 ; k <= g_n ; k++)
{
剩余21页未读,继续阅读
资源评论
- FAQriri2024-01-11这个资源值得下载,资源内容详细全面,与描述一致,受益匪浅。
hhappy0123456789
- 粉丝: 61
- 资源: 5万+
下载权益
C知道特权
VIP文章
课程特权
开通VIP
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功