MATLAB课程设计.docx
- 文档编号:16243087
- 上传时间:2023-07-12
- 格式:DOCX
- 页数:18
- 大小:157.93KB
MATLAB课程设计.docx
《MATLAB课程设计.docx》由会员分享,可在线阅读,更多相关《MATLAB课程设计.docx(18页珍藏版)》请在冰点文库上搜索。
MATLAB课程设计
《MATLAB》课程设计
题目名称:
旅行商最短线路(TSP)
所在学院:
信息工程学院
专业名称:
自动化专升本13-1
姓名:
学号:
指导教师:
目录
第1章引言2
1.1研究背景2
1.2研究内容2
1.3研究目标2
1.4研究意义2
第2章贪心算法的基本知识概述3
2.1贪心算法定义3
2.2贪心算法的基本思路及实现过程3
2.2.1贪心的基本思想3
2.2.2贪心算法的实现过程3
2.3贪心算法的核心3
2.4贪心算法的基本要素4
2.4.1贪心选择性质4
2.4.2最优子结构性质4
2.4.3贪心算法的特点4
2.5贪心算法的理论基础5
2.6贪心算法存在的问题6
第3章第3章旅行商问题(TSP)6
3.1旅行商问题(TSP)6
3.2多点贪心算法原理7
3.2.1贪心算法基本原理7
3.2.2多点贪心算法原理7
3.3算法过程的VisualBasic程序描述7
3.4算例分析9
第4章总结与展望12
4.1总结12
4.2展望12
第5章参考文献13
第1章引言
1.1研究背景
为了满足人们对大数据量信息处理的渴望,为解决各种实际问题,计算机算法学得到了飞速的发展,线性规划、动态规划、贪心策略等一系列运筹学模型纷纷运用到计算机算法学中,产生了解决各种现实问题的有效算法。
虽然设计一个好的求解算法更像是一门艺术而不像是技术,但仍然存在一些行之有效的、能够用于解决许多问题的算法设计方法,你可以使用这些方法来设计算法,并观察这些算法是如何工作的。
一般情况下,为了获得较好的性能,必须对算法进行细致的调整。
但是在某些情况下,算法经过调整之后性能仍无法达到要求,这时就必须寻求另外的方法来求解该问题。
当一个问题具有最优子结构性质和贪心选择性质时,贪心算法通常会给出一个简单、直观和高效的解法。
贪心算法通过一系列的选择来得到一个问题的解。
它所作的每一个选择都是在当前状态下具有某种意义的最好选择,即贪心选择;并且每次贪心选择都能将问题化简为一个更小的与原问题具有相同形式的子问题。
尽管贪心算法对许多问题不能总是产生整体最优解,但对诸如最短路径问题、最小生成树问题,以及哈夫曼编码问题等具有最优子结构和贪心选择性质的问题却可以获得整体最优解。
而且所给出的算法一般比动态规划算法更加简单、直观和高效。
1.2研究内容
贪心算法的定义(是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法),贪心算法的基本要素(最优子结构性质、贪心选择性质)、贪心算法的思路及过程,贪心算法的核心(贪心策略)及特性(无回溯)、探讨贪心算法存在的问题。
1.3研究目标
通过本课题的研究来探讨贪心算法理论基础以及对贪心策略在更多实例中的运用做可行的研究,为贪心算法能够运用到更多的实际中的问题作示范。
1.4研究意义
贪心算法是计算机算法策略中常用的一个,往往在需要解决一些最优性问题时,都可以应用贪心算法。
贪心算法的用法特点有:
一是明显的贪心,一般此类应用问题本身就是贪心;二是贪心数据结构,如:
堆,最小树;三是可证明贪心策略的贪心,这是我们最常见的;四是博弈、游戏策略,这些策略大多是贪心;五是求较优解或多次逼近最优解。
通过用贪心算法求解以上问题,可以找到解决这些问题的最优算法,为其它的类似问题的解决有示范和例证作用。
第2章贪心算法的基本知识概述
2.1贪心算法定义
贪心算法可以简单描述为:
对一组数据进行排序,找出最小值,进行处理,再找出最小值,再处理。
也就是说贪心算法是一种在每一步选择中都采取在当前状态下最好或最优的选择,从而希望得到结果是最好或最优的算法。
贪心算法是一种能够得到某种度量意义下的最优解的分级处理方法,通过一系列的选择来得到一个问题的解,而它所做的每一次选择都是当前状态下某种意义的最好选择,即贪心选择。
即希望通过问题的局部最优解来求出整个问题的最优解。
这种策略是一种很简洁的方法,对许多问题它能产生整体最优解,但不能保证总是有效,因为它不是对所有问题都能得到整体最优解,只能说其解必然是最优解的很好近似值。
2.2贪心算法的基本思路及实现过程
2.2.1贪心的基本思想
用局部解构造全局解,即从问题的某一个初始解逐步逼近给定的目标,以尽可能快地求得更好的解。
当某个算法中的某一步不能再继续前进时,算法停止。
贪心算法思想的本质就是分治,或者说:
分治是贪心的基础。
每次都形成局部最优解,换一种方法说,就是每次都处理出一个最好的方案。
利用贪心策略解题,需要解决两个问题:
(1)该题是否适合于用贪心策略求解;
(2)如何选择贪心标准,以得到问题的最优/较优解。
2.2.2贪心算法的实现过程
(1)应用同一规则F,将原问题变为一个相似的、但规模更小的子问题;
(2)从问题的某一初始解出发:
While(能朝给定目标前进一步)
求出可行解的一个解元素;
(3)由所有解元素组合成问题的一个可行解。
2.3贪心算法的核心
贪心算法的核心问题是选择能产生问题最优解的最优度量标准,即具体的贪心策略。
贪心策略是指从问题的初始状态出发,通过若干次的贪心选择而得出最优值(或较优解)的一种解题方法。
其实,从“贪心策略”一词我们便可以看出,贪心策略总是做出在当前看来是最优的选择,也就是说贪心策略并不是从整体上加以考虑,它所做出的选择只是在某种意义上的局部最优解,而许多问题自身的特性决定了该题运用贪心策略可以得到最优解或较优解。
2.4贪心算法的基本要素
2.4.1贪心选择性质
所谓贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择,即贪心选择来达到。
这是贪心算法可行的第一个基本要素,也是贪心算法与动态规划算法的主要区别。
在动态规划算法中,每步所做的选择往往依赖于相关子问题的解。
因而只有在解出相关子问题后,才能做出选择。
而在贪心算法中,仅在当前状态下做出最好选择,即局部最优选择。
然后再去解做出这个选择后产生的相应的子问题。
贪心算法所做的贪心选择可以依赖于以往所做过的选择,但决不依赖于将来所做的选择,也不依赖于子问题的解。
正是由于这种差别,动态规划算法通常以自底向上的方式解各子问题,而贪心算法则通常以自顶向下的方式进行,以迭代的方式做出相继的贪心选择,每做一次贪心选择就将所求问题简化为规模更小的子问题。
对于一个具体问题,要确定它是否具有贪心选择性质,必须证明每一步所做的贪心选择最终导致问题的整体最优解。
首先考察问题的一个整体最优解,并证明可修改这个最优解,使其以贪心选择开始。
做了贪心选择后,原问题简化为规模更小的类似子问题。
然后,用数学归纳法证明,通过每一步做贪心选择,最终可得到问题的整体最优解。
其中,证明贪心选择后的问题简化为规模更小的类似子问题的关键在于利用该问题的最优子结构性质。
2.4.2最优子结构性质
当一个问题的最优解包含其子问题的最优解时,称此问题具有最优子结构性质。
运用贪心策略在每一次转化时都取得了最优解。
问题的最优子结构性质是该问题可用贪心算法或动态规划算法求解的关键特征。
贪心算法的每一次操作都对结果产生直接影响,而动态规划则不是。
贪心算法对每个子问题的解决方案都做出选择,不能回退;动态规划则会根据以前的选择结果对当前进行选择,有回退功能。
动态规划主要运用于二维或三维问题,而贪心一般是一维问题。
2.4.3贪心算法的特点
贪心算法的最大特点就是快,通常是线性二次式,不需要多少额外的内存。
一般二次方级的存储要浪费额外的空间,而且那些空间经常得不出正解。
但是,使用贪心算法时,这些空间可以帮助算法更容易实现且更快执行。
如果有正确贪心性质存在,那么一定要采用。
因为它容易编写,容易调试,速度极快,并且节约空间。
几乎可以说,此时它是所有算法中最好的。
但是应该注意,贪心算法有两大难点:
(1)如何贪心
怎样用一个小规模的解构造更大规模的解呢?
总体上,这与问题本身有关。
但是大部分都是有规律的。
正因为贪心有如此性质,它才能比其他算法快。
具有应当采用贪心算法的问题,当“贪心序列”中的每项互异且当问题没有重叠性时,看起来总能通过贪心算法取得(近似)最优解的。
或者,总有一种直觉在引导我们对一些问题采用贪心算法。
其中“找零钱”这个问题就是一个例子。
题中给出的硬币面值事实上具有特殊性,如果面值发生变化,可能贪心算法就不能返回最优解了。
但是,值得指出的是,当一个问题具有多个最优解时,贪心算法并不能求出所有最优解。
另外,我们经过实践发现,单纯的贪心算法是顺序处理问题的;而且每个结果是可以在处理完一个数据后即时输出的。
(2)贪心的正确性
要证明贪心性质的正确性,才是贪心算法的真正挑战,因为并不是每次局部最优解都会与整体最优解之间有联系,往往靠贪心算法生成的解不是最优解。
这样,贪心性质的证明就成了贪心算法正确的关键。
对某些问题贪心性质也许是错的,即使它在大部分数据中都是可行的,但还必须考虑到所有可能出现的特殊情况,并证明该贪心性质在这些特殊情况中仍然正确。
而这样容易陷入证明不正确贪心性质的泥塘中无法自拔,因为贪心算法的适用范围并不大,而且有一部分极难证明,若是没有把握,最好不要冒险,还有其他算法会比它要保险。
2.5贪心算法的理论基础
正如前文所说的那样,贪心策略是最接近人类认知思维的一种解题策略。
但是,越是显而易见的方法往往越难以证明。
下面我们就来介绍贪心策略的理论—拟阵。
“拟阵”理论是一种能够确定贪心策略何时能够产生最优解的理论,虽然这套理论还很不完善,但在求解最优化问题时发挥着越来越重要的作用。
拟阵M定义为满足下面3个条件的有序对(S,I):
(1)S是非空有限集;
(2)I是S的一类具有遗传性质的独立子集族,即若B∈I,则B是S的独立子集,且B的任意子集也都是S的独立子集。
空集¢必为I的成员;
(3)I满足交换性质,即若A∈I,B∈I且|A|<|B|,则存在某一元素x∈B-A,使得A∪{x}∈I。
定理2.1拟阵M中所有极大独立子集具有相同大小。
引理2.1(拟阵的贪心选择性质)设M=(S,I)是具有权函数M的带权拟阵,且S中元素依权值从大到小排列,又设x∈S是S中第一个使得{x}是独立子集元素,则存在S的最优子集A使得x∈A。
引理2.2设M=(S,I)是拟阵。
若S中元素x不是空集¢的一个可扩元素,则x也不可能是S中任一独立子集A的可扩展元素。
引理2.3(拟阵的最优子结构性质)设x是求带权拟阵M=(S,I)的最优子集的贪心算法Greedy所选择的S中的第一个元素。
那么,原问题可简化为求带权拟阵M'=(S',I')的最优子集问题,其中S'={y|y∈S且{x,y}∈I}
I'={B|B
S-{x}且B∪{x}∈I}
M'的权函数是M的权函数在S'上的限制(称M'为M关于元素x的收缩)。
定理2.4(带权拟阵贪心算法的正确性)高M=(S,I)是具有权函数W的带权拟阵,算法Greedy返回M的最优子集。
适宜于用贪心策略来求解的许多问题都可以归结为在加权拟阵中找一个具有最大权值的独立子集的问题,即给定一个加权拟阵M=(S,I),若能找出一个独立且具有最大可能权值的子集A,且A不被M中比它更大的独立子集所包含,那么A为最优子集,也是一个最大的独立子集。
我们认为,针对绝大多数的信息学问题,只要它具备了“拟阵”的结构,便可用贪心策略求解。
拟阵理论对于我们判断贪心策略是否适用于某一复杂问题是十分有效的。
2.6贪心算法存在的问题
(1)不能保证求得的最后解是最佳的。
由于贪心策略总是采用从局部看来是最优的选择,因此并不从整体上加以考虑;
(2)贪心算法只能用来求某些最大或最小解的问题;
(3)贪心算法只能确定某些问题的可行性范围。
第3章第3章旅行商问题(TSP)
3.1旅行商问题(TSP)
旅行商问题(TravelingSalemanProblem,TSP)属于NP难题,也称为货郎担问题,是由爱尔兰数学家SirWilliamRowanHamilton和英国数学家ThomasPenyngtonKirkman在19世纪提出的数学问题。
它是指:
假设有一个旅行商人要拜访n个城市,需要选择一条最优路径,每个城市只能拜访一次,而且最后要回到原来出发的城市。
如何确定最短路线?
TSP问题最简单的求解方法是枚举法。
它的解是多维的、多局部极值的、趋于无穷大的复杂解的空间,搜索空间是n个点的所有排列的集合,大小为n!
。
路径的选择目标是要求得的路径路程为所有路径之中的最小值。
由于该问题的描述简单,而其实际模型在管道铺设,线路选择等优化问题中又有着广泛的应用,故长期以来一直吸引着国内外许多研究人员进行研究,他们尝试着用各种算法来求解TSP问题。
归纳起来有:
近似解法、局部搜索法、神经网络、遗传算法、克隆算法、模拟退火算法、混合遗传算法等[1~10]。
在所有的算法中,贪心算法是容易理解的好算法,也可也达到问题的一个次优解。
但是古典的贪心算法存在的问题的最后返回出发点可能会出现一个较大的距离。
本文将在古典的贪心算法基础上,通过改进获得一个称为多点贪心算法,并给出算例分析。
3.2多点贪心算法原理
3.2.1贪心算法基本原理
设共有n点,以下称为节点,其节点号码分别为
。
贪心算法依据下面过程:
(1)从
号节点出发,分别计算1号节点余下的
个节点距离,与1号节点的最短距离点称为
,最小距离为
;
(2)计算
号节点与余下的
个节点距离,与
号节点的最短距离点称为
,其最小距离为
;
;(3)计算
号节点与余下的
个节点距离,与
号节点的最短距离点称为
,其最小距离为
;
;(4)最后,计算
号节点与余下的
号节点距离,
。
总路程:
。
上面的算法,可能会导致最后返回出发点的距离很大。
3.2.2多点贪心算法原理
为了改善贪心算法直接计算的不足,可以考虑出发节点不同情况;两个步骤:
(1)确定从n个节点中的每个节点出发,依据贪心算法确定总路程
;
(2)比较
,获得最短路程:
。
(3)按
,给出行走路线;无论从哪个节点出发,都将按此行走路线方向行走。
3.3算法过程的VisualBasic程序描述
(1)输入节点数量与坐标;
(2)标记目前节点,设置
点为开始节点;
(3)确定以
为开始节点的贪婪路线:
包括计算、比较每步最小距离,计算路线总距离。
计算第
点与余下所有点距离
比较出第
点与余下所有点的最小距离,并获得第
点;
文件输出,行走路线
绘制行走路线
计算从
点为开始节点的最小贪心路程
文件输出路程长度
(4)当
时,
转到
(2)
当
时,转到(5)
(5)比较多点贪心算法最优路程,获得最优出发点
3.4算例分析
算例1:
具有30个节点TSP问题,其节点坐标位置见表1。
表1算例1的节点坐标
序号
x
y
序号
x
y
序号
x
y
1
41
94
11
64
60
21
87
76
2
37
84
12
18
54
22
18
40
3
54
67
13
22
60
23
13
40
4
25
62
14
83
46
24
82
7
5
7
64
15
91
38
25
62
32
6
2
99
16
25
38
26
58
35
7
68
58
17
24
42
27
45
21
8
71
44
18
58
69
28
41
26
9
54
62
19
71
71
29
44
35
10
83
69
20
74
78
30
4
50
下表为程序计算的从序号节点出发的路程情况。
表2算例1不同起点贪心算法路程列表
序号
路程
序号
路程
序号
路程
1
572.9255
11
546.4583
21
534.0436
2
571.8588
12
565.6044
22
590.5583
3
539.7319
13
486.9163
23
590.1809
4
482.6496
14
488.7771
24
569.4215
5
515.4323
15
473.3292
25
577.7069
6
515.4324
16
542.6708
26
497.5285
7
523.1558
17
539.5327
27
520.0176
8
597.2203
18
536.9409
28
530.1949
9
532.7935
19
507.0815
29
532.7643
10
592.1368
20
513.0300
30
499.3936
多点贪婪算法的最短路程为L=473.3292。
图绘制出了该情况的行走路线。
起点为15号节点。
其行走顺序为:
15→14→8→7→11→9→3→18→19→20→10→21→1→2→4→13→12→17→16→22→23→30→5→6→29→28→27→26→25→24→15
图1算例1行走路线
算例2:
具有50个节点的TSP问题,其节点坐标位置为表3。
表3算例2的节点坐标
序号
x
y
序号
x
y
序号
x
y
序号
x
y
1
31
32
14
42
41
27
56
37
40
62
63
2
32
39
15
17
33
28
52
41
41
20
26
3
40
30
16
25
32
29
49
49
42
5
6
4
37
69
17
5
64
30
58
48
43
13
13
5
27
68
18
8
52
31
57
58
44
21
10
6
37
52
19
12
42
32
39
10
45
30
15
7
38
46
20
7
38
33
46
10
46
36
16
8
31
62
21
5
25
34
59
15
47
62
42
9
30
48
22
10
17
35
51
21
48
63
69
10
21
47
23
45
35
36
48
28
49
52
64
11
25
55
24
42
57
37
52
33
50
43
67
12
16
57
25
32
22
38
58
27
13
17
63
26
27
23
39
61
33
表4算例2不同起点贪心算法路程列表
序号
路程
序号
路程
序号
路程
序号
路程
1
565.0313
14
567.27
27
593.9211
40
560.0534
2
563.8102
15
570.2241
28
586.1978
41
504.2818
3
571.0603
16
539.0402
29
559.2667
42
524.3514
4
544.2585
17
507.4037
30
576.6629
43
524.3514
5
534.9626
18
535.7208
31
489.1917
44
535.4759
6
512.5934
19
561.1537
32
524.8142
45
589.0931
7
552.4794
20
558.473
33
538.1735
46
555.7452
8
539.5091
21
564.0051
34
598.4741
47
585.4095
9
511.2411
22
601.7819
35
557.8325
48
494.0723
10
510.5335
23
565.4716
36
550.5068
49
492.705
11
503.8491
24
519.5168
37
574.7575
50
492.705
12
527.7145
25
546.9865
38
576.3978
13
493.3062
26
574.9308
39
524.3655
多点贪婪算法的最短路程为L=489.1917。
图绘制出了该情况的行走路线。
起点为31号节点。
其行走顺序为:
31→40→48→49→50→4→8→5→13→12→11→9→6→7→14→23→3→36→37→27→28→29→30→47→39→38→35→34→33→32→46→45→25→26→41→15→16→1→2→10→19→20→21→22→43→44→42→18→17→24→31
图2算例2行走路线
第4章总结与展望
4.1总结
贪心算法是很常见的算法,贪心策略是最接近人的日常思维的一种解题策略,虽然它不能保证求得的最后解一定是最佳的,但是它可以为某些问题确定一个可行性范围。
贪心算法所作的选择依赖于以往所作过的选择,但决不依赖于将来的选择,这使得算法在编码和执行过程中都有一定的速度优势。
对于一个问题的最优解只能用穷举法得到时,用贪心算法是寻找问题最优解的较好算法。
对一个问题可以同时用几种方法解决,贪心算法并不是对所有的问题都能得到整体最优解或是最理想的近似解时,就需判断贪心性质的正确性了。
与回溯法、动态规划法等比较,它的适用区域相对狭窄许多。
总之,如果一个贪心解决方案存在,就可以使用它。
4.2展望
对于贪心算法的应用,如果某个问题具有贪心算法的贪心选择性质和最优子结构性质,那么,它就可以采用贪心策略进行分析,进而求解,贪心算法的应用举例不仅只有本论文中的那几个,他对于背包问题、最优装载问题、硬币找钱问题等都是十分方便有效的算法,贪心算法在科学计算和工程中的应用也越来越广泛,例如用贪心算法进行三角剖分的指纹匹配方法、贪心算法在竞赛中的应用、贪心算法在排课系统中的应用、贪心聚类算法及其在遥感图像分类和压缩中的应用等等,在未来出现的一些问题中,只要符合贪心算法的贪心策略性质,就可以用贪心算法求解,让贪心算法能够应用到更广更多的问题中去吧!
第5章参考文献
【1】邢文训,谢金星.现代优化计算方法[M].北京:
清华大学出版社,1998:
117-121.
【2】周培德.求解货郎担问题的几何算法[J].北京理工大学学报,1995,15
(1):
97-99.
【3】邹鹏.求解TSP问题的多级归约算法[J].软件学报,2003,14
(1):
35-42.
【4】朱文兴,傅清祥.一个基于填充函数变换的对称TSP问题的局部搜索算法[J].计算机学报,2002,25(7):
701-707.
【5】孙惠文.遗传算法求解旅行商问题[J].西南交通大学学报,1996,3
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- MATLAB 课程设计