14
数学建模竞赛常用算法(10)
10. 图象处理算法
赛题中有一类问题与图形有关，即使问题与图形无 关，论文中也会需要图片来说明问题，这些图形如何展 示以及如何处理就是需要解决的问题，通常使用MATLAB 进行处理。
✓ 01年A 题中需要你会读BMP 图象 ✓ 98年美国A 题需要你知道三维插值计算 ✓ 03年B 题要求更高，不但需要编程计算还要进行处理
29
三个孩子的年龄(2)
A：他们三个年龄之和等于那幢房子的窗户个数。 A指着对面的一幢房子说。 B考虑了一下说，但是，我还有一点信息来解决你的这 个难题。 A：我的大儿子的眼睛是蓝色的。 B：哦，够了， B给出了正确的答案，即三个小孩的年龄。
30
三个孩子的年龄(3)
根据对话信息，用搜索的方法来解此问题。
32
Part 2 模拟方法
33
方法分类
确定性模拟
离散时间 离散事件
随机性模拟
Monte Carlo方法 其它方法
34
Monte Carlo法
穷举是线性搜索（或顺序搜索） Monte Carlo法是随机取点 解决多维、大规模、复杂问题的通用法 模拟次数要足够多
35
Monte Carlo法
孩年龄
第二个小 1
2
3
4
2
6
孩年龄
第三个小 1
1
1
1
2
1
孩年龄
窗户数: 38 21 16 14 13 13
6
4
3
3
2
3
11 10
如果窗户数为38、21、16、14、11、10即可得出答案
B还需信息，即窗户数为13. 则可能为(9、2、2)或(6、6、1)
信息2:大儿子眼睛是蓝色的 得答案：(9、2、2)
5
数学建模竞赛常用算法
✓ 97年的A题 每个零件都有自己的标定值，也都有自
己的容差等级，而求解最优的组合方案将要面对着的是一 个极其复杂的公式和108种容差选取方案，根本不可能去求 解析解，那如何去找到最优的方案呢？随机性模拟搜索最 优方案就是其中的一种方法，在每个零件可行的区间中按 照正态分布随机的选取一个标定值和选取一个容差值作为 一种方案，然后通过蒙特卡罗算法仿真出大量的方案，从 中选取一个最佳的。
drawnow k=k+1; t=t+dt;q=[1 v0*t];u(k)=1;v(k)=q(2); w=q-p;d=norm(w); w=w/d;p=p+v1*dt*w; x(k)=p(1);y(k)=p(2); set(h,'xdata',[x';u'],'ydata',[y';v']);
%pause end %plot(x,y,u,v,'o')
38
确定性模拟
✓ 按时间模拟 ✓ 按事件模拟 ✓ 关键：f(x+1)=f(x)+else
✓ 以人口问题为例 ✓ x(t+h)=x(t)+r x(t) h
dxt
dt
rxt
x0 x0
39
Matlab求解
1. 定义函数
40
Matlab求解
2. 求解
41
Matlab求解
3. 结果
42
Matlab求解
Randi([0,1],[1,10000])
20
模型求解
A=randi([0,1],[1,10000]); Times=sum(A) Probability=Times/10000
小练习 若正面朝下-- -1
21
计算机模拟的特点
适用于大量重复的工作 搜索 穷举 网络法
22
穷举法
4
数学建模竞赛常用算法(1)
1. 蒙特卡罗方法(Monte-Carlo方法, MC)
该算法又称计算机随机性模拟方法，也称统计试验 方法。MC方法是一种基于“随机数”的计算方法，能够 比较逼真地描述事物的特点及物理实验过程，解决一些 数值方法难以解决的问题。
MC方法的雏型可以追溯到十九世纪后期的蒲丰随机 投针试验，即著名的蒲丰问题。 MC方法通过计算机仿 真(模拟)解决问题，同时也可以通过模拟来检验自己 模型的正确性，是比赛中经常使用的方法。
23
穷举法
猜测：解为整数 估计：0<x<25, 0<y<25 算法：列出所有的（x,y）组合，看看哪一
组满足方程。
24
穷举法（一）
25
穷举法（二）
26
网格法
实质上也是穷举法 问题不一定是整数，一般是实数 连续型变量“个数”是无穷，故无法做到穷
举，但实际问题一般允许误差，在精度范围 内可以近似。 给定误差，固定步长，得到网格，进行判断， 得到结果 稳定性差
这方面问题和ACM 程序设计竞赛中的问题类似， 可看一下与计算机算法有关的书。
10
数学建模竞赛常用算法(6)
6. 最优化理论的三大非经典算法:
模拟退火法(SA)、神经网络(NN)、遗传算法(GA)
近几年的赛题越来越复杂，很多问题没有什么很好的 模型可以借鉴，于是这三类算法很多时候可以派上用场。
✓ 97年A 题用模拟退火算法 ✓ 00年B 题用神经网络分类算法 ✓ 01年B 题这种难题也可以使用神经网络 ✓ 美国89年A 题也和BP 算法有关系 ✓ 美国03年B 题伽马刀问题也是目前研究的课题，目前
27
网格法
28
搜索示例：三个孩子的年龄(1)
两个多年未见的朋友相遇，聊了很多事情。…
A：既然你是数学教授，那你帮我算这个题，今天是 个特殊日子：我三个儿子都在今天庆祝生日！那么你 能算出他们都有多大吗？ B：好，但你得跟我讲讲他们的情况。 A：好的，我给你一些提示，他们三个年龄之积是36. B：很好，但我还需要更多提示。
✓ 98 年B 题、00年B 题、95 年锁具装箱等问题体现了 图论问题的重要性。
9
数学建模竞赛常用算法(5)
5. 计算机算法设计中的问题
计算机算法设计包括很多内容：动态规划、回溯搜 索、分治算法、分枝定界等计算机算法. ✓ 92 年B 题用分枝定界法 ✓ 97 年B 题是典型的动态规划问题 ✓ 98 年B 题体现了分治算法
数模论文中也有很多图片需要展示，解决这类问题 要熟悉MATLAB图形图像工具箱。
15
什么是计算机模拟
简单地说：就是用计算机代替人工做事！
模拟就是利用物理的、数学的模型来类比、 模仿现实系统及其演变过程，以寻求过程规 律的一种方法．
在一定的假设条件下，运用数学运算模拟系 统的运行，称为数学模拟．现代的数学模拟 都是在计算机上进行的，称为计算机模拟．
16
计算机模拟抛硬币
如何用计算机来模拟抛硬币 人会抛硬币 但计算机不会 这中间必须架设一座桥
17
建模分析
抛硬币的目的是什么？
18
建模目的
目的： 想知道抛的结果 是正面朝上，还是朝下？ 或者是否击中目标？ ．．．
19
建立模型
正面朝上--1 正面朝下--0 人工抛一次--计算机产生一个随机数 Randi([0,1])
12
数学建模竞赛常用算法(8)
8. 连续问题离散化的方法
很多问题都是实际来的，数据可以是连续的，而计 算机只能处理离散的数据，因此需要将连续问题进行 离散化处理后再用计算机求解。比如差分代替微分、 求和代替积分等思想都是把连续问题离散化的常用方 法。
13
数学建模竞赛常用算法(9)
9. 数值分析方法
36
思考与练习 1. 试求解方程 x10 ex 100 (x 0)
2. 求函数的最小值点（ Rastrigin’s Function）
Ras(x) 20 x12 x22 10(cos 2 x1 cos 2 x2)
全局最小点 (0,0)
37
确定性模拟
例：追击问题
clear clc clf p=[0 0];q=[1,0]; t=0;dt=0.02;v0=0.42/60;v1=2*v0; h=plot([0;1],[0;0],'.'); axis square grid off axis([-0.5,1.5,0,1]); set(h,'erasemode','none','markersize',1); k=0; while 1-p(1)>1e-5
本例中：x(i+h)=x(i)+r x(i) h
49
动态仿真法
50
动态仿真法
51
结合其它方法--插值与拟合
1. 已有数据 2. 观察数据图 3. 选择适合的模型进行拟合
52
拟合
53
拟合
54
随机性模拟
蒙特卡罗（Monte Carlo）方法是一种应 用随机数来进行计算机模拟的方法．此方法 对研究的系统进行随机观察抽样，通过对样 本值的观察统计，求得所研究系统的某些参 数．
信息1:三个小孩年龄之积为36 只有以下8种可能，搜索范围减少至8种情况:
第一个小 36 18 12 9 9 6 6 4
孩年龄
第二个小 1 2 3
孩年龄
4 2 633
第三个小 1 1 1
孩年龄
1 2 1 23
31
三个孩子的年龄(4)
信息2:三个小孩年龄之和等于窗户数
第一个小 36 18 12
9
9
6
算法最佳的是遗传算法。
11
数学建模竞赛常用算法(7)
7. 网格算法和穷举算法
网格算法和穷举法一样，只是网格法是连续问题的穷 举。此类算法运算量较大。
✓ 97 年A 题、99 年B 题都可以用网格法搜索