人工智能机器人课程:实用算法之模拟方法
1.模拟法
用a.的数学量和图形描述问题。
计算机处理数学量。用计算机解决实际问题,需要把实际问题抽象成数学量或数。举个例子,
记事本根据ASCII码表将文字转换成数字并存储。对速度的需求用数字来衡量汽车的性能
无论好坏。一个漂亮的算法需要用数学量来表达。
任务:软件工程有两个生产任务,你的团队可以接手任何一个。现在要从两者中选择一个,你需要
考虑制作成本,制作成功的可能性,经济效益的多少,对你团队知名度的影响等等。你们
如何定量分析解决这个问题?
提示:需要将每一项转换成数值,必要时加上权重,计算期望值。如果我们只考虑以上四个因素,我们可以得到
下面的数学公式
综合收益=生产成功概率* 《可获得经济收益-制作成本》 *经济效益权重*团队知名度影响*社会
收益权重
其中概率和两个权重是要估计的值。
有时候,我们需要用更直观的图形来描述实际问题。
图论是一个很好的方法。图形是表达离散量之间关系的一种形式,也是一种思想,常用于建模。与此同时,
前人也给我们提供了很多现成的图论算法,可以解决很多常见的问题,后面会讲到。
矩阵也是一种常用的方法。有时矩阵表示成三角形,如“杨辉三角形”。矩阵通常与数学有关,
矩阵的递推公式是计算机计算中常用的公式。这个后面也会提到。
b.模拟计算过程
模拟是最常见、最直接的算法构造方法。
任务:编程实现欧几里德算法(用相除法求两个数的最大公约数gcd(a,b))。
提示:
欧几里德算法原理:gcd(a,b)=gcd(b,a mod b)
欧几里德算法的图形描述―
| 168 63 |
| 168 63 | 2
|
四十二个
|
1.写下两个数字。2.将两个数相除,将余数写在较大的数下面。
| 168 63 | 2
| 168 63 | 2
1 | 42 21 | 2 ――可除
1 | 42 21 |
3.将每一列中最低的数相除,余数写在被除数下面。4.重复第3步,直到它被平均分配,此时,最终写入的余数为
前两个数的最大公约数。
这是一个简单的模拟算法。在实际过程中,量与量之间的关系往往比这复杂得多,所以仿真算法可以非常复杂。
是的。
有些仿真算法还涉及图形等复杂的数据结构,这就需要我们熟练运用语言,熟练传递其他关系。
数学量之间的关系。
c.模拟的优化
如果处理不当,模拟法写的程序会很长。这就需要我们在模拟中把相似的步骤结合起来,并及时加以利用。
函数简化了程序。
以上面的欧几里德算法为例:
/*在实现时,将左列编号的底部记为L1000,右列编号记为R1000,显然是不明智的,因为
因为只有每列中的最后一个数字将用于将来的计算*/
/*实现方法一:并且每列最后一个数字分别为L和R。也就是说,输入是L,R和gcd(L,R)*/
int Euclid_1(int L,int R)
{
for(;)
{
L=L % R;
if(L==0)返回R;
R=R % L;
if(R==0)返回L;
}
}
/*我们发现有两个步骤是相似的。所以我们可以简化为第二种实现方法*/
int Euclid_2(int L,int R)
{
int t;
for(;)
{
t=R;R=L % Rl=t;
if(R==0)返回L;
}
}
/*甚至我们可以把它写成递归的形式。下面是第三种实现方法*/
int Euclid_3(int L,int R)
{
if(L%R==0)return R;
else return Euclid_3(R,L%R);
}
这个实例主要体现模拟算法的简化过程。虽然在这样小的程序段中,这样的简化作用不大,但遇到复杂
的模拟问题,这种利用相似性的简化便非常有用了。应 当重视这样的代码优化。
d.高精度计算算法
竞赛中经常会用上一些很大的数,超出长整型的数值范围。这时我们需要使用高精度计算算法。这种算
法可以把数值范围增加到我们想要的程度。
高精度函数往往包括加、减、乘、输入、输出五种。
实现高精度计算时,常常使用模拟算法――模拟小学竖式运算。我们把一个高精度数表示为一个数组 H<>,
数组中的某一个数相当于高精度数的某一位。
要注意的是,输出时往往要求以十进制形式输出。因而,高精度数每一位都应便于直接输出。这样,每
一位上的最大数都应是10^n-1。简单地说,若把 H<> 定为 unsigned 型,高精度数每一位上最大数
最好为9999。这样既能尽量利用储存空间,又便于输出。
另外,高精度数有时会用到负数。在补码的体系中,仍然可以按正数的方法处理负数,但是要特别注意
输出时的问题,和对溢出的防止。
任务:实现高精度运算加法
提示:设计函数 unsigned *HAdd(unsigned N1<>,unsigned N2<>,unsigned Ans<>),从末
位起相加,注意是否进位。
显然,减法作为加法的逆运算,也很容易实现。另一种聪明的办法是,对减数每一位取补码,在做加法
4
即可。请读者自行实现高精度减法。
高精度乘法困难一些。我推荐的方法是,先考虑多位高精度数乘一位高精度数的过程。多位高精度数乘
多位高精度数可以转化为多位高精度数乘另一高精度数每一 位,再将结果相加的过程。下面给出多位
高精度数乘一位高精度数的源代码:
#define H_Bit 256 /*定义常数:高精度数位数*/
unsigned *HTimesInt(unsigned N1<>,int N2,unsigned Ans<>) /*N1<>为多位高精度数,
N2为高精度数的一位,Ans<>为另一高精度数,用于储存结果*/
/*这里允许 N1与 Ans 相同*/
{
unsigned i,up=0;
unsigned long temp;
for(i=H_Bit-1;i<=H_Bit;i--)
{
temp=N1*N2+up;
up=temp/10000;
Ans=(unsigned)(temp%10000);
}
return Ans;
/*函数返回作为答案的高精度数首地址,这样更便于高精度运算函数的使用,例如连乘可以写成
HTimesInt(HTimesInt(N1<>,N2,Ans<>),N3,Ans<>)*/
}
高精度数的输入输出需要专门的函数。针对不同语言的不同特点,可以比较容易地写出这两个函数。但
要注意输出非首位数位上的“0”。