Sunday, September 12, 2004

 

Some notes on Windows Game

1.
Richard Kaye's Minesweeper Pages

From http://web.mat.bham.ac.uk/R.W.Kaye/minesw/minesw.htm

It is interesting to find that

"Minesweeper is NP-complete!
For minesweeper addicts, this is either very good news, or very bad news (it depends on your point of view). My paper with the above title, which incidently goes to some lengths to explain what NP-completeness means and why it is important, has appeared in the Mathematical Intelligencer."

Saturday, September 11, 2004

 

Hit Testing for Lines and Curves

1.
Win32: Hit Testing Lines and Curves
Dennis Crain
Microsoft Developer Network Technology Group

Created: February 8, 1994
From http://msdn.microsoft.com/library/default.asp?url=/library/en-us/dngdi/html/msdn_hittest2.asp

"What Is Hit Testing?
To the user, the act of hit testing in a graphical user interface seems natural. The pointing device's cursor is placed over an object, and the user initiates an action to "hit" the object. Most often this pointing device is a mouse, and the action is a mouse click.

Within the context of this article, let's agree that hit testing is the process of determining if the user has selected a line or a curve by means of a mouse click. I will describe three methods for selecting these objects. Two methods are general in that they do not rely on any of the functionality of Win32. The third method combines the line hit-testing method with a new feature of Win32, paths.

Many programmers know hit testing as "picking," the term used in many textbooks on graphics and in many graphics languages. For example, you pick a line segment on the screen and move it to another location."

2.
Connectors and Cables
Dennis Crain
Microsoft Developer Network Technology Group

May 1995

From http://msdn.microsoft.com/archive/default.asp?url=/archive/en-us/dnargdi/html/msdn_cables.asp

3.
GDI+ Line/Curve Drawing and Hit Test
By Husni Che Ngah

Demo application for developing a drawing application using GDI+. Featuring line/curve draw, hit test, and implementation of CObject/CObArray classes.

http://www.codeproject.com/vcpp/gdiplus/HitTester.asp

4.
Graph Marker with Hit-Testing
By Wenfei Wu February 11, 1999

http://www.codeguru.com/Cpp/misc/misc/graphics/article.php/c379/

Friday, September 10, 2004

 

常用算法设计方法

原作者:宁波高等专科学校电子系 周文革

要使计算机能完成人们预定的工作,首先必须为如何完成预定的工作设计一个算法,然后再根据算法编写程序。计算机程序要对问题的每个对象和处理规则给出正确详尽的描述,其中程序的数据结构和变量用来描述问题的对象,程序结构、函数和语句用来描述问题的算法。算法数据结构是程序的两个重要方面。
算法是问题求解过程的精确描述,一个算法由有限条可完全机械地执行的、有确定结果的指令组成。指令正确地描述了要完成的任务和它们被执行的顺序。计算机按算法指令所描述的顺序执行算法的指令能在有限的步骤内终止,或终止于给出问题的解,或终止于指出问题对此输入数据无解。
通常求解一个问题可能会有多种算法可供选择,选择的主要标准是算法的正确性和可靠性,简单性和易理解性。其次是算法所需要的存储空间少和执行更快等。
算法设计是一件非常困难的工作,经常采用的算法设计技术主要有迭代法、穷举搜索法、递推法、贪婪法、回溯法、分治法、动态规划法等等。另外,为了更简洁的形式设计和藐视算法,在算法设计时又常常采用递归技术,用递归描述算法。

# 回复:常用算法设计方法(转贴)-> 2004-11-19 12:00 PM 一、迭代法
一、迭代法

迭代法是用于求方程或方程组近似根的一种常用的算法设计方法。设方程为f(x)=0,用某种数学方法导出等价的形式x=g(x),然后按以下步骤执行:
(1) 选一个方程的近似根,赋给变量x0;
(2) 将x0的值保存于变量x1,然后计算g(x1),并将结果存于变量x0;
(3) 当x0与x1的差的绝对值还小于指定的精度要求时,重复步骤(2)的计算。
若方程有根,并且用上述方法计算出来的近似根序列收敛,则按上述方法求得的x0就认为是方程的根。上述算法用C程序的形式表示为:
【算法】迭代法求方程的根
{ x0=初始近似根;
do {
x1=x0;
x0=g(x1); /*按特定的方程计算新的近似根*/
} while ( fabs(x0-x1)>Epsilon);
printf(“方程的近似根是%f\n”,x0);
}
迭代算法也常用于求方程组的根,令
X=(x0,x1,…,xn-1)
设方程组为:
xi=gi(X) (I=0,1,…,n-1)
则求方程组根的迭代算法可描述如下:
【算法】迭代法求方程组的根
{ for (i=0;i< n;i++)
x[i]=初始近似根;
do {
for (i=0;i< n;i++)
y[i]=x[i];
for (i=0;i< n;i++)
x[i]=gi(X);
for (delta=0.0,i=0;i< n;i++)
if (fabs(y[i]-x[i])>delta) delta=fabs(y[i]-x[i]);
} while (delta>Epsilon);
for (i=0;i< n;i++)
printf(“变量x[%d]的近似根是 %f”,I,x[i]);
printf(“\n”);
}
具体使用迭代法求根时应注意以下两种可能发生的情况:
(1) 如果方程无解,算法求出的近似根序列就不会收敛,迭代过程会变成死循环,因此在使用迭代算法前应先考察方程是否有解,并在程序中对迭代的次数给予限制;
(2) 方程虽然有解,但迭代公式选择不当,或迭代的初始近似根选择不合理,也会导致迭代失败。


# 回复:常用算法设计方法(转贴)-> 2004-11-19 12:01 PM 二、穷举搜索法
二、穷举搜索法

穷举搜索法是对可能是解的众多候选解按某种顺序进行逐一枚举和检验,并从众找出那些符合要求的候选解作为问题的解。
【问题】 将A、B、C、D、E、F这六个变量排成如图所示的三角形,这六个变量分别取[1,6]上的整数,且均不相同。求使三角形三条边上的变量之和相等的全部解。如图就是一个解。
程序引入变量a、b、c、d、e、f,并让它们分别顺序取1至6的证书,在它们互不相同的条件下,测试由它们排成的如图所示的三角形三条边上的变量之和是否相等,如相等即为一种满足要求的排列,把它们输出。当这些变量取尽所有的组合后,程序就可得到全部可能的解。细节见下面的程序。
【程序1】
# include < stdio.h>
void main()
{ int a,b,c,d,e,f;
for (a=1;a< =6;a++)
for (b=1;b< =6;b++) {
if (b==a) continue;
for (c=1;c< =6;c++) {
if (c==a)||(c==b) continue;
for (d=1;d< =6;d++) {
if (d==a)||(d==b)||(d==c) continue;
for (e=1;e< =6;e++) {
if (e==a)||(e==b)||(e==c)||(e==d) continue;
f=21-(a+b+c+d+e);
if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {
printf(“%6d,a);
printf(“%4d%4d”,b,f);
printf(“%2d%4d%4d”,c,d,e);
scanf(“%*c”);
}
}
}
}
}
}
按穷举法编写的程序通常不能适应变化的情况。如问题改成有9个变量排成三角形,每条边有4个变量的情况,程序的循环重数就要相应改变。
对一组数穷尽所有排列,还有更直接的方法。将一个排列看作一个长整数,则所有排列对应着一组整数。将这组整数按从小到大的顺序排列排成一个整数,从对应最小的整数开始。按数列的递增顺序逐一列举每个排列对应的每个整数,这能更有效地完成排列的穷举。从一个排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为1,2,4,6,5,3,并令其对应的长整数为124653。要寻找比长整数124653更大的排列,可从该排列的最后一个数字顺序向前逐位考察,当发现排列中的某个数字比它前一个数字大时,如本例中的6比它的前一位数字4大,这说明还有对应更大整数的排列。但为了顺序从小到大列举出所有的排列,不能立即调整得太大,如本例中将数字6与数字4交换得到的排列126453就不是排列124653的下一个排列。为了得到排列124653的下一个排列,应从已经考察过的那部分数字中选出比数字大,但又是它们中最小的那一个数字,比如数字5,与数字4交换。该数字也是从后向前考察过程中第一个比4大的数字。5与4交换后,得到排列125643。在前面数字1,2,5固定的情况下,还应选择对应最小整数的那个排列,为此还需将后面那部分数字的排列顺序颠倒,如将数字6,4,3的排列顺序颠倒,得到排列1,2,5,3,4,6,这才是排列1,2,4,6,5,3的下一个排列。按以上想法编写的程序如下。
【程序2】
# include < stdio.h>
# define SIDE_N 3
# define LENGTH 3
# define VARIABLES 6
int A,B,C,D,E,F;
int *pt[]={&A,&B,&C,&D,&E,&F};
int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A};
int side_total[SIDE_N];
main{}
{ int i,j,t,equal;
for (j=0;j< VARIABLES;j++)
*pt[j]=j+1;
while(1)
{ for (i=0;i< SIDE_N;i++)
{ for (t=j=0;j< LENGTH;j++)
t+=*side[i][j];
side_total[i]=t;
}
for (equal=1,i=0;equal&&i< SIDE_N-1;i++)
if (side_total[i]!=side_total[i+1] equal=0;
if (equal)
{ for (i=1;i< VARIABLES;i++)
printf(“%4d”,*pt[i]);
printf(“\n”);
scanf(“%*c”);
}
for (j=VARIABLES-1;j>0;j--)
if (*pt[j]>*pt[j-1]) break;
if (j==0) break;
for (i=VARIABLES-1;i>=j;i--)
if (*pt[i]>*pt[i-1]) break;
t=*pt[j-1];* pt[j-1] =* pt[i]; *pt[i]=t;
for (i=VARIABLES-1;i>j;i--,j++)
{ t=*pt[j]; *pt[j] =* pt[i]; *pt[i]=t; }
}
}
从上述问题解决的方法中,最重要的因素就是确定某种方法来确定所有的候选解。下面再用一个示例来加以说明。
【问题】 背包问题
问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
设n个物品的重量和价值分别存储于数组w[ ]和v[ ]中,限制重量为tw。考虑一个n元组(x0,x1,…,xn-1),其中xi=0 表示第i个物品没有选取,而xi=1则表示第i个物品被选取。显然这个n元组等价于一个选择方案。用枚举法解决背包问题,需要枚举所有的选取方案,而根据上述方法,我们只要枚举所有的n元组,就可以得到问题的解。
显然,每个分量取值为0或1的n元组的个数共为2n个。而每个n元组其实对应了一个长度为n的二进制数,且这些二进制数的取值范围为0~2n-1。因此,如果把0~2n-1分别转化为相应的二进制数,则可以得到我们所需要的2n个n元组。
【算法】
maxv=0;
for (i=0;i< 2n;i++)
{ B[0..n-1]=0;
把i转化为二进制数,存储于数组B中;
temp_w=0;
temp_v=0;
for (j=0;j< n;j++)
{ if (B[j]==1)
{ temp_w=temp_w+w[j];
temp_v=temp_v+v[j];
}
if ((temp_w< =tw)&&(temp_v>maxv))
{ maxv=temp_v;
保存该B数组;
}
}
}

# 回复:常用算法设计方法(转贴)-> 2004-11-19 12:02 PM 三、递推法
三、递推法
递推法是利用问题本身所具有的一种递推关系求问题解的一种方法。设要求问题规模为N的解,当N=1时,解或为已知,或能非常方便地得到解。能采用递推法构造算法的问题有重要的递推性质,即当得到问题规模为i-1的解后,由问题的递推性质,能从已求得的规模为1,2,…,i-1的一系列解,构造出问题规模为I的解。这样,程序可从i=0或i=1出发,重复地,由已知至i-1规模的解,通过递推,获得规模为i的解,直至得到规模为N的解。
【问题】 阶乘计算
问题描述:编写程序,对给定的n(n≦100),计算并输出k的阶乘k!(k=1,2,…,n)的全部有效数字。
由于要求的整数可能大大超出一般整数的位数,程序用一维数组存储长整数,存储长整数数组的每个元素只存储长整数的一位数字。如有m位成整数N用数组a[ ]存储:
N=a[m]×10m-1+a[m-1]×10m-2+ … +a[2]×101+a[1]×100
并用a[0]存储长整数N的位数m,即a[0]=m。按上述约定,数组的每个元素存储k的阶乘k!的一位数字,并从低位到高位依次存于数组的第二个元素、第三个元素……。例如,5!=120,在数组中的存储形式为:
3 0 2 1 ……
首元素3表示长整数是一个3位数,接着是低位到高位依次是0、2、1,表示成整数120。
计算阶乘k!可采用对已求得的阶乘(k-1)!连续累加k-1次后求得。例如,已知4!=24,计算5!,可对原来的24累加4次24后得到120。细节见以下程序。
# include < stdio.h>
# include < malloc.h>
# define MAXN 1000
void pnext(int a[ ],int k)
{ int *b,m=a[0],i,j,r,carry;
b=(int * ) malloc(sizeof(int)* (m+1));
for ( i=1;i< =m;i++) b[i]=a[i];
for ( j=1;j< =k;j++)
{ for ( carry=0,i=1;i< =m;i++)
{ r=(i< a[0]?a[i]+b[i]:a[i])+carry;
a[i]=r%10;
carry=r/10;
}
if (carry) a[++m]=carry;
}
free(b);
a[0]=m;
}

void write(int *a,int k)
{ int i;
printf(“%4d!=”,k);
for (i=a[0];i>0;i--)
printf(“%d”,a[i]);
printf(“\n\n”);
}

void main()
{ int a[MAXN],n,k;
printf(“Enter the number n: “);
scanf(“%d”,&n);
a[0]=1;
a[1]=1;
write(a,1);
for (k=2;k< =n;k++)
{ pnext(a,k);
write(a,k);
getchar();
}
}

# 回复:常用算法设计方法(转贴)-> 2004-11-19 12:03 PM 四、递归
四、递归
递归是设计和描述算法的一种有力的工具,由于它在复杂算法的描述中被经常采用,为此在进一步介绍其他算法设计方法之前先讨论它。
能采用递归描述的算法通常有这样的特征:为求解规模为N的问题,设法将它分解成规模较小的问题,然后从这些小问题的解方便地构造出大问题的解,并且这些规模较小的问题也能采用同样的分解和综合方法,分解成规模更小的问题,并从这些更小问题的解构造出规模较大问题的解。特别地,当规模N=1时,能直接得解。
【问题】 编写计算斐波那契(Fibonacci)数列的第n项函数fib(n)。
斐波那契数列为:0、1、1、2、3、……,即:
fib(0)=0;
fib(1)=1;
fib(n)=fib(n-1)+fib(n-2) (当n>1时)。
写成递归函数有:
int fib(int n)
{ if (n==0) return 0;
if (n==1) return 1;
if (n>1) return fib(n-1)+fib(n-2);
}
递归算法的执行过程分递推和回归两个阶段。在递推阶段,把较复杂的问题(规模为n)的求解推到比原问题简单一些的问题(规模小于n)的求解。例如上例中,求解fib(n),把它推到求解fib(n-1)和fib(n-2)。也就是说,为计算fib(n),必须先计算fib(n-1)和fib(n-2),而计算fib(n-1)和fib(n-2),又必须先计算fib(n-3)和fib(n-4)。依次类推,直至计算fib(1)和fib(0),分别能立即得到结果1和0。在递推阶段,必须要有终止递归的情况。例如在函数fib中,当n为1和0的情况。
在回归阶段,当获得最简单情况的解后,逐级返回,依次得到稍复杂问题的解,例如得到fib(1)和fib(0)后,返回得到fib(2)的结果,……,在得到了fib(n-1)和fib(n-2)的结果后,返回得到fib(n)的结果。
在编写递归函数时要注意,函数中的局部变量和参数知识局限于当前调用层,当递推进入“简单问题”层时,原来层次上的参数和局部变量便被隐蔽起来。在一系列“简单问题”层,它们各有自己的参数和局部变量。
由于递归引起一系列的函数调用,并且可能会有一系列的重复计算,递归算法的执行效率相对较低。当某个递归算法能较方便地转换成递推算法时,通常按递推算法编写程序。例如上例计算斐波那契数列的第n项的函数fib(n)应采用递推算法,即从斐波那契数列的前两项出发,逐次由前两项计算出下一项,直至计算出要求的第n项。
【问题】 组合问题
问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。例如n=5,r=3的所有组合为: (1)5、4、3 (2)5、4、2 (3)5、4、1
(4)5、3、2 (5)5、3、1 (6)5、2、1
(7)4、3、2 (8)4、3、1 (9)4、2、1
(10)3、2、1
分析所列的10个组合,可以采用这样的递归思想来考虑求组合函数的算法。设函数为void comb(int m,int k)为找出从自然数1、2、……、m中任取k个数的所有组合。当组合的第一个数字选定时,其后的数字是从余下的m-1个数中取k-1数的组合。这就将求m个数中取k个数的组合问题转化成求m-1个数中取k-1个数的组合问题。设函数引入工作数组a[ ]存放求出的组合的数字,约定函数将确定的k个数字组合的第一个数字放在a[k]中,当一个组合求出后,才将a[ ]中的一个组合输出。第一个数可以是m、m-1、……、k,函数将确定组合的第一个数字放入数组后,有两种可能的选择,因还未去顶组合的其余元素,继续递归去确定;或因已确定了组合的全部元素,输出这个组合。细节见以下程序中的函数comb。
【程序】
# include < stdio.h>
# define MAXN 100
int a[MAXN];
void comb(int m,int k)
{ int i,j;
for (i=m;i>=k;i--)
{ a[k]=i;
if (k>1)
comb(i-1,k-1);
else
{ for (j=a[0];j>0;j--)
printf(“%4d”,a[j]);
printf(“\n”);
}
}
}

void main()
{ a[0]=3;
comb(5,3);
}
【问题】 背包问题
问题描述:有不同价值、不同重量的物品n件,求从这n件物品中选取一部分物品的选择方案,使选中物品的总重量不超过指定的限制重量,但选中物品的价值之和最大。
设n件物品的重量分别为w0、w1、…、wn-1,物品的价值分别为v0、v1、…、vn-1。采用递归寻找物品的选择方案。设前面已有了多种选择的方案,并保留了其中总价值最大的方案于数组option[ ],该方案的总价值存于变量maxv。当前正在考察新方案,其物品选择情况保存于数组cop[ ]。假定当前方案已考虑了前i-1件物品,现在要考虑第i件物品;当前方案已包含的物品的重量之和为tw;至此,若其余物品都选择是可能的话,本方案能达到的总价值的期望值为tv。算法引入tv是当一旦当前方案的总价值的期望值也小于前面方案的总价值maxv时,继续考察当前方案变成无意义的工作,应终止当前方案,立即去考察下一个方案。因为当方案的总价值不比maxv大时,该方案不会被再考察,这同时保证函数后找到的方案一定会比前面的方案更好。
对于第i件物品的选择考虑有两种可能:
(1) 考虑物品i被选择,这种可能性仅当包含它不会超过方案总重量限制时才是可行的。选中后,继续递归去考虑其余物品的选择。
(2) 考虑物品i不被选择,这种可能性仅当不包含物品i也有可能会找到价值更大的方案的情况。
按以上思想写出递归算法如下:
try(物品i,当前选择已达到的重量和,本方案可能达到的总价值tv)
{ /*考虑物品i包含在当前方案中的可能性*/
if(包含物品i是可以接受的)
{ 将物品i包含在当前方案中;
if (i< n-1)
try(i+1,tw+物品i的重量,tv);
else
/*又一个完整方案,因为它比前面的方案好,以它作为最佳方案*/
以当前方案作为临时最佳方案保存;
恢复物品i不包含状态;
}
/*考虑物品i不包含在当前方案中的可能性*/
if (不包含物品i仅是可男考虑的)
if (i< n-1)
try(i+1,tw,tv-物品i的价值);
else
/*又一个完整方案,因它比前面的方案好,以它作为最佳方案*/
以当前方案作为临时最佳方案保存;
}
为了理解上述算法,特举以下实例。设有4件物品,它们的重量和价值见表:
物品 0 1 2 3
重量 5 3 2 1
价值 4 4 3 1

并设限制重量为7。则按以上算法,下图表示找解过程。由图知,一旦找到一个解,算法就进一步找更好的佳。如能判定某个查找分支不会找到更好的解,算法不会在该分支继续查找,而是立即终止该分支,并去考察下一个分支。

按上述算法编写函数和程序如下:
【程序】
# include < stdio.h>
# define N 100
double limitW,totV,maxV;
int option[N],cop[N];
struct { double weight;
double value;
}a[N];
int n;
void find(int i,double tw,double tv)
{ int k;
/*考虑物品i包含在当前方案中的可能性*/
if (tw+a[i].weight< =limitW)
{ cop[i]=1;
if (i< n-1) find(i+1,tw+a[i].weight,tv);
else
{ for (k=0;k< n;k++)
option[k]=cop[k];
maxv=tv;
}
cop[i]=0;
}
/*考虑物品i不包含在当前方案中的可能性*/
if (tv-a[i].value>maxV)
if (i< n-1) find(i+1,tw,tv-a[i].value);
else
{ for (k=0;k< n;k++)
option[k]=cop[k];
maxv=tv-a[i].value;
}
}

void main()
{ int k;
double w,v;
printf(“输入物品种数\n”);
scanf((“%d”,&n);
printf(“输入各物品的重量和价值\n”);
for (totv=0.0,k=0;k< n;k++)
{ scanf(“%1f%1f”,&w,&v);
a[k].weight=w;
a[k].value=v;
totV+=V;
}
printf(“输入限制重量\n”);
scanf(“%1f”,&limitV);
maxv=0.0;
for (k=0;k< n;k++) cop[k]=0;
find(0,0.0,totV);
for (k=0;k< n;k++)
if (option[k]) printf(“%4d”,k+1);
printf(“\n总价值为%.2f\n”,maxv);
}
作为对比,下面以同样的解题思想,考虑非递归的程序解。为了提高找解速度,程序不是简单地逐一生成所有候选解,而是从每个物品对候选解的影响来形成值得进一步考虑的候选解,一个候选解是通过依次考察每个物品形成的。对物品i的考察有这样几种情况:当该物品被包含在候选解中依旧满足解的总重量的限制,该物品被包含在候选解中是应该继续考虑的;反之,该物品不应该包括在当前正在形成的候选解中。同样地,仅当物品不被包括在候选解中,还是有可能找到比目前临时最佳解更好的候选解时,才去考虑该物品不被包括在候选解中;反之,该物品不包括在当前候选解中的方案也不应继续考虑。对于任一值得继续考虑的方案,程序就去进一步考虑下一个物品。
【程序】
# include < stdio.h>
# define N 100
double limitW;
int cop[N];
struct ele { double weight;
double value;
} a[N];
int k,n;
struct { int flg;
double tw;
double tv;
}twv[N];
void next(int i,double tw,double tv)
{ twv[i].flg=1;
twv[i].tw=tw;
twv[i].tv=tv;
}
double find(struct ele *a,int n)
{ int i,k,f;
double maxv,tw,tv,totv;
maxv=0;
for (totv=0.0,k=0;k< n;k++)
totv+=a[k].value;
next(0,0.0,totv);
i=0;
While (i>=0)
{ f=twv[i].flg;
tw=twv[i].tw;
tv=twv[i].tv;
switch(f)
{ case 1: twv[i].flg++;
if (tw+a[i].weight< =limitW)
if (i< n-1)
{ next(i+1,tw+a[i].weight,tv);
i++;
}
else
{ maxv=tv;
for (k=0;k< n;k++)
cop[k]=twv[k].flg!=0;
}
break;
case 0: i--;
break;
default: twv[i].flg=0;
if (tv-a[i].value>maxv)
if (i< n-1)
{ next(i+1,tw,tv-a[i].value);
i++;
}
else
{ maxv=tv-a[i].value;
for (k=0;k< n;k++)
cop[k]=twv[k].flg!=0;
}
break;
}
}
return maxv;
}

void main()
{ double maxv;
printf(“输入物品种数\n”);
scanf((“%d”,&n);
printf(“输入限制重量\n”);
scanf(“%1f”,&limitW);
printf(“输入各物品的重量和价值\n”);
for (k=0;k< n;k++)
scanf(“%1f%1f”,&a[k].weight,&a[k].value);
maxv=find(a,n);
printf(“\n选中的物品为\n”);
for (k=0;k< n;k++)
if (option[k]) printf(“%4d”,k+1);
printf(“\n总价值为%.2f\n”,maxv);
}

# 回复:常用算法设计方法(转贴)-> 2004-11-19 12:08 PM 五、回溯法
五、回溯法
回溯法也称为试探法,该方法首先暂时放弃关于问题规模大小的限制,并将问题的候选解按某种顺序逐一枚举和检验。当发现当前候选解不可能是解时,就选择下一个候选解;倘若当前候选解除了还不满足问题规模要求外,满足所有其他要求时,继续扩大当前候选解的规模,并继续试探。如果当前候选解满足包括问题规模在内的所有要求时,该候选解就是问题的一个解。在回溯法中,放弃当前候选解,寻找下一个候选解的过程称为回溯。扩大当前候选解的规模,以继续试探的过程称为向前试探。
1、回溯法的一般描述
可用回溯法求解的问题P,通常要能表达为:对于已知的由n元组(x1,x2,…,xn)组成的一个状态空间E={(x1,x2,…,xn)∣xi∈Si ,i=1,2,…,n},给定关于n元组中的一个分量的一个约束集D,要求E中满足D的全部约束条件的所有n元组。其中Si是分量xi的定义域,且 |Si| 有限,i=1,2,…,n。我们称E中满足D的全部约束条件的任一n元组为问题P的一个解。
解问题P的最朴素的方法就是枚举法,即对E中的所有n元组逐一地检测其是否满足D的全部约束,若满足,则为问题P的一个解。但显然,其计算量是相当大的。
我们发现,对于许多问题,所给定的约束集D具有完备性,即i元组(x1,x2,…,xi)满足D中仅涉及到x1,x2,…,xi的所有约束意味着j(j< i)元组(x1,x2,…,xj)一定也满足D中仅涉及到x1,x2,…,xj的所有约束,i=1,2,…,n。换句话说,只要存在0≤j≤n-1,使得(x1,x2,…,xj)违反D中仅涉及到x1,x2,…,xj的约束之一,则以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)一定也违反D中仅涉及到x1,x2,…,xi的一个约束,n≥i>j。因此,对于约束集D具有完备性的问题P,一旦检测断定某个j元组(x1,x2,…,xj)违反D中仅涉及x1,x2,…,xj的一个约束,就可以肯定,以(x1,x2,…,xj)为前缀的任何n元组(x1,x2,…,xj,xj+1,…,xn)都不会是问题P的解,因而就不必去搜索它们、检测它们。回溯法正是针对这类问题,利用这类问题的上述性质而提出来的比枚举法效率更高的算法。
回溯法首先将问题P的n元组的状态空间E表示成一棵高为n的带权有序树T,把在E中求问题P的所有解转化为在T中搜索问题P的所有解。树T类似于检索树,它可以这样构造:
设Si中的元素可排成xi(1) ,xi(2) ,…,xi(mi-1) ,|Si| =mi,i=1,2,…,n。从根开始,让T的第I层的每一个结点都有mi个儿子。这mi个儿子到它们的双亲的边,按从左到右的次序,分别带权xi+1(1) ,xi+1(2) ,…,xi+1(mi) ,i=0,1,2,…,n-1。照这种构造方式,E中的一个n元组(x1,x2,…,xn)对应于T中的一个叶子结点,T的根到这个叶子结点的路径上依次的n条边的权分别为x1,x2,…,xn,反之亦然。另外,对于任意的0≤i≤n-1,E中n元组(x1,x2,…,xn)的一个前缀I元组(x1,x2,…,xi)对应于T中的一个非叶子结点,T的根到这个非叶子结点的路径上依次的I条边的权分别为x1,x2,…,xi,反之亦然。特别,E中的任意一个n元组的空前缀(),对应于T的根。
因而,在E中寻找问题P的一个解等价于在T中搜索一个叶子结点,要求从T的根到该叶子结点的路径上依次的n条边相应带的n个权x1,x2,…,xn满足约束集D的全部约束。在T中搜索所要求的叶子结点,很自然的一种方式是从根出发,按深度优先的策略逐步深入,即依次搜索满足约束条件的前缀1元组(x1i)、前缀2元组(x1,x2)、…,前缀I元组(x1,x2,…,xi),…,直到i=n为止。
在回溯法中,上述引入的树被称为问题P的状态空间树;树T上任意一个结点被称为问题P的状态结点;树T上的任意一个叶子结点被称为问题P的一个解状态结点;树T上满足约束集D的全部约束的任意一个叶子结点被称为问题P的一个回答状态结点,它对应于问题P的一个解。
【问题】 组合问题
问题描述:找出从自然数1、2、……、n中任取r个数的所有组合。
例如n=5,r=3的所有组合为:
(1)1、2、3 (2)1、2、4 (3)1、2、5
(4)1、3、4 (5)1、3、5 (6)1、4、5
(7)2、3、4 (8)2、3、5 (9)2、4、5
(10)3、4、5
则该问题的状态空间为:
E={(x1,x2,x3)∣xi∈S ,i=1,2,3 } 其中:S={1,2,3,4,5}
约束集为: x1< x2< x3
显然该约束集具有完备性。
问题的状态空间树T:













2、回溯法的方法
对于具有完备约束集D的一般问题P及其相应的状态空间树T,利用T的层次结构和D的完备性,在T中搜索问题P的所有解的回溯法可以形象地描述为:
从T的根出发,按深度优先的策略,系统地搜索以其为根的子树中可能包含着回答结点的所有状态结点,而跳过对肯定不含回答结点的所有子树的搜索,以提高搜索效率。具体地说,当搜索按深度优先策略到达一个满足D中所有有关约束的状态结点时,即“激活”该状态结点,以便继续往深层搜索;否则跳过对以该状态结点为根的子树的搜索,而一边逐层地向该状态结点的祖先结点回溯,一边“杀死”其儿子结点已被搜索遍的祖先结点,直到遇到其儿子结点未被搜索遍的祖先结点,即转向其未被搜索的一个儿子结点继续搜索。
在搜索过程中,只要所激活的状态结点又满足终结条件,那么它就是回答结点,应该把它输出或保存。由于在回溯法求解问题时,一般要求出问题的所有解,因此在得到回答结点后,同时也要进行回溯,以便得到问题的其他解,直至回溯到T的根且根的所有儿子结点均已被搜索过为止。
例如在组合问题中,从T的根出发深度优先遍历该树。当遍历到结点(1,2)时,虽然它满足约束条件,但还不是回答结点,则应继续深度遍历;当遍历到叶子结点(1,2,5)时,由于它已是一个回答结点,则保存(或输出)该结点,并回溯到其双亲结点,继续深度遍历;当遍历到结点(1,5)时,由于它已是叶子结点,但不满足约束条件,故也需回溯。
3、回溯法的一般流程和技术
在用回溯法求解有关问题的过程中,一般是一边建树,一边遍历该树。在回溯法中我们一般采用非递归方法。下面,我们给出回溯法的非递归算法的一般流程:

在用回溯法求解问题,也即在遍历状态空间树的过程中,如果采用非递归方法,则我们一般要用到栈的数据结构。这时,不仅可以用栈来表示正在遍历的树的结点,而且可以很方便地表示建立孩子结点和回溯过程。
例如在组合问题中,我们用一个一维数组Stack[ ]表示栈。开始栈空,则表示了树的根结点。如果元素1进栈,则表示建立并遍历(1)结点;这时如果元素2进栈,则表示建立并遍历(1,2)结点;元素3再进栈,则表示建立并遍历(1,2,3)结点。这时可以判断它满足所有约束条件,是问题的一个解,输出(或保存)。这时只要栈顶元素(3)出栈,即表示从结点(1,2,3)回溯到结点(1,2)。
【问题】 组合问题
问题描述:找出从自然数1,2,…,n中任取r个数的所有组合。
采用回溯法找问题的解,将找到的组合以从小到大顺序存于a[0],a[1],…,a[r-1]中,组合的元素满足以下性质:
(1) a[i+1]>a[i],后一个数字比前一个大;
(2) a[i]-i< =n-r+1。
按回溯法的思想,找解过程可以叙述如下:
首先放弃组合数个数为r的条件,候选组合从只有一个数字1开始。因该候选解满足除问题规模之外的全部条件,扩大其规模,并使其满足上述条件(1),候选组合改为1,2。继续这一过程,得到候选组合1,2,3。该候选解满足包括问题规模在内的全部条件,因而是一个解。在该解的基础上,选下一个候选解,因a[2]上的3调整为4,以及以后调整为5都满足问题的全部要求,得到解1,2,4和1,2,5。由于对5不能再作调整,就要从a[2]回溯到a[1],这时,a[1]=2,可以调整为3,并向前试探,得到解1,3,4。重复上述向前试探和向后回溯,直至要从a[0]再回溯时,说明已经找完问题的全部解。按上述思想写成程序如下:
【程序】
# define MAXN 100
int a[MAXN];
void comb(int m,int r)
{ int i,j;
i=0;
a[i]=1;
do {
if (a[i]-i< =m-r+1
{ if (i==r-1)
{ for (j=0;j< r;j++)
printf(“%4d”,a[j]);
printf(“\n”);
}
a[i]++;
continue;
}
else
{ if (i==0)
return;
a[--i]++;
}
} while (1)
}

main()
{ comb(5,3);
}
【问题】 填字游戏
问题描述:在3×3个方格的方阵中要填入数字1到N(N≥10)内的某9个数字,每个方格填一个整数,似的所有相邻两个方格内的两个整数之和为质数。试求出所有满足这个要求的各种数字填法。
可用试探发找到问题的解,即从第一个方格开始,为当前方格寻找一个合理的整数填入,并在当前位置正确填入后,为下一方格寻找可填入的合理整数。如不能为当前方格找到一个合理的可填证书,就要回退到前一方格,调整前一方格的填入数。当第九个方格也填入合理的整数后,就找到了一个解,将该解输出,并调整第九个的填入的整数,寻找下一个解。
为找到一个满足要求的9个数的填法,从还未填一个数开始,按某种顺序(如从小到大的顺序)每次在当前位置填入一个整数,然后检查当前填入的整数是否能满足要求。在满足要求的情况下,继续用同样的方法为下一方格填入整数。如果最近填入的整数不能满足要求,就改变填入的整数。如对当前方格试尽所有可能的整数,都不能满足要求,就得回退到前一方格,并调整前一方格填入的整数。如此重复执行扩展、检查或调整、检查,直到找到一个满足问题要求的解,将解输出。
回溯法找一个解的算法:
{ int m=0,ok=1;
int n=8;
do{
if (ok) 扩展;
else 调整;
ok=检查前m个整数填放的合理性;
} while ((!ok||m!=n)&&(m!=0))
if (m!=0) 输出解;
else 输出无解报告;
}
如果程序要找全部解,则在将找到的解输出后,应继续调整最后位置上填放的整数,试图去找下一个解。相应的算法如下:
回溯法找全部解的算法:
{ int m=0,ok=1;
int n=8;
do{
if (ok)
{ if (m==n)
{ 输出解;
调整;
}
else 扩展;
}
else 调整;
ok=检查前m个整数填放的合理性;
} while (m!=0);
}
为了确保程序能够终止,调整时必须保证曾被放弃过的填数序列不会再次实验,即要求按某种有许模型生成填数序列。给解的候选者设定一个被检验的顺序,按这个顺序逐一形成候选者并检验。从小到大或从大到小,都是可以采用的方法。如扩展时,先在新位置填入整数1,调整时,找当前候选解中下一个还未被使用过的整数。将上述扩展、调整、检验都编写成程序,细节见以下找全部解的程序。
【程序】
# include < stdio.h>
# define N 12
void write(int a[ ])
{ int i,j;
for (i=0;i< 3;i++)
{ for (j=0;j< 3;j++)
printf(“%3d”,a[3*i+j]);
printf(“\n”);
}
scanf(“%*c”);
}

int b[N+1];
int a[10];
int isprime(int m)
{ int i;
int primes[ ]={2,3,5,7,11,17,19,23,29,-1};
if (m==1||m%2=0) return 0;
for (i=0;primes[i]>0;i++)
if (m==primes[i]) return 1;
for (i=3;i*i< =m;)
{ if (m%i==0) return 0;
i+=2;
}
return 1;
}

int checkmatrix[ ][3]={ {-1},{0,-1},{1,-1},{0,-1},{1,3,-1},
{2,4,-1},{3,-1},{4,6,-1},{5,7,-1}};
int selectnum(int start)
{ int j;
for (j=start;j< =N;j++)
if (b[j]) return j
return 0;
}

int check(int pos)
{ int i,j;
if (pos< 0) return 0;
for (i=0;(j=checkmatrix[pos][i])>=0;i++)
if (!isprime(a[pos]+a[j])
return 0;
return 1;
}

int extend(int pos)
{ a[++pos]=selectnum(1);
b[a][pos]]=0;
return pos;
}

int change(int pos)
{ int j;
while (pos>=0&&(j=selectnum(a[pos]+1))==0)
b[a[pos--]]=1;
if (pos< 0) return –1
b[a[pos]]=1;
a[pos]=j;
b[j]=0;
return pos;
}

void find()
{ int ok=0,pos=0;
a[pos]=1;
b[a[pos]]=0;
do {
if (ok)
if (pos==8)
{ write(a);
pos=change(pos);
}
else pos=extend(pos);
else pos=change(pos);
ok=check(pos);
} while (pos>=0)
}

void main()
{ int i;
for (i=1;i< =N;i++)
b[i]=1;
find();
}
【问题】 n皇后问题
问题描述:求出在一个n×n的棋盘上,放置n个不能互相捕捉的国际象棋“皇后”的所有布局。
这是来源于国际象棋的一个问题。皇后可以沿着纵横和两条斜线4个方向相互捕捉。如图所示,一个皇后放在棋盘的第4行第3列位置上,则棋盘上凡打“×”的位置上的皇后就能与这个皇后相互捕捉。

1 2 3 4 5 6 7 8
× ×
× × ×
× × ×
× × Q × × × × ×
× × ×
× × ×
× ×
× ×
从图中可以得到以下启示:一个合适的解应是在每列、每行上只有一个皇后,且一条斜线上也只有一个皇后。
求解过程从空配置开始。在第1列至第m列为合理配置的基础上,再配置第m+1列,直至第n列配置也是合理时,就找到了一个解。接着改变第n列配置,希望获得下一个解。另外,在任一列上,可能有n种配置。开始时配置在第1行,以后改变时,顺次选择第2行、第3行、…、直到第n行。当第n行配置也找不到一个合理的配置时,就要回溯,去改变前一列的配置。得到求解皇后问题的算法如下:
{ 输入棋盘大小值n;
m=0;
good=1;
do {
if (good)
if (m==n)
{ 输出解;
改变之,形成下一个候选解;
}
else 扩展当前候选接至下一列;
else 改变之,形成下一个候选解;
good=检查当前候选解的合理性;
} while (m!=0);
}
在编写程序之前,先确定边式棋盘的数据结构。比较直观的方法是采用一个二维数组,但仔细观察就会发现,这种表示方法给调整候选解及检查其合理性带来困难。更好的方法乃是尽可能直接表示那些常用的信息。对于本题来说,“常用信息”并不是皇后的具体位置,而是“一个皇后是否已经在某行和某条斜线合理地安置好了”。因在某一列上恰好放一个皇后,引入一个一维数组(col[ ]),值col[i]表示在棋盘第i列、col[i]行有一个皇后。例如:col[3]=4,就表示在棋盘的第3列、第4行上有一个皇后。另外,为了使程序在找完了全部解后回溯到最初位置,设定col[0]的初值为0当回溯到第0列时,说明程序已求得全部解,结束程序运行。
为使程序在检查皇后配置的合理性方面简易方便,引入以下三个工作数组:
(1) 数组a[ ],a[k]表示第k行上还没有皇后;
(2) 数组b[ ],b[k]表示第k列右高左低斜线上没有皇后;
(3) 数组 c[ ],c[k]表示第k列左高右低斜线上没有皇后;
棋盘中同一右高左低斜线上的方格,他们的行号与列号之和相同;同一左高右低斜线上的方格,他们的行号与列号之差均相同。
初始时,所有行和斜线上均没有皇后,从第1列的第1行配置第一个皇后开始,在第m列col[m]行放置了一个合理的皇后后,准备考察第m+1列时,在数组a[ ]、b[ ]和c[ ]中为第m列,col[m]行的位置设定有皇后标志;当从第m列回溯到第m-1列,并准备调整第m-1列的皇后配置时,清除在数组a[ ]、b[ ]和c[ ]中设置的关于第m-1列,col[m-1]行有皇后的标志。一个皇后在m列,col[m]行方格内配置是合理的,由数组a[ ]、b[ ]和c[ ]对应位置的值都为1来确定。细节见以下程序:
【程序】
# include < stdio.h>
# include < stdlib.h>
# define MAXN 20
int n,m,good;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];

void main()
{ int j;
char awn;
printf(“Enter n: “); scanf(“%d”,&n);
for (j=0;j< =n;j++) a[j]=1;
for (j=0;j< =2*n;j++) cb[j]=c[j]=1;
m=1; col[1]=1; good=1; col[0]=0;
do {
if (good)
if (m==n)
{ printf(“列\t行”);
for (j=1;j< =n;j++)
printf(“%3d\t%d\n”,j,col[j]);
printf(“Enter a character (Q/q for exit)!\n”);
scanf(“%c”,&awn);
if (awn==’Q’||awn==’q’) exit(0);
while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
else
{ a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0;
col[++m]=1;
}
else
{ while (col[m]==n)
{ m--;
a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1;
}
col[m]++;
}
good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]];
} while (m!=0);
}
试探法找解算法也常常被编写成递归函数,下面两程序中的函数queen_all()和函数queen_one()能分别用来解皇后问题的全部解和一个解。
【程序】
# include < stdio.h>
# include < stdlib.h>
# define MAXN 20
int n;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
void main()
{ int j;
printf(“Enter n: “); scanf(“%d”,&n);
for (j=0;j< =n;j++) a[j]=1;
for (j=0;j< =2*n;j++) cb[j]=c[j]=1;
queen_all(1,n);
}

void queen_all(int k,int n)
{ int i,j;
char awn;
for (i=1;i< =n;i++)
if (a[i]&&b[k+i]&&c[n+k-i])
{ col[k]=i;
a[i]=b[k+i]=c[n+k-i]=0;
if (k==n)
{ printf(“列\t行”);
for (j=1;j< =n;j++)
printf(“%3d\t%d\n”,j,col[j]);
printf(“Enter a character (Q/q for exit)!\n”);
scanf(“%c”,&awn);
if (awn==’Q’||awn==’q’) exit(0);
}
queen_all(k+1,n);
a[i]=b[k+i]=c[n+k-i];
}
}
采用递归方法找一个解与找全部解稍有不同,在找一个解的算法中,递归算法要对当前候选解最终是否能成为解要有回答。当它成为最终解时,递归函数就不再递归试探,立即返回;若不能成为解,就得继续试探。设函数queen_one()返回1表示找到解,返回0表示当前候选解不能成为解。细节见以下函数。
【程序】
# define MAXN 20
int n;
int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1];
int queen_one(int k,int n)
{ int i,found;
i=found=0;
While (!found&&i< n)
{ i++;
if (a[i]&&b[k+i]&&c[n+k-i])
{ col[k]=i;
a[i]=b[k+i]=c[n+k-i]=0;
if (k==n) return 1;
else
found=queen_one(k+1,n);
a[i]=b[k+i]=c[n+k-i]=1;
}
}
return found;
}

# 回复:常用算法设计方法(转贴)-> 2004-11-19 12:09 PM 六、贪婪法
六、贪婪法
贪婪法是一种不追求最优解,只希望得到较为满意解的方法。贪婪法一般可以快速得到满意的解,因为它省去了为找最优解要穷尽所有可能而必须耗费的大量时间。贪婪法常以当前情况为基础作最优选择,而不考虑各种可能的整体情况,所以贪婪法不要回溯。
例如平时购物找钱时,为使找回的零钱的硬币数最少,不考虑找零钱的所有各种发表方案,而是从最大面值的币种开始,按递减的顺序考虑各币种,先尽量用大面值的币种,当不足大面值币种的金额时才去考虑下一种较小面值的币种。这就是在使用贪婪法。这种方法在这里总是最优,是因为银行对其发行的硬币种类和硬币面值的巧妙安排。如只有面值分别为1、5和11单位的硬币,而希望找回总额为15单位的硬币。按贪婪算法,应找1个11单位面值的硬币和4个1单位面值的硬币,共找回5个硬币。但最优的解应是3个5单位面值的硬币。
【问题】 装箱问题
问题描述:装箱问题可简述如下:设有编号为0、1、…、n-1的n种物品,体积分别为v0、v1、…、vn-1。将这n种物品装到容量都为V的若干箱子里。约定这n种物品的体积均不超过V,即对于0≤i<n,有0<vi≤V。不同的装箱方案所需要的箱子数目可能不同。装箱问题要求使装尽这n种物品的箱子数要少。
若考察将n种物品的集合分划成n个或小于n个物品的所有子集,最优解就可以找到。但所有可能划分的总数太大。对适当大的n,找出所有可能的划分要花费的时间是无法承受的。为此,对装箱问题采用非常简单的近似算法,即贪婪法。该算法依次将物品放到它第一个能放进去的箱子中,该算法虽不能保证找到最优解,但还是能找到非常好的解。不失一般性,设n件物品的体积是按从大到小排好序的,即有v0≥v1≥…≥vn-1。如不满足上述要求,只要先对这n件物品按它们的体积从大到小排序,然后按排序结果对物品重新编号即可。装箱算法简单描述如下:
{ 输入箱子的容积;
输入物品种数n;
按体积从大到小顺序,输入各物品的体积;
预置已用箱子链为空;
预置已用箱子计数器box_count为0;
for (i=0;i< n;i++)
{ 从已用的第一只箱子开始顺序寻找能放入物品i 的箱子j;
if (已用箱子都不能再放物品i)
{ 另用一个箱子,并将物品i放入该箱子;
box_count++;
}
else
将物品i放入箱子j;
}
}
上述算法能求出需要的箱子数box_count,并能求出各箱子所装物品。下面的例子说明该算法不一定能找到最优解,设有6种物品,它们的体积分别为:60、45、35、20、20和20单位体积,箱子的容积为100个单位体积。按上述算法计算,需三只箱子,各箱子所装物品分别为:第一只箱子装物品1、3;第二只箱子装物品2、4、5;第三只箱子装物品6。而最优解为两只箱子,分别装物品1、4、5和2、3、6。
若每只箱子所装物品用链表来表示,链表首结点指针存于一个结构中,结构记录尚剩余的空间量和该箱子所装物品链表的首指针。另将全部箱子的信息也构成链表。以下是按以上算法编写的程序。
【程序】
# include < stdio.h>
# include < stdlib.h>
typedef struct ele
{ int vno;
struct ele *link;
} ELE;
typedef struct hnode
{ int remainder;
ELE *head;
Struct hnode *next;
} HNODE;

void main()
{ int n, i, box_count, box_volume, *a;
HNODE *box_h, *box_t, *j;
ELE *p, *q;
Printf(“输入箱子容积\n”);
Scanf(“%d”,&box_volume);
Printf(“输入物品种数\n”);
Scanf(“%d”,&n);
A=(int *)malloc(sizeof(int)*n);
Printf(“请按体积从大到小顺序输入各物品的体积:”);
For (i=0;i< n;i++) scanf(“%d”,a+i);
Box_h=box_t=NULL;
Box_count=0;
For (i=0;i< n;i++)
{ p=(ELE *)malloc(sizeof(ELE));
p->vno=i;
for (j=box_h;j!=NULL;j=j->next)
if (j->remainder>=a[i]) break;
if (j==NULL)
{ j=(HNODE *)malloc(sizeof(HNODE));
j->remainder=box_volume-a[i];
j->head=NULL;
if (box_h==NULL) box_h=box_t=j;
else box_t=boix_t->next=j;
j->next=NULL;
box_count++;
}
else j->remainder-=a[i];
for (q=j->next;q!=NULL&&q->link!=NULL;q=q->link);
if (q==NULL)
{ p->link=j->head;
j->head=p;
}
else
{ p->link=NULL;
q->link=p;
}
}
printf(“共使用了%d只箱子”,box_count);
printf(“各箱子装物品情况如下:”);
for (j=box_h,i=1;j!=NULL;j=j->next,i++)
{ printf(“第%2d只箱子,还剩余容积%4d,所装物品有;\n”,I,j->remainder);
for (p=j->head;p!=NULL;p=p->link)
printf(“%4d”,p->vno+1);
printf(“\n”);
}
}
【问题】 马的遍历
问题描述:在8×8方格的棋盘上,从任意指定的方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
马在某个方格,可以在一步内到达的不同位置最多有8个,如图所示。如用二维数组board[ ][ ]表示棋盘,其元素记录马经过该位置时的步骤号。另对马的8种可能走法(称为着法)设定一个顺序,如当前位置在棋盘的(i,j)方格,下一个可能的位置依次为(i+2,j+1)、(i+1,j+2)、(i-1,j+2)、(i-2,j+1)、(i-2,j-1)、(i-1,j-2)、(i+1,j-2)、(i+2,j-1),实际可以走的位置尽限于还未走过的和不越出边界的那些位置。为便于程序的同意处理,可以引入两个数组,分别存储各种可能走法对当前位置的纵横增量。
4 3
5 2

6 1
7 0

对于本题,一般可以采用回溯法,这里采用Warnsdoff策略求解,这也是一种贪婪法,其选择下一出口的贪婪标准是在那些允许走的位置中,选择出口最少的那个位置。如马的当前位置(i,j)只有三个出口,他们是位置(i+2,j+1)、(i-2,j+1)和(i-1,j-2),如分别走到这些位置,这三个位置又分别会有不同的出口,假定这三个位置的出口个数分别为4、2、3,则程序就选择让马走向(i-2,j+1)位置。
由于程序采用的是一种贪婪法,整个找解过程是一直向前,没有回溯,所以能非常快地找到解。但是,对于某些开始位置,实际上有解,而该算法不能找到解。对于找不到解的情况,程序只要改变8种可能出口的选择顺序,就能找到解。改变出口选择顺序,就是改变有相同出口时的选择标准。以下程序考虑到这种情况,引入变量start,用于控制8种可能着法的选择顺序。开始时为0,当不能找到解时,就让start增1,重新找解。细节以下程序。
【程序】
# include < stdio.h>
int delta_i[ ]={2,1,-1,-2,-2,-1,1,2};
int delta_j[ ]={1,2,2,1,-1,-2,-2,-1};
int board[8][8];
int exitn(int i,int j,int s,int a[ ])
{ int i1,j1,k,count;
for (count=k=0;k< 8;k++)
{ i1=i+delta_i[(s+k)%8];
j1=i+delta_j[(s+k)%8];
if (i1>=0&&i1< 8&&j1>=0&&j1< 8&&board[I1][j1]==0)
a[count++]=(s+k)%8;
}
return count;
}

int next(int i,int j,int s)
{ int m,k,mm,min,a[8],b[8],temp;
m=exitn(i,j,s,a);
if (m==0) return –1;
for (min=9,k=0;k< m;k++)
{ temp=exitn(I+delta_i[a[k]],j+delta_j[a[k]],s,b);
if (temp< min)
{ min=temp;
kk=a[k];
}
}
return kk;
}

void main()
{ int sx,sy,i,j,step,no,start;
for (sx=0;sx< 8;sx++)
for (sy=0;sy< 8;sy++)
{ start=0;
do {
for (i=0;i< 8;i++)
for (j=0;j< 8;j++)
board[i][j]=0;
board[sx][sy]=1;
I=sx; j=sy;
For (step=2;step< 64;step++)
{ if ((no=next(i,j,start))==-1) break;
I+=delta_i[no];
j+=delta_j[no];
board[i][j]=step;
}
if (step>64) break;
start++;
} while(step< =64)
for (i=0;i< 8;i++)
{ for (j=0;j< 8;j++)
printf(“%4d”,board[i][j]);
printf(“\n\n”);
}
scanf(“%*c”);
}
}
七、分治法
1、分治法的基本思想
任何一个可以用计算机求解的问题所需的计算时间都与其规模N有关。问题的规模越小,越容易直接求解,解题所需的计算时间也越少。例如,对于n个元素的排序问题,当n=1时,不需任何计算;n=2时,只要作一次比较即可排好序;n=3时只要作3次比较即可,…。而当n较大时,问题就不那么容易处理了。要想直接解决一个规模较大的问题,有时是相当困难的。
分治法的设计思想是,将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之。
如果原问题可分割成k个子问题(1< k≤n),且这些子问题都可解,并可利用这些子问题的解求出原问题的解,那么这种分治法就是可行的。由分治法产生的子问题往往是原问题的较小模式,这就为使用递归技术提供了方便。在这种情况下,反复应用分治手段,可以使子问题与原问题类型一致而其规模却不断缩小,最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。分治与递归像一对孪生兄弟,经常同时应用在算法设计之中,并由此产生许多高效算法。
2、分治法的适用条件
分治法所能解决的问题一般具有以下几个特征:
(1)该问题的规模缩小到一定的程度就可以容易地解决;
(2)该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质;
(3)利用该问题分解出的子问题的解可以合并为该问题的解;
(4)该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子子问题。
上述的第一条特征是绝大多数问题都可以满足的,因为问题的计算复杂性一般是随着问题规模的增加而增加;第二条特征是应用分治法的前提,它也是大多数问题可以满足的,此特征反映了递归思想的应用;第三条特征是关键,能否利用分治法完全取决于问题是否具有第三条特征,如果具备了第一条和第二条特征,而不具备第三条特征,则可以考虑贪心法或动态规划法。第四条特征涉及到分治法的效率,如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题,此时虽然可用分治法,但一般用动态规划法较好。
3、分治法的基本步骤
分治法在每一层递归上都有三个步骤:
(1)分解:将原问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题;
(2)解决:若子问题规模较小而容易被解决则直接解,否则递归地解各个子问题;
(3)合并:将各个子问题的解合并为原问题的解。
它的一般的算法设计模式如下:
Divide_and_Conquer(P)
if |P|≤n0
then return(ADHOC(P))
将P分解为较小的子问题P1、P2、…、Pk
for i←1 to k
do
yi ← Divide-and-Conquer(Pi) △ 递归解决Pi
T ← MERGE(y1,y2,…,yk) △ 合并子问题
Return(T)
其中 |P| 表示问题P的规模;n0为一阈值,表示当问题P的规模不超过n0时,问题已容易直接解出,不必再继续分解。ADHOC(P)是该分治法中的基本子算法,用于直接解小规模的问题P。因此,当P的规模不超过n0时,直接用算法ADHOC(P)求解。
算法MERGE(y1,y2,…,yk)是该分治法中的合并子算法,用于将P的子问题P1、P2、…、Pk的相应的解y1、y2、…、yk合并为P的解。
根据分治法的分割原则,原问题应该分为多少个子问题才较适宜?各个子问题的规模应该怎样才为适当?这些问题很难予以肯定的回答。但人们从大量实践中发现,在用分治法设计算法时,最好使子问题的规模大致相同。换句话说,将一个问题分成大小相等的k个子问题的处理方法是行之有效的。许多问题可以取k=2。这种使子问题规模大致相等的做法是出自一种平衡子问题的思想,它几乎总是比子问题规模不等的做法要好。
分治法的合并步骤是算法的关键所在。有些问题的合并方法比较明显,有些问题合并方法比较复杂,或者是有多种合并方案;或者是合并方案不明显。究竟应该怎样合并,没有统一的模式,需要具体问题具体分析。
【问题】 大整数乘法
问题描述:
通常,在分析一个算法的计算复杂性时,都将加法和乘法运算当作是基本运算来处理,即将执行一次加法或乘法运算所需的计算时间当作一个仅取决于计算机硬件处理速度的常数。
这个假定仅在计算机硬件能对参加运算的整数直接表示和处理时才是合理的。然而,在某些情况下,我们要处理很大的整数,它无法在计算机硬件能直接表示的范围内进行处理。若用浮点数来表示它,则只能近似地表示它的大小,计算结果中的有效数字也受到限制。若要精确地表示大整数并在计算结果中要求精确地得到所有位数上的数字,就必须用软件的方法来实现大整数的算术运算。
请设计一个有效的算法,可以进行两个n位大整数的乘法运算。
设X和Y都是n位的二进制整数,现在要计算它们的乘积XY。我们可以用小学所学的方法来设计一个计算乘积XY的算法,但是这样做计算步骤太多,显得效率较低。如果将每2个1位数的乘法或加法看作一步运算,那么这种方法要作O(n2)步运算才能求出乘积XY。下面我们用分治法来设计一个更有效的大整数乘积算法。

图6-3 大整数X和Y的分段
我们将n位的二进制整数X和Y各分为2段,每段的长为n/2位(为简单起见,假设n是2的幂),如图6-3所示。
由此,X=A2n/2+B,Y=C2n/2+D。这样,X和Y的乘积为:
XY=(A2n/2+B)(C2n/2+D)=AC2n+(AD+CB)2n/2+BD (1)
如果按式(1)计算XY,则我们必须进行4次n/2位整数的乘法(AC,AD,BC和BD),以及3次不超过n位的整数加法(分别对应于式(1)中的加号),此外还要做2次移位(分别对应于式(1)中乘2n和乘2n/2)。所有这些加法和移位共用O(n)步运算。设T(n)是2个n位整数相乘所需的运算总数,则由式(1),我们有:
(2)
由此可得T(n)=O(n2)。因此,用(1)式来计算X和Y的乘积并不比小学生的方法更有效。要想改进算法的计算复杂性,必须减少乘法次数。为此我们把XY写成另一种形式:
XY=AC2n+[(A-B)(D-C)+AC+BD]2n/2+BD (3)
虽然,式(3)看起来比式(1)复杂些,但它仅需做3次n/2位整数的乘法(AC,BD和(A-B)(D-C)),6次加、减法和2次移位。由此可得:
(4)
用解递归方程的套用公式法马上可得其解为T(n)=O(nlog3)=O(n1.59)。利用式(3),并考虑到X和Y的符号对结果的影响,我们给出大整数相乘的完整算法MULT如下:
function MULT(X,Y,n); {X和Y为2个小于2n的整数,返回结果为X和Y的乘积XY}
begin
S=SIGN(X)*SIGN(Y); {S为X和Y的符号乘积}
X=ABS(X);
Y=ABS(Y); {X和Y分别取绝对值}
if n=1 then
if (X=1)and(Y=1) then return(S)
else return(0)
else begin
A=X的左边n/2位;
B=X的右边n/2位;
C=Y的左边n/2位;
D=Y的右边n/2位;
ml=MULT(A,C,n/2);
m2=MULT(A-B,D-C,n/2);
m3=MULT(B,D,n/2);
S=S*(m1*2n+(m1+m2+m3)*2n/2+m3);
return(S);
end;
end;
上述二进制大整数乘法同样可应用于十进制大整数的乘法以提高乘法的效率减少乘法次数。
【问题】 最接近点对问题
问题描述:
在应用中,常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中,常需要了解其邻域中其他几何对象的信息。例如,在空中交通控制问题中,若将飞机作为空间中移动的一个点来看待,则具有最大碰撞危险的2架飞机,就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一。下面我们着重考虑平面上的最接近点对问题。
最接近点对问题的提法是:给定平面上n个点,找其中的一对点,使得在n个点的所有点对中,该点对的距离最小。
严格地说,最接近点对可能多于1对。为了简单起见,这里只限于找其中的一对。
这个问题很容易理解,似乎也不难解决。我们只要将每一点与其他n-1个点的距离算出,找出达到最小距离的两个点即可。然而,这样做效率太低,需要O(n2)的计算时间。我们能否找到问题的一个O (nlogn)算法。
这个问题显然满足分治法的第一个和第二个适用条件,我们考虑将所给的平面上n个点的集合S分成2个子集S1和S2,每个子集中约有n/2个点,然后在每个子集中递归地求其最接近的点对。在这里,一个关键的问题是如何实现分治法中的合并步骤,即由S1和S2的最接近点对,如何求得原集合S中的最接近点对,因为S1和S2的最接近点对未必就是S的最接近点对。如果组成S的最接近点对的2个点都在S1中或都在S2中,则问题很容易解决。但是,如果这2个点分别在S1和S2中,则对于S1中任一点p,S2中最多只有n/2个点与它构成最接近点对的候选者,仍需做n2/4次计算和比较才能确定S的最接近点对。因此,依此思路,合并步骤耗时为O(n2)。整个算法所需计算时间T(n)应满足:
T(n)=2T(n/2)+O(n2)
它的解为T(n)=O(n2),即与合并步骤的耗时同阶,显示不出比用穷举的方法好。从解递归方程的套用公式法,我们看到问题出在合并步骤耗时太多。这启发我们把注意力放在合并步骤上。
为了使问题易于理解和分析,我们先来考虑一维的情形。此时S中的n个点退化为x轴上的n个实数x1、x2、…、xn。最接近点对即为这n个实数中相差最小的2个实数。我们显然可以先将x1、x2、…、xn排好序,然后,用一次线性扫描就可以找出最接近点对。这种方法主要计算时间花在排序上,因此如在排序算法中所证明的,耗时为O(nlogn)。然而这种方法无法直接推广到二维的情形。因此,对这种一维的简单情形,我们还是尝试用分治法来求解,并希望能推广到二维的情形。
假设我们用x轴上某个点m将S划分为2个子集S1和S2,使得S1={x∈S | x≤m};S2={x∈S | x>m}。这样一来,对于所有p∈S1和q∈S2有p< q。
递归地在S1和S2上找出其最接近点对{p1,p2}和{q1,q2},并设δ=min{|p1-p2|,|q1-q2|},S中的最接近点对或者是{p1,p2},或者是{q1,q2},或者是某个{p3,q3},其中p3∈S1且q3∈S2。如图1所示。

图1 一维情形的分治法
我们注意到,如果S的最接近点对是{p3,q3},即 | p3-q3 | < δ,则p3和q3两者与m的距离不超过δ,即 | p3-m | < δ,| q3-m | < δ,也就是说,p3∈(m-δ,m),q3∈(m,m+δ)。由于在S1中,每个长度为δ的半闭区间至多包含一个点(否则必有两点距离小于δ),并且m是S1和S2的分割点,因此(m-δ,m)中至多包含S中的一个点。同理,(m,m+δ)中也至多包含S中的一个点。由图1可以看出,如果(m-δ,m)中有S中的点,则此点就是S1中最大点。同理,如果(m,m+δ)中有S中的点,则此点就是S2中最小点。因此,我们用线性时间就能找到区间(m-δ,m)和(m,m+δ)中所有点,即p3和q3。从而我们用线性时间就可以将S1的解和S2的解合并成为S的解。也就是说,按这种分治策略,合并步可在O(n)时间内完成。这样是否就可以得到一个有效的算法了呢?
还有一个问题需要认真考虑,即分割点m的选取,及S1和S2的划分。选取分割点m的一个基本要求是由此导出集合S的一个线性分割,即S=S1∪S2 ,S1∩S2=Φ,且S1 {x | x≤m};S2 {x | x>m}。容易看出,如果选取m=[max(S)+min(S)]/2,可以满足线性分割的要求。选取分割点后,再用O(n)时间即可将S划分成S1={x∈S | x≤m}和S2={x∈S | x>m}。然而,这样选取分割点m,有可能造成划分出的子集S1和S2的不平衡。例如在最坏情况下,|S1|=1,|S2|=n-1,由此产生的分治法在最坏情况下所需的计算时间T(n)应满足递归方程:
T(n)=T(n-1)+O(n)
它的解是T(n)=O(n2)。这种效率降低的现象可以通过分治法中“平衡子问题”的方法加以解决。也就是说,我们可以通过适当选择分割点m,使S1和S2中有大致相等个数的点。自然地,我们会想到用S的n个点的坐标的中位数来作分割点。在选择算法中介绍的选取中位数的线性时间算法使我们可以在O(n)时间内确定一个平衡的分割点m。
至此,我们可以设计出一个求一维点集S中最接近点对的距离的算法pair如下。
Float pair(S);
{ if | S | =2 δ= | x[2]-x[1] | /*x[1..n]存放的是S中n个点的坐标*/
else
{ if ( | S | =1) δ=∞
else
{ m=S中各点的坐标值的中位数;
构造S1和S2,使S1={x∈S | x≤m},S2={x∈S | x>m};
δ1=pair(S1);
δ2=pair(S2);
p=max(S1);
q=min(S2);
δ=min(δ1,δ2,q-p);
}
return(δ);
}
由以上的分析可知,该算法的分割步骤和合并步骤总共耗时O(n)。因此,算法耗费的计算时间T(n)满足递归方程:

解此递归方程可得T(n)=O(nlogn)。

【问题】循环赛日程表
问题描述:设有n=2k个运动员要进行网球循环赛。现要设计一个满足以下要求的比赛日程表:
(1)每个选手必须与其他n-1个选手各赛一次;
(2)每个选手一天只能参赛一次;
(3)循环赛在n-1天内结束。
请按此要求将比赛日程表设计成有n行和n-1列的一个表。在表中的第i行,第j列处填入第i个选手在第j天所遇到的选手。其中1≤i≤n,1≤j≤n-1。
按分治策略,我们可以将所有的选手分为两半,则n个选手的比赛日程表可以通过n/2个选手的比赛日程表来决定。递归地用这种一分为二的策略对选手进行划分,直到只剩下两个选手时,比赛日程表的制定就变得很简单。这时只要让这两个选手进行比赛就可以了。

1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 1 4 3 6 7 8 5
3 4 1 2 7 8 5 6
1 2 3 4 3 2 1 8 5 6 7
1 2 3 4 5 6 7 8 1 4 3 2
1 2 1 4 3 6 5 8 7 2 1 4 3
1 2 3 4 1 2 7 8 5 6 3 2 1 4
2 1 4 3 2 1 8 7 6 5 4 3 2 1
(1) (2) (3)
图1 2个、4个和8个选手的比赛日程表
图1所列出的正方形表(3)是8个选手的比赛日程表。其中左上角与左下角的两小块分别为选手1至选手4和选手5至选手8前3天的比赛日程。据此,将左上角小块中的所有数字按其相对位置抄到右下角,又将左下角小块中的所有数字按其相对位置抄到右上角,这样我们就分别安排好了选手1至选手4和选手5至选手8在后4天的比赛日程。依此思想容易将这个比赛日程表推广到具有任意多个选手的情形。

# 回复:常用算法设计方法(转贴)-> 2004-11-19 12:10 PM 八、动态规划法
八、动态规划法
经常会遇到复杂问题不能简单地分解成几个子问题,而会分解出一系列的子问题。简单地采用把大问题分解成子问题,并综合子问题的解导出大问题的解的方法,问题求解耗时会按问题规模呈幂级数增加。
为了节约重复求相同子问题的时间,引入一个数组,不管它们是否对最终解有用,把所有子问题的解存于该数组中,这就是动态规划法所采用的基本方法。以下先用实例说明动态规划方法的使用。
【问题】 求两字符序列的最长公共字符子序列
问题描述:字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y1,…,yk-1”是X的子序列,存在X的一个严格递增下标序列< i0,i1,…,ik-1>,使得对所有的j=0,1,…,k-1,有xij=yj。例如,X=“ABCBDAB”,Y=“BCDB”是X的一个子序列。
给定两个序列A和B,称序列Z是A和B的公共子序列,是指Z同是A和B的子序列。问题要求已知两序列A和B的最长公共子序列。
如采用列举A的所有子序列,并一一检查其是否又是B的子序列,并随时记录所发现的子序列,最终求出最长公共子序列。这种方法因耗时太多而不可取。
考虑最长公共子序列问题如何分解成子问题,设A=“a0,a1,…,am-1”,B=“b0,b1,…,bm-1”,并Z=“z0,z1,…,zk-1”为它们的最长公共子序列。不难证明有以下性质:
(1) 如果am-1=bn-1,则zk-1=am-1=bn-1,且“z0,z1,…,zk-2”是“a0,a1,…,am-2”和“b0,b1,…,bn-2”的一个最长公共子序列;
(2) 如果am-1!=bn-1,则若zk-1!=am-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列;
(3) 如果am-1!=bn-1,则若zk-1!=bn-1,蕴涵“z0,z1,…,zk-1”是“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列。
这样,在找A和B的公共子序列时,如有am-1=bn-1,则进一步解决一个子问题,找“a0,a1,…,am-2”和“b0,b1,…,bm-2”的一个最长公共子序列;如果am-1!=bn-1,则要解决两个子问题,找出“a0,a1,…,am-2”和“b0,b1,…,bn-1”的一个最长公共子序列和找出“a0,a1,…,am-1”和“b0,b1,…,bn-2”的一个最长公共子序列,再取两者中较长者作为A和B的最长公共子序列。
定义c[i][j]为序列“a0,a1,…,ai-2”和“b0,b1,…,bj-1”的最长公共子序列的长度,计算c[i][j]可递归地表述如下:
(1)c[i][j]=0 如果i=0或j=0;
(2)c[i][j]= c[i-1][j-1]+1 如果I,j>0,且a[i-1]=b[j-1];
(3)c[i][j]=max(c[i][j-1],c[i-1][j]) 如果I,j>0,且a[i-1]!=b[j-1]。
按此算式可写出计算两个序列的最长公共子序列的长度函数。由于c[i][j]的产生仅依赖于c[i-1][j-1]、c[i-1][j]和c[i][j-1],故可以从c[m][n]开始,跟踪c[i][j]的产生过程,逆向构造出最长公共子序列。细节见程序。
# include < stdio.h>
# include < string.h>
# define N 100
char a[N],b[N],str[N];

int lcs_len(char *a, char *b, int c[ ][ N])
{ int m=strlen(a), n=strlen(b), i,j;
for (i=0;i< =m;i++) c[i][0]=0;
for (i=0;i< =n;i++) c[0][i]=0;
for (i=1;i< =m;i++)
for (j=1;j< =m;j++)
if (a[i-1]==b[j-1])
c[i][j]=c[i-1][j-1]+1;
else if (c[i-1][j]>=c[i][j-1])
c[i][j]=c[i-1][j];
else
c[i][j]=c[i][j-1];
return c[m][n];
}

char *buile_lcs(char s[ ],char *a, char *b)
{ int k, i=strlen(a), j=strlen(b);
k=lcs_len(a,b,c);
s[k]=’\0’;
while (k>0)
if (c[i][j]==c[i-1][j]) i--;
else if (c[i][j]==c[i][j-1]) j--;
else { s[--k]=a[i-1];
i--; j--;
}
return s;
}

void main()
{ printf (“Enter two string(< %d)!\n”,N);
scanf(“%s%s”,a,b);
printf(“LCS=%s\n”,build_lcs(str,a,b));
}
1、动态规划的适用条件
任何思想方法都有一定的局限性,超出了特定条件,它就失去了作用。同样,动态规划也并不是万能的。适用动态规划的问题必须满足最优化原理和无后效性。
(1)最优化原理(最优子结构性质)
最优化原理可这样阐述:一个最优化策略具有这样的性质,不论过去状态和决策如何,对前面的决策所形成的状态而言,余下的诸决策必须构成最优策略。简而言之,一个最优化策略的子策略总是最优的。一个问题满足最优化原理又称其具有最优子结构性质。

图2
例如图2中,若路线I和J是A到C的最优路径,则根据最优化原理,路线J必是从B到C的最优路线。这可用反证法证明:假设有另一路径J’是B到C的最优路径,则A到C的路线取I和J’比I和J更优,矛盾。从而证明J’必是B到C的最优路径。
最优化原理是动态规划的基础,任何问题,如果失去了最优化原理的支持,就不可能用动态规划方法计算。根据最优化原理导出的动态规划基本方程是解决一切动态规划问题的基本方法。
(2)无后向性
将各阶段按照一定的次序排列好之后,对于某个给定的阶段状态,它以前各阶段的状态无法直接影响它未来的决策,而只能通过当前的这个状态。换句话说,每个状态都是过去历史的一个完整总结。这就是无后向性,又称为无后效性。
(3)子问题的重叠性
动态规划算法的关键在于解决冗余,这是动态规划算法的根本目的。动态规划实质上是一种以空间换时间的技术,它在实现的过程中,不得不存储产生过程中的各种状态,所以它的空间复杂度要大于其它的算法。选择动态规划算法是因为动态规划算法在空间上可以承受,而搜索算法在时间上却无法承受,所以我们舍空间而取时间。
所以,能够用动态规划解决的问题还有一个显著特征:子问题的重叠性。这个性质并不是动态规划适用的必要条件,但是如果该性质无法满足,动态规划算法同其他算法相比就不具备优势。
2、动态规划的基本思想
前文主要介绍了动态规划的一些理论依据,我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划,这种标准动态规划是在研究多阶段决策问题时推导出来的,具有严格的数学形式,适合用于理论上的分析。在实际应用中,许多问题的阶段划分并不明显,这时如果刻意地划分阶段法反而麻烦。一般来说,只要该问题可以划分成规模更小的子问题,并且原问题的最优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决。
动态规划的实质是分治思想和解决冗余,因此,动态规划是一种将问题实例分解为更小的、相似的子问题,并存储子问题的解而避免计算重复的子问题,以解决最优化问题的算法策略。
由此可知,动态规划法与分治法和贪心法类似,它们都是将问题实例归纳为更小的、相似的子问题,并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择,但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下,一步一步地作出贪心选择;而分治法中的各个子问题是独立的(即不包含公共的子子问题),因此一旦递归地求出各子问题的解后,便可自下而上地将子问题的解合并成问题的解。但不足的是,如果当前选择可能要依赖子问题的解时,则难以通过局部的贪心策略达到全局最优解;如果各子问题是不独立的,则分治法要做许多不必要的工作,重复地解公共的子问题。
解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题,这类问题会有多种可能的解,每个解都有一个值,而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话,它只取其中的一个。在求解过程中,该方法也是通过求解局部子问题的解达到全局最优解,但与分治法和贪心法不同的是,动态规划允许这些子问题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择,该方法对每一个子问题只解一次,并将结果保存起来,避免每次碰到时都要重复计算。
因此,动态规划法所针对的问题有一个显著的特征,即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于,对于重复出现的子问题,只在第一次遇到时加以求解,并把答案保存起来,让以后再遇到时直接引用,不必重新求解。
3、动态规划算法的基本步骤
设计一个标准的动态规划算法,通常可按以下几个步骤进行:
(1)划分阶段:按照问题的时间或空间特征,把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的(即无后向性),否则问题就无法用动态规划求解。
(2)选择状态:将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然,状态的选择要满足无后效性。
(3)确定决策并写出状态转移方程:之所以把这两步放在一起,是因为决策和状态转移有着天然的联系,状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以,如果我们确定了决策,状态转移方程也就写出来了。但事实上,我们常常是反过来做,根据相邻两段的各状态之间的关系来确定决策。
(4)写出规划方程(包括边界条件):动态规划的基本方程是规划方程的通用形式化表达式。
一般说来,只要阶段、状态、决策和状态转移确定了,这一步还是比较简单的。动态规划的主要难点在于理论上的设计,一旦设计完成,实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值,但是一般将其改为递推计算,实现的大体上的框架如下:
标准动态规划的基本框架
1. 对fn+1(xn+1)初始化; {边界条件}
for k:=n downto 1 do
for 每一个xk∈Xk do
for 每一个uk∈Uk(xk) do
begin
5. fk(xk):=一个极值; {∞或-∞}
6. xk+1:=Tk(xk,uk); {状态转移方程}
7. t:=φ(fk+1(xk+1),vk(xk,uk)); {基本方程(9)式}
if t比fk(xk)更优 then fk(xk):=t; {计算fk(xk)的最优值}
end;
9. t:=一个极值; {∞或-∞}
for 每一个x1∈X1 do
11. if f1(x1)比t更优 then t:=f1(x1); {按照10式求出最优指标}
12. 输出t;
但是,实际应用当中经常不显式地按照上面步骤设计动态规划,而是按以下几个步骤进行:
(1)分析最优解的性质,并刻划其结构特征。
(2)递归地定义最优值。
(3)以自底向上的方式或自顶向下的记忆化方法(备忘录法)计算出最优值。
(4)根据计算最优值时得到的信息,构造一个最优解。
步骤(1)~(3)是动态规划算法的基本步骤。在只需要求出最优值的情形,步骤(4)可以省略,若需要求出问题的一个最优解,则必须执行步骤(4)。此时,在步骤(3)中计算最优值时,通常需记录更多的信息,以便在步骤(4)中,根据所记录的信息,快速地构造出一个最优解。

【问题】 凸多边形的最优三角剖分问题
问题描述:多边形是平面上一条分段线性的闭曲线。也就是说,多边形是由一系列首尾相接的直线段组成的。组成多边形的各直线段称为该多边形的边。多边形相接两条边的连接点称为多边形的顶点。若多边形的边之间除了连接顶点外没有别的公共点,则称该多边形为简单多边形。一个简单多边形将平面分为3个部分:被包围在多边形内的所有点构成了多边形的内部;多边形本身构成多边形的边界;而平面上其余的点构成了多边形的外部。当一个简单多边形及其内部构成一个闭凸集时,称该简单多边形为凸多边形。也就是说凸多边形边界上或内部的任意两点所连成的直线段上所有的点均在该凸多边形的内部或边界上。
通常,用多边形顶点的逆时针序列来表示一个凸多边形,即P=< v0,v1,…,vn-1>表示具有n条边v0v1,v1v2,…,vn-1vn的一个凸多边形,其中,约定v0=vn 。
若vi与vj是多边形上不相邻的两个顶点,则线段vivj称为多边形的一条弦。弦将多边形分割成凸的两个子多边形< vi,vi+1,…,vj>和< vj,vj+1,…,vi>。多边形的三角剖分是一个将多边形分割成互不重迭的三角形的弦的集合T。图1是一个凸多边形的两个不同的三角剖分。

(a) (b)
图1 一个凸多边形的2个不同的三角剖分
在凸多边形P的一个三角剖分T中,各弦互不相交且弦数已达到最大,即P的任一不在T中的弦必与T中某一弦相交。在一个有n个顶点的凸多边形的三角刮分中,恰好有n-3条弦和n-2个三角形。
凸多边形最优三角剖分的问题是:给定一个凸多边形P=< v0,v1,…,vn-1>以及定义在由多边形的边和弦组成的三角形上的权函数ω。要求确定该凸多边形的一个三角剖分,使得该三角剖分对应的权即剖分中诸三角形上的权之和为最小。
可以定义三角形上各种各样的权函数ω。例如:定义ω(△vivjvk)=| vivj |+| vivk |+| vkvj |,其中,| vivj |是点vi到vj的欧氏距离。相应于此权函数的最优三角剖分即为最小弦长三角剖分。
(1)最优子结构性质
凸多边形的最优三角剖分问题有最优子结构性质。事实上,若凸(n+1)边形P=< v0,v1 ,…,vn>的一个最优三角剖分T包含三角形v0vkvn,1≤k≤n-1,则T的权为3个部分权的和,即三角形v0vkvn的权,子多边形< v0,v1,…,vk>的权和< vk,vk+1,…,vn>的权之和。可以断言由T所确定的这两个子多边形的三角剖分也是最优的,因为若有< v0,v1,…,vk>或< vk,vk+1,…,vn>的更小权的三角剖分,将会导致T不是最优三角剖分的矛盾。
(2)最优三角剖分对应的权的递归结构
首先,定义t[i,j](1≤i< j≤n)为凸子多边形< vi-1,vi,…,vj>的最优三角剖分所对应的权值,即最优值。为方便起见,设退化的多边形< vi-1,vi>具有权值0。据此定义,要计算的凸(n+1)边多边形P对应的权的最优值为t[1,n]。
t[i,j]的值可以利用最优子结构性质递归地计算。由于退化的2顶点多边形的权值为0,所以t[i,i]=0,i=1,2,…,n 。当j一i≥1时,子多边形< vi-1,vi,…,vj>至少有3个顶点。由最优于结构性质,t[i,j]的值应为t[i,k]的值加上t[k+1,j]的值,再加上△vi-1vkvj的权值,并在i≤k≤j-1的范围内取最小。由此,t[i,j]可递归地定义为:

(3)计算最优值
下面描述的计算凸(n+1)边形P=< v0,v1,…,vn>的三角剖分最优权值的动态规划算法MINIMUM_WEIGHT,输入是凸多边形P=< v0,v1,…,vn>的权函数ω,输出是最优值t[i,j]和使得t[i,k]+t[k+1,j]+ω(△vi-1vkvj)达到最优的位置(k=)s[i,j],1≤i≤j≤n 。
Procedure MINIMUM_WEIGHT(P,w);
Begin
n=length[p]-1;
for i=1 to n do t[i,i]:=0;
for ll=2 to n do
for i=1 to n-ll+1 do
begin
j=i+ll-1;
t[i,j]=∞;
for k=i to j-1 do
begin
q=t[i,k]+t[k+1,j]+ω(△vi-1vkvj);
if q< t[i,j] then
begin
t[i,j]=q;
s[i,j]=k;
end;
end;
end;
return(t,s);
end;
算法MINIMUM_WEIGHT_占用θ(n2)空间,耗时θ(n3)。
(4)构造最优三角剖分
如我们所看到的,对于任意的1≤i≤j≤n ,算法MINIMUM_WEIGHT在计算每一个子多边形< vi-1,vi,…,vj>的最优三角剖分所对应的权值t[i,j]的同时,还在s[i,j]中记录了此最优三角剖分中与边(或弦)vi-1vj构成的三角形的第三个顶点的位置。因此,利用最优子结构性质并借助于s[i,j],1≤i≤j≤n ,凸(n+l)边形P=< v0,v1,…,vn>的最优三角剖分可容易地在Ο(n)时间内构造出来。

习题:
1、汽车加油问题:
设有路程长度为L公里的公路上,分布着m个加油站,它们的位置分别为p[i](i=1,2,……,m),而汽车油箱加满油后(油箱最多可以加油k升),可以行驶n公里。设计一个方案,使汽车经过此公路的加油次数尽量少(汽车出发时是加满油的)。
2、最短路径:
设有一个网络,要求从某个顶点出发到其他顶点的最短路径
3、跳马问题:
在8*8方格的棋盘上,从任意指定的方格出发,为马寻找一条走遍棋盘每一格并且只经过一次的一条路径。
4、二叉树的遍历
5、背包问题
6、用分治法实现两个大整数相乘
7、设x1,x2,…,xn是直线上的n个点,若要用单位长度的闭区间去覆盖这n个点,至少需要多少个这样的单位闭区间?
8、用关系“<”和“=”将3个数A、B和C依次排列时,有13种不同的序关系:
A=B=C,A=B<C,A<B=C,A<B<C,A<C<B,A=C<B,B<A=C,
B<A<C,B<C<A,B=C<A,C<A=B,C<A<B,C<A<B。
若要将n个数依序进行排列,试设计一个动态规划算法,计算出有多少钟不同的序关系。
9、有一种单人玩的游戏:设有n(2< =n< =200)堆薄片,各堆顺序用0至 n-1编号,极端情况,有的堆可能没有薄片。在游戏过程中,一次移动只能取某堆上的若干张薄片,移到该堆的相邻堆上。如指定
I堆k张 k 移到I-1(I>0)堆,和将k 张薄片移至I+1(I< n-1)堆。所以当有两个堆与 I 堆相邻 时,I堆原先至少有2k 张薄片;只有一个堆与 I 堆相邻 时, I 堆原先至少有k张薄片。
游戏的目标是对给定的堆数,和各堆上的薄片数,按上述规则移动薄片,最终使 各堆的薄片数相同。为了使移动次数较少些,移动哪一堆薄片,和移多少薄片先作以下估算:

ci:I堆的薄片数(0< =I< n,0< =ci< =200);
v:每堆 的平均薄片数;
ai:I堆的相邻堆可以从I堆得到的薄片数。
估算方法如下:
v=c0+a1-a0 a1=v+a0-c0
v=c1+a0+a2-2a1 a2=v+2a1-a0-c1
…….. ……….
V=ci+ai-1+ai+1-2aI ai+1=v+2ai-ai-1-ci
这里并不希望准确地求出A0 至an-1,而是作以下处理:若令 a0 为0,能按上述算式计算出 A1至 an-1。程序找出 a 中的最小值,并让全部a值减去这最小值,使每堆移去的薄片数大于等于0。
实际操作采用以下贪心策略:
(1)每次从第一堆出发顺序搜索每一堆,若发现可从 I堆移走薄片,就完成一次移动。即, I堆的相邻堆从 I堆取走 ai片薄片。可从I 堆移薄片到相邻堆取于 I堆薄片数:若I 堆是处于两端位置( I=0 I=n-1), 要求 ci>=ai ;若 I堆是中间堆,则要求ci>=2ai。
(2)因在ai>0的所有堆中,薄片数最多的堆 在平分过程中被它的相邻堆取走的薄片数也最多。在用策略(1)搜索移动时,当发生没有满足条件(1)的可移走薄片的堆时,采用本策略,让在ai>0的所有堆中,薄片数最多的堆被它的相邻堆取走它的全部薄片。

Thursday, September 09, 2004

 

Vehicle Detection and Recognition for Autonomous Intelligent Cruise Control

Concise and clearly

http://www.ecs.soton.ac.uk/publications/rj/1995-1996/isis/ndm/journal.htm#figcol_detect

1995/6 Research Journal
Image, Speech and Intelligent Systems


Vehicle Detection and Recognition for Autonomous Intelligent Cruise Control
N. D. Matthews, P. E. An and C. J. Harris

The introduction of new technologies such as autonomous intelligent cruise control or collision avoidance schemes to road vehicles necessitates a high degree of robustness and reliability. Whilst very accurate range estimates may be recovered using conventional sensors, e.g. millimetric radar, these typically suffer from both low bearing resolution and potential ambiguities through, for example, false alarms.

This work details a novel two-stage vehicle detection and recognition algorithm which combines an image processing area of interest (AOI) designator to cue a secondary recognition process implemented using principal component analysis (PCA) as input to a Multi-Layered Perceptron (MLP) classifier. The combination of an initial detection phase, followed by a recognition process has allowed the classifier design to be greatly simplified. In turn the classifier performance has allowed some of the image processing assumptions to be relaxed, whilst maintaining a high signal to noise ratio (SNR). Both the image processing system and MLP classifier have been designed for real-time implementation and data-fusion with other information sources such as a range/range rate radar.

Detection

Vehicle Cues
Road-vehicles, especially cars and to a lesser extent lorries, comprise a large number of horizontal structures, particularly when viewed approximately from the rear, e.g. rear-window, boot, bumper (Figure 2). Whilst, there are obviously other potential sources of horizontal structure, both natural, e.g. horizon, and man-made, e.g.\ road-signs, it is generally possible to mask areas within the image where these may occur and it is physically impossible for vehicles to be present, such as above the horizon. Practical experience suggests that clusters of horizontal edges are a significant cue for areas of interest (AOI's) which potentially contain vehicles.

In practice man-made objects, e.g. vehicles, exhibit a stronger edge response than ``natural' objects. Hence, an appropriate technique is to consider the total horizontal edge response over some AOI, rather than using an edge threshold. However, it is extremely difficult to define an appropriate AOI, thus an additional assumption is made that vehicles do not occlude each other greatly, i.e. overlap image columns significantly (Figure 2); this assumption is often implicit in many symmetry based techniques.

Applying the horizontal overlap assumption each image column may be considered as a potential AOI to sum over. Firstly, the horizontal edge response in each image column is summed and smoothed with a triangular filter (Figure 1)

Figure 1: Filtered edge response column sums

-- for images an appropriate support is found to be 10 pixels. Potential vehicle locations are then obtained from locally maximal peaks which are extracted from the smoothed column responses in decreasing order, with an additional constraint to discard maxima which are ``too close' to a previously extracted, i.e. higher, peak -- for images maxima within 25 pixels of a previously extracted peak are ignored.

Figure 2: Detected candidate vehicle columns

Although this technique has a number of limitations, such as the triangular filter support width and the proximity constraint which have implications for the potential size of recovered AOI, it is invariant to camera pitching, for example when changing gear.

Vehicle Width
The vehicle's horizontal extent is determined in a similar manner from an edge following technique applied to the horizontal edge response image. Edges are linked left and right from the candidate vehicle horizontal position on each row until the horizontal edge response drops below a given threshold -- a threshold of 2 has been found to be effective. The vehicle width is determined by the leftmost and rightmost linked edge response pixels (Figure 3).

Figure 3: Detected candidate vehicle widths

Although this technique will overestimate the vehicle width if a large horizontal features crosses the candidate vehicle location, in practice it tends to underestimate the true horizontal vehicle extent since only horizontal edges are considered, whereas a vehicle boundary is usually at a vertical edge.

Vehicle Vertical Location
An important vehicle cue in daylight imagery is the shadow under a vehicle. Consider a small area designated as a road ``template' at the bottom of the original input grey level image whose pixel grey levels are assumed to obey a Gaussian distribution, together with some extraneous pixels belonging to e.g. road markings. The mean of the underlying Gaussian distribution is equivalenced to the mode of the grey level patch -- the mean of a purely Gaussian distribution is by definition equivalent to its mode. The standard deviation of the underlying normal distribution is given by Equation (1)

where x is the position which has a value equal to half of the response observed at modal value. Pixels in the original grey level image in the range are classed as due to a potential under-vehicle shadow.

Areas corresponding to under-vehicle shadows are located by considering each potential vehicle location in turn. Pixels within a given candidate image strip are considered row by row, starting at the bottom of the image, i.e. closest. If more pixels on any given row within a given candidate vehicle's image strip are considered to be shadow than non-shadow, then the row is interpreted as part of an under-vehicle shadow and the vertical location noted as the bottom of the candidate vehicle (Figure 4).

Figure 4: Detected under-vehicle shadows

The candidate vehicle location is discarded if no location can be obtained to satisfy the under-vehicle shadow criterion.

Vehicle height
Obviously, to extract an AOI for subsequent classification an estimate is required for the location of the top of the vehicle. As there are no consistent cues associated with a vehicle roof, a heuristic is applied that rears of cars are approximately square, subject to digitisation. Hence, the vehicle height is equivalenced to its width and thus the top of the vehicle may be estimated from the vehicle width and the location of its under-vehicle shadow (Figure 5).

Figure 5: Detected candidate vehicle AOI's

Horizontal edge clustering
Whilst the vehicle vertical location derived from the under-vehicle shadow is generally temporally stable, it may fail when road characteristics differ greatly from those in the template patch, for example due to shadows cast by overtaking vehicles. Therefore a second vehicle vertical location algorithm has been developed, based on horizontal edge clustering.

A vehicle-sized patch may be defined by applying the same aspect ratio heuristic used to derive the vehicle height. Within a given candidate vehicle strip (Figure 3) the vehicle vertical location is given by the maximum horizontal edge response summed over all vehicle-size patches (figure 6).

Figure 6: Detected candidate vehicle AOI's

Although this technique generally finds an area close to a vehicle it is not as temporally stable as the under-vehicle shadow. Since each image strip will by definition generate a maximum vertical patch position there is an explicit requirement for the car/road classifier.

Classifier Input
The candidate AOI's are dilated slightly to ensure that any vehicle is completely extracted. The AOI is then scaled to a constant size to maintain scale invariance for the classifier. The scaled AOI size is pixels to reduce the dimensionality of the classification problem; any further reduction is likely to ``oversmooth' car edges and other useful features. AOI's extracted using the under-vehicle shadow are shown in Figure 7 and AOI's extracted using horizontal edge clustering are shown in Figure 8.

Figure 7: AOI's for MLP classification

Figure 8: AOI's for MLP classification -- 2

Recognition

Dimensionality Reduction/Feature Extraction
Pattern classification tasks for many image applications are generally considered difficult problems because of the associated high dimensional pattern space and poor signal-to-noise ratio (SNR) due to redundancy of pattern components. Feature extraction is an essential procedure to reduce the problem dimensionality whilst retaining the required SNR. In this combined detection/recognition system a high degree of data reduction has already been performed by the initial image processing stage. With this information, the AOI considered by a classifier may be kept to a reasonable size, greatly improving the SNR and enabling accurate pattern classification.

Local PCA
Since the statistical characteristics of many road patterns tend to be stationary, i.e. a set of localised eigenvectors defined in a smaller dimension can be used to reconstruct the entire pattern by forming an union of local patches, a local principal components analysis (PCA) is generally more robust when reconstructing a pattern which is not in S. This has been verified in this application, where M = 90, L = 25, N = 5. This is an important property for car detection where real-time classification at (near) frame rate is required. An example of such localised eigenvectors or eigenmasks ( pixels) corresponding to the ten largest eigenvalues derived from ninety road/car images (Figure 9).

Figure 9: Eigenmasks corresponding to the ten largest eigenvalues (in descending, raster order)

Pattern Classification
Given a set of properly extracted features, criteria for selecting proper classifiers are commonly based on Bayesian Maximum A Posteriori (MAP) or Maximum Likelihood (ML) principles so that the average error probability is minimised. A nonlinear interpolative model, Multi-layered Perceptron (MLP), is frequently used to approximate the posterior class distribution because of its nonlinear modelling capability. Although the MLP is generally inappropriate for on-line control applications because of its slow adaptation process and non-unique solution minimum, it generalises efficiently in a high dimensional space by means of globally extent basis functions, which is essential for most classification applications. The MLP is chosen as the classifier for this study due to the high dimensionality of the input space.

Training
Car/road identification is performed by the MLP using features extracted by local PCA from a given scaled AOI (fig.\ 7 and 8). The scaled pixel AOI is partitioned into subpatterns, each of size pixels (L=25). Local PCA is performed using the eigenmasks (Figure 9) on the individual subpatterns, and the principal components associated with the five most dominant eigenvalues are computed (N = 5) for each of the subpatterns. The set of principal components forms a transformed pattern (80 dimension). These transformed patterns are then used to adapt the MLP network via backpropagation to estimate the car/road decision boundary. To avoid the common problem of overfitting/parameter drift due to modelling error and measurement noise, the pattern classifier is only trained off-line, and hence its rate of convergence is less critical (this off-line condition obviously requires the training patterns to be truly representative).

By comparing the performance among different pattern distributions, an optimal set of network parameters can be chosen at the point where the classification performance based on the validation set begins to deteriorate (10,000 cycles for 1 hidden node; 9,000 cycles for both 3 and 5 hidden nodes). The mis-classification of car and road patterns was also evaluated to ensure that the classifier was not biased toward any particular class (table 1). Further details are given in [1].

Table 1: MLP classification of training data.

These results indicate that the bias is relatively insignificant (or uniform) for an MLP classifier of 1, 3 or 5 hidden nodes and that classification performance is acceptable, i.e.\ within error, provided that the image characteristics are similar to those in the training patterns.

Integration and results
The integrated system generates a number of candidate AOI's (Figures 7 and 8), potentially two per vertical strip, one due to recovered under-vehicle shadow position and one due to maximum horizontal edge response location, and invokes the MLP classifier on all candidate AOI's. If more than one potential vehicle is detected in a given vertical strip then the AOI with the highest classifier confidence is accepted (figure 12).

For the example image the MLP classifications are shown in figures 10 and 11.

Figure 10: AOI's classified as road (76.2%, 100% and 100%)
Figure 11: AOI's classified as car (27.07%, 40.58%, 88.78%, 93.72%, 94.89%, 95.40% and 96.63%)

A background and lorry tail-gate AOI are categorised as ``car' since they are significantly ``not-road', due to their high degree of internal structure, although the classifier has a low (27.07%) confidence in the classification of the background area.

Figure 12: Detected and classified vehicle targets

Conclusions
The hybrid detection and recognition system has proved to be remarkably successful. The use of the image processing AOI detection enables multiple potential vehicles in a single image to be classified and rejects most extraneous background information from the classification process. Additionally, the use of AOI's has allowed the classifier to be both scale invariant and independent of the AOI position within the input image. The success of the classification system has allowed some of the image processing constraints to be relaxed and hence has enabled an extra degree of robustness to be incorporated into the combined system.

Acknowledgements
The authors thank Lucas Automotive, Ford-Jaguar and Pilkington for their support of this PROMETHEUS research project.

References

1 N.D. Matthews, P.E. An, D. Charnley, and C.J. Harris. Vehicle detection and recognition in greyscale imagery. In 2nd Int. Workshop on Intelligent Autonomous Vehicles, pages 1-6, Helsinki, 1995. IFAC.

Wednesday, September 08, 2004

 

虚拟的随机迷宫创造器

/******************************************************
* 迷宫是一个游戏里经常要用到的东西,以前的迷宫都需要 *
* 巫师一个房间一个房间地手工绘制,费时费力,而且一旦 *
* 被玩家找出正确的线路,迷宫格局被泄漏,迷宫就不称其 *
* 为迷宫了,所以巫师们都绞尽脑汁把迷宫设计的尽量复杂,*
* 但再复杂的迷宫早晚也会被找到正确的路线,而且过于复 *
* 杂难走的迷宫也使玩家感觉过于繁琐,降低乐趣。因此产 *
* 生此想法。 *
* 随机迷宫的产生算法尽量简单,迷宫的储存尽量节省记忆 *
* 体,迷宫房间采用虚拟物件,处理灵活,迷宫房间只有在 *
* 玩家走到时才会装进内存,而且迷宫房间也象普通的ROOM *
* 一样当一段时间没有被参考到可以销毁节省记忆体,当整 *
* 个迷宫一段时间没有被参考到可以被完全摧毁,下次再需 *
* 要的时候会重新建立,又会产生一个新的迷宫。区域巫师 *
* 写作随机迷宫只需规定一些预设的参数如迷宫的单边长、 *
* 房间描述、出入口描述,几十个乃至几千个房间、路线时 *
* 时不同的随机迷宫就建立好了,大大提高了区域写作效率 *
* 和游戏的可玩性。 *
* 此物件目前适合于随机的迷宫,即:迷宫内房间的描述基 *
* 本相同,比如一片树林、一片坟地等,如要此物件创作完 *
* 整的随机区域即有一定的情节、一定格局的区域,则需要 *
* 根据自己的情况规定出迷宫内房间描述的一些规则,使相 *
* 邻房间的描述变化合理,房间内物件与描述协调。如果愿 *
* 意巫师可以只制作迷宫间的连接部分,而用几个迷宫组合 *
* 成一个完全随机的区域,哈,那以后做巫师可轻松多了。 *
* 目前本游戏使用的迷宫一般为单边长10至40,到底能做多 *
* 大的迷宫我也不知道,下面对此有一个说明,要根据自己 *
* 的服务器性能来讲,不过我想最普通的机器制作一个面积 *
* 为100x100的迷宫应该也是一件轻松的事情。 *
* 由于采用 virtual object,牵涉到一点安全问题,需要根*
* 据自己的系统考量调整。 *
******************************************************/

#pragma optimize

#define N 8
#define S 4
#define W 2
#define E 1
#define ALL 15

/****************************************************
* 迷宫的单边长最大值目前暂定为 100,由于随机迷宫的
* 创造和操作比较耗费资源单边长 100 的迷宫'面积'就是
* 100x100 等于 10000 个房间的一个迷宫,一般恐怕是用
* 不到。一般的实时迷宫(实时迷宫是指在游戏运行过程
* 中随时被 destruct 随着需要又会随时被创建的迷宫)的
* 单边长以 10 到 50 之间为宜。如需创造巨型迷宫如有几
* 万乃至十几万个房间的迷宫,应将创建工作放置于游戏启
* 动时做,游戏启动的一段时间(比如20秒)禁止玩家登入。
* 游戏通过定期重新启动来更新此迷宫。
* 不知谁会用到这么大的迷宫。。。。。。
****************************************************/
#define MAX_LONG 100

// 只要能与其他房间相连的房间就肯定有一个入口.
// 而可能的出口有三个.
// define 这项规定房间最多只能有两个出口.
// 也就是对于有三个出口的房间会随机关闭一个.
// 不会使玩家由于看到四个方向都有出口很烦
// 降低游戏乐趣。
#define TWO_VALID_LEAVES

inherit F_CLEAN_UP;

class coordinate{ int x; int y; }
class coordinate *newpath = ({}),/*待处理队列*/
enter,/* 入口坐标 */
leave;/* 出口坐标 */

private string *valid_dirs = ({ "south","north","west","east" });
private mapping reverse_dir = ([
"north" : "south",
"south" : "north",
"west" : "east",
"east" : "west",
]);

// 全迷宫出口阵列.
private mixed *all;

/***************** 迷宫的一些预设特性:*****************/
private int l; // 迷宫的单边长
private string *inherit_rooms = ({}); // 迷宫允许继承的档案名称
private string entry_dir; // 迷宫入口方向
private string link_entry_dir; // 迷宫入口与区域的连接方向
private string link_entry_room; // 迷宫入口所连接区域档案的文件名
private string link_exit_dir; // 迷宫出口与区域的连接方向
private string link_exit_room; // 迷宫出口所连接区域档案的文件名
private string entry_short; // 迷宫入口的短描述
private string entry_desc; // 迷宫入口的长描述
private string exit_short; // 迷宫出口的短描述
private string exit_desc; // 迷宫出口的长描述
private string *maze_room_desc = ({}); // 迷宫房间的长描述
private string maze_room_short; // 迷宫房间的短描述
private int is_outdoors = 0; // 迷宫房间是否为户外
private string *maze_npcs = ({}); // 迷宫中的怪物
/******************* ---- END ---- *********************/

// 建立标记.
private int maze_built = 0;

// 重置全域变量.
private void refresh_vars();

// 建立迷宫
private void create_maze();

// 选择随机出口.
private int random_out(int x,int y,int n);

// 处理连接.
private void link_to_north(int x,int y);
private void link_to_south(int x,int y);
private void link_to_west(int x,int y);
private void link_to_east(int x,int y);

// 绘制已建成迷宫的地图.
private void paint_vrm_map();

private string mroom_fname(int x,int y)
{ return sprintf("%s/%d/%d",base_name(this_object()),x,y);}


private void refresh_vars() // 重置全域变量.
{
newpath = ({});
all = 0;
}

// 对一些必设参数的合法性检查
private int check_vars()
{
int i,n;

if( (l < 5) || l > MAX_LONG )
return 0;

inherit_rooms -=({0});
if( !n = sizeof(inherit_rooms) )
return 0;

for(i=0;iif(!stringp(inherit_rooms[i]) || (inherit_rooms[i] == ""))
return 0;

if(!stringp(entry_dir) || (member_array(entry_dir,valid_dirs) == -1)

)
return 0;
/*
if(!stringp(link_entry_dir) || (member_array(link_entry_dir,valid_dir

s) == -1) )
return 0;

if(!stringp(link_exit_dir) || (member_array(link_exit_dir,valid_dirs)

== -1) )
return 0;
*/
if(!stringp(link_entry_room) || (link_entry_room == ""))
return 0;

if(!stringp(link_exit_room) || (link_exit_room == ""))
return 0;

if(!stringp(entry_short) || (entry_short == ""))
return 0;

if(!stringp(exit_short) || (exit_short == ""))
return 0;

if(!stringp(entry_desc) || (entry_desc == ""))
return 0;

if(!stringp(exit_desc) || (exit_desc == ""))
return 0;

maze_room_desc -=({0});
if( !n = sizeof(maze_room_desc) )
return 0;

for(i=0;iif(!stringp(maze_room_desc[i]) || (maze_room_desc[i] == ""))
return 0;

if(!stringp(maze_room_short) || (maze_room_short == ""))
return 0;

return 1;
}

private int random_out(int x,int y,int n) // 选择随机出口函数.
{
int *outs = ({}), retn = 0;
class coordinate temp;

// The west room is (x-1,y)
if( n&W
&& ((x-1) >= 0)
&& !all[x-1][y] )
{
temp = new(class coordinate);
temp->x = x-1;
temp->y = y;

// 西面的房间不在待处理列表 newpath 中.
//if( member_array(temp,newpath) == -1 )
outs += ({ W });
}

// The east room is (x+1,y)
if( n&E
&& ((x+1) < l)
&& !all[x+1][y] )
{
temp = new(class coordinate);
temp->x = x+1;
temp->y = y;

// 东面的房间不在待处理列表 newpath 中.
//if( member_array(temp,newpath) == -1 )
outs += ({ E });
}

// The south room is (x,y-1)
if( n&S
&& ((y-1) >= 0)
&& !all[x][y-1] )
{
temp = new(class coordinate);
temp->x = x;
temp->y = y-1;

// 南面的房间不在待处理列表 newpath 中.
//if( member_array(temp,newpath) == -1 )
outs += ({ S });
}

// The north room is (x,y+1)
if( n&N
&& ((y+1) < l)
&& !all[x][y+1] )
{
temp = new(class coordinate);
temp->x = x;
temp->y = y+1;

// 北面的房间不在待处理列表 newpath 中.
//if( member_array(temp,newpath) == -1 )
outs += ({ N });
}

#ifdef TWO_VALID_LEAVES
// 如果有三个出口,随机关闭一个.
if(sizeof(outs) >= 3)
outs -= ({ outs[random(sizeof(outs))] });
#endif

for(int i=0;iretn |= outs[i];

return retn;
}

private void create_maze()
{
int i;
class coordinate *valid_leaves=({}),temp;

refresh_vars(); // 重置全域变量.
if( !check_vars() ) // 对一些预设变量进行检查。
return;

// 1.确定迷宫单边长.
all = allocate(l);
for(i=0;iall[i] = allocate(l); // 建立数组.

enter = new(class coordinate);

switch (entry_dir)
{
case "south":
// enter 入口坐标.
enter->x = to_int(l/2); // 取中迷宫比较平衡。
enter->y = 0;
all[enter->x][enter->y] |= S;
break;
case "north":
enter->x = to_int(l/2);
enter->y = l-1;
all[enter->x][enter->y] |= N;
break;
case "west":
enter->y = to_int(l/2);
enter->x = 0;
all[enter->x][enter->y] |= W;
break;
case "east":
enter->y = to_int(l/2);
enter->x = l-1;
all[enter->x][enter->y] |= E;
break;
}

// 存入待处理队列.
newpath += ({ enter });

// 进入主循环.
do
{
int x,y,out,numb;

// 进行一些监测与初始化.
if( !(numb=sizeof(newpath)) )
continue;
numb = random(numb);
reset_eval_cost();
x = newpath[numb]->x;
y = newpath[numb]->y;

// 如果有三个可能的出口随机关闭一个出口:
out = ALL^(all[x][y]);
out = random_out(x,y,out);

if(!out) // 没有可能的出口了.
{
newpath -= ({ newpath[numb] });
continue;
}

// 处理连接.
if(out&W) link_to_west(x,y);
if(out&E) link_to_east(x,y);
if(out&N) link_to_north(x,y);
if(out&S) link_to_south(x,y);

// 当前房间处理完毕.
newpath -= ({ newpath[numb] });
}
while (sizeof(newpath));

switch (entry_dir)
{
case "west":
for(i=0;iif(all[l-1][i])
{
temp = new(class coordinate);
temp->x = l-1;
temp->y = i;
valid_leaves += ({temp});
}
break;
case "east":
for(i=0;iif(all[0][i])
{
temp = new(class coordinate);
temp->x = 0;
temp->y = i;
valid_leaves += ({temp});
}
break;
case "south":
for(i=0;iif(all[i][l-1])
{
temp = new(class coordinate);
temp->x = i;
temp->y = l-1;
valid_leaves += ({temp});
}
break;
case "north":
for(i=0;iif(all[i][0])
{
temp = new(class coordinate);
temp->x = i;
temp->y = 0;
valid_leaves += ({temp});
}
break;
}

if( !(i=sizeof(valid_leaves)) ) // 没有出口 须重新建立
{
call_other(this_object(),"create_maze");
return;
}

if(i == 1)
leave = valid_leaves[0];
else
leave = valid_leaves[random(i)]; // 随机选一个.

switch (entry_dir)
{
case "south":
all[leave->x][leave->y] |= N;
break;
case "north":
all[leave->x][leave->y] |= S;
break;
case "west":
all[leave->x][leave->y] |= E;
break;
case "east":
all[leave->x][leave->y] |= W;
break;
}

// 迷宫创建完毕。
maze_built = 1;

// 绘制完成的迷宫地图。
// 地图文件为同目录下同名的'.map' 文件,
// 绘制地图也许可利于区域巫师的工作。
// 如需要可开放物件对于本目录的'写'。
//paint_vrm_map();
}

private void link_to_west(int x,int y) // The west room is (x-1,y)
{
class coordinate temp;
// can't link. 当前房间已经是最西面的房间了.
if( (x-1) < 0 )
return;

temp = new(class coordinate);
temp->x = x-1;
temp->y = y;

// 西面的房间已经于 path 中,或者 已在待处理列表 newpath 中.
if(all[temp->x][temp->y] /*|| member_array(temp,newpath)*/)
return;

all[x][y] |= W;
all[temp->x][temp->y] |= E;
newpath += ({temp});
}

private void link_to_east(int x,int y) // The east room is (x+1,y)
{
class coordinate temp;
// can't link. 当前房间已经是最东面的房间了.
if( (x+1) >= l )
return;

temp = new(class coordinate);
temp->x = x+1;
temp->y = y;

// 东面的房间已经于 path 中,或者 已在待处理列表 newpath 中.
if(all[temp->x][temp->y] /*|| member_array(temp,newpath)*/)
return;

all[x][y] |= E;
all[temp->x][temp->y] |= W;
newpath += ({temp});
}

private void link_to_south(int x,int y) // The south room is (x,y-1)

{
class coordinate temp;
// can't link. 当前房间已经是最南端的房间了.
if( (y-1) <0 )
return;

temp = new(class coordinate);
temp->x = x;
temp->y = y-1;

// 南端的房间已经于 path 中,或者 已在待处理列表 newpath 中.
if(all[temp->x][temp->y] /*|| member_array(temp,newpath)*/)
return;

all[x][y] |= S;
all[temp->x][temp->y] |= N;
newpath += ({temp});
}

private void link_to_north(int x,int y) // The north room is (x,y+1)

{
class coordinate temp;
// can't link. 当前房间已经是最北端的房间了.
if( (y+1) >= l )
return;

temp = new(class coordinate);
temp->x = x;
temp->y = y+1;

// 北端的房间已经于 path 中,或者 已在待处理列表 newpath 中.
if(all[temp->x][temp->y] /*|| member_array(temp,newpath)*/)
return;

all[x][y] |= N;
all[temp->x][temp->y] |= S;
newpath += ({temp});
}

// 绘制已建成迷宫的地图.
private void paint_vrm_map()
{
string hor = "─" ,ver = "│ ",room = "◎",sroom = "●";
int x,y;
string output = "",map_file;

for(y=(l-1);y>=0;y--)
{
reset_eval_cost();

output += sprintf("y=%-3d: ",y);
for(x=0;x{
output += sprintf("%s",
(( (x==enter->x) && (y==enter->y))
|| ( (x==leave->x) && (y==leave->y) ))?
sroom:room);

if( (all[x][y])&E ) // have east
output += hor;
else
output += " ";
}

output += "\n";
output += " ";
for(x=0;x{
if( (all[x][y])&S ) // have south
output += ver;
else
output += " ";
}
output += "\n";
}

map_file = sprintf( "%s.map",base_name(this_object()) );
write_file(map_file,output,1);
}

nomask int clean_up()
{
string fname;
int x,y;
object *maze_objs = ({}),link_room;

if(!maze_built)
{
destruct(this_object());
return 0;
}

fname = base_name(this_object());

if( objectp(link_room = find_object(sprintf("%s/entry",fname))) )
{
link_room->clean_up();
if( objectp(link_room) )
return 1;
}

if( objectp(link_room = find_object(sprintf("%s/exit",fname))) )
{
link_room->clean_up();
if( objectp(link_room) )
return 1;
}

for(x=0;xfor(y=0;yif(objectp(find_object(sprintf("%s/%d/%d",fname,x,y))))
maze_objs += ({find_object(sprintf("%s/%d/%d",fname,x,y))});

maze_objs->clean_up();
maze_objs -= ({0});

if(sizeof(maze_objs))
return 1;
else
{
destruct(this_object());
return 0;
}
}

// 巫师可以 update 区域迷宫主物件强制更新迷宫,
// 但此时迷宫中的玩家就要去 VOID 了。
void remove(string euid)
{
string fname = base_name(this_object());
object m_room;
int x,y;

for(x=0;xfor(y=0;yif(objectp(m_room = find_object(sprintf("%s/%d/%d",fname,x,y))))
destruct(m_room);
if(find_object(sprintf("%s/entry",fname)))
destruct(sprintf("%s/entry",fname));
if(find_object(sprintf("%s/exit",fname)))
destruct(sprintf("%s/exit",fname));
}

/**** 以下是预设迷宫参数的接口函数 ****/
// 迷宫的单边长
void set_maze_long(int mlong)
{
if(!intp(mlong))
return;

// 最小为 5,再小了没什么意义。
if( (mlong < 5) || mlong > MAX_LONG )
return;

l = mlong;
}

// 迷宫房间所继承的物件的档案名称。
void set_inherit_room( mixed rooms )
{
if(stringp(rooms))
{
// 此档案是否存在
if(file_size(sprintf("%s.c",rooms)) > 0)
inherit_rooms = ({ rooms });
return;
}

else if(arrayp(rooms))
{
foreach(string f in rooms)
{
if(!stringp(f) || f == "")
return;
if(file_size(sprintf("%s.c",f)) <= 0)
return;
}
inherit_rooms = rooms;
return;
}

return;
}

// 入口方向(出口在对面)
void set_entry_dir(string dir)
{
if(!stringp(dir))
return;

// 入口方向的合法性检查.
if(member_array(dir,valid_dirs) == -1)
return;

entry_dir = dir;
}

//入口与区域的连接方向
void set_link_entry_dir(string dir)
{
if(!stringp(dir) || dir == "")
return;

link_entry_dir = dir;
}

// 迷宫入口所连接区域档案的文件名
void set_link_entry_room(string lroom)
{
if(!stringp(lroom) || lroom == "")
return;

if(file_size(sprintf("%s.c",lroom)) <= 0)
return;

link_entry_room = lroom;
}

//出口与区域的连接方向
void set_link_exit_dir(string dir)
{
if(!stringp(dir) || dir == "")
return;

link_exit_dir = dir;
}

// 迷宫出口所连接区域档案的文件名
void set_link_exit_room(string lroom)
{
if(!stringp(lroom) || lroom == "")
return;

if(file_size(sprintf("%s.c",lroom)) <= 0)
return;

link_exit_room = lroom;
}

// 迷宫入口的短描述
void set_entry_short(string desc)
{
if(!stringp(desc) || desc == "")
return;

entry_short = desc;
}

// 迷宫入口的长描述
void set_entry_desc(string desc)
{
if(!stringp(desc) || desc == "")
return;

entry_desc = desc;
}

// 迷宫出口的短描述
void set_exit_short(string desc)
{
if(!stringp(desc) || desc == "")
return;

exit_short = desc;
}

// 迷宫出口的长描述
void set_exit_desc(string desc)
{
if(!stringp(desc) || desc == "")
return;

exit_desc = desc;
}

//迷宫房间的短描述
void set_maze_room_short(string desc)
{
if(!stringp(desc) || desc == "")
return;

maze_room_short = desc;
}

//迷宫房间的描述,如果有多条描述,制造每个房
//间的时候会从中随机选择一个。
void set_maze_room_desc(mixed desces)
{
if(stringp(desces))
{
maze_room_desc = ({ desces });
return;
}

if(arrayp(desces))
{
foreach(string desc in desces)
if(!stringp(desc))
return;
maze_room_desc = desces;
return;
}
}

// 迷宫房间是否为户外房间
void set_outdoors(int outd)
{
if(!intp(outd))
return;

if(outd)
is_outdoors = 1;
}

// 迷宫中的怪物
void set_maze_npcs(mixed npc)
{
if(stringp(npc))
{
// 此档案是否存在
if(file_size(sprintf("%s.c",npc)) > 0)
maze_npcs = ({ npc });
return;
}

else if(arrayp(npc))
{
foreach(string f in npc)
{
if(!stringp(f) || f == "")
return;
if(file_size(sprintf("%s.c",f)) <= 0)
return;
}
maze_npcs = npc;
return;
}

return;

}

/**** 以上是预设迷宫参数的接口函数 ****/

// 创造迷宫房间,由 VIRTUAL_D 调用。
nomask object query_maze_room(string str)
{
int random_rate = 20; // 房间内放置 npc 的可能性
int idx,x,y,exits;
object ob;
string f;

if( previous_object() && (geteuid(previous_object()) != ROOT_UID) )
return 0;

if(!stringp(str) || str == "")
return 0;

if(!maze_built) // 迷宫未建立
create_maze();
if(!maze_built)
return 0;

if(str == "entry") // 迷宫入口房间
{
f = inherit_rooms[random(sizeof(inherit_rooms))];

ob = new(f);
if(!ob)
return 0;
ob->set("virtual_room",1);
ob->set("short",entry_short);
ob->set("long",entry_desc);
if(is_outdoors)
ob->set("outdoors",1);
ob->set(sprintf("exits/%s",link_entry_dir),link_entry_room);
ob->set(sprintf("exits/%s",reverse_dir[entry_dir]),mroom_fname(enter

->x,enter->y));
if( sizeof(maze_npcs) && (random(100) <= random_rate) )
{
ob->set("objects",([
maze_npcs[random(sizeof(maze_npcs))] : 1,
]));
ob->setup();
}
return ob;
}

if(str == "exit") // 迷宫出口房间
{
f = inherit_rooms[random(sizeof(inherit_rooms))];

ob = new(f);
if(!ob)
return 0;

ob->set("virtual_room",1);
ob->set("short",exit_short);
ob->set("long",exit_desc);
if(is_outdoors)
ob->set("outdoors",1);
ob->set(sprintf("exits/%s",link_exit_dir),link_exit_room);
ob->set(sprintf("exits/%s",entry_dir),
mroom_fname(leave->x,leave->y));
if( sizeof(maze_npcs) && (random(100) <= random_rate) )
{
ob->set("objects",([
maze_npcs[random(sizeof(maze_npcs))] : 1,
]));
ob->setup();
}
return ob;
}

idx = member_array('/', str);
if( idx == -1 )
return 0;

if(!sscanf(str[0..idx-1],"%d",x))
return 0;
if(!sscanf(str[idx+1..],"%d",y))
return 0;

if( !exits = all[x][y] )
return 0;

f = inherit_rooms[random(sizeof(inherit_rooms))];
ob = new(f);
if(!ob)
return 0;

ob->set("virtual_room",1);
ob->set("short",maze_room_short);
ob->set("long",maze_room_desc[random(sizeof(maze_room_desc))]);
if(is_outdoors)
ob->set("outdoors",1);

if(exits&W)
ob->set("exits/west",mroom_fname(x-1,y));
if(exits&E)
ob->set("exits/east",mroom_fname(x+1,y));
if(exits&N)
ob->set("exits/north",mroom_fname(x,y+1));
if(exits&S)
ob->set("exits/south",mroom_fname(x,y-1));

if( (x == enter->x) && (y == enter->y) )
ob->set(sprintf("exits/%s",entry_dir),
sprintf("%s/entry",base_name(this_object())));
if( (x == leave->x) && (y == leave->y) )
ob->set(sprintf("exits/%s",reverse_dir[entry_dir]),
sprintf("%s/exit",base_name(this_object())));

if( sizeof(maze_npcs) && (random(100) <= random_rate) )
{
ob->set("objects",([
maze_npcs[random(sizeof(maze_npcs))] : 1,
]));
ob->setup();
}

return ob;
}

Tuesday, September 07, 2004

 

计算几何常用算法概览

原作者:怒火之袍
出处:放飞网

一、引言

计算机的出现使得很多原本十分繁琐的工作得以大幅度简化,但是也有一些在人们直观看来很容易的问题却需要拿出一套并不简单的通用解决方案,比如几何问题。作为计算机科学的一个分支,计算几何主要研究解决几何问题的算法。在现代工程和数学领域,计算几何在图形学、机器人技术、超大规模集成电路设计和统计等诸多领域有着十分重要的应用。在本文中,我们将对计算几何常用的基本算法做一个全面的介绍,希望对您了解并应用计算几何的知识解决问题起到帮助。

二、算法介绍

矢量的概念:

如果一条线段的端点是有次序之分的,我们把这种线段成为有向线段(directed segment)。如果有向线段p1p2的起点p1在坐标原点,我们可以把它称为矢量(vector)p2。

矢量加减法:

设二维矢量P = ( x1,y1 ) ,Q = ( x2 , y2 ) ,则矢量加法定义为: P + Q = ( x1 + x2 , y1 + y2 ),同样的,矢量减法定义为: P - Q = ( x1 - x2 , y1 - y2 )。显然有性质 P + Q = Q + P , P - Q = - ( Q - P )。

矢量叉积:

计算矢量叉积是与直线和线段相关算法的核心部分。设矢量P = (x1,y1) ,Q = (x2,y2),则矢量叉积定义为由(0,0)、p1、p2和p1+p2所组成的平行四边形的带符号的面积,即:P × Q = x1*y2 - x2*y1,其结果是一个标量。显然有性质 P × Q = - ( Q × P ) 和 P × ( - Q ) = - ( P × Q )。一般在不加说明的情况下,本文下述算法中所有的点都看作矢量,两点的加减法就是矢量相加减,而点的乘法则看作矢量叉积。

叉积的一个非常重要性质是可以通过它的符号判断两矢量相互之间的顺逆时针关系:

若 P × Q > 0 , 则P在Q的顺时针方向。
若 P × Q < 0 , 则P在Q的逆时针方向。
若 P × Q = 0 , 则P与Q共线,但可能同向也可能反向。

折线段的拐向判断:

折线段的拐向判断方法可以直接由矢量叉积的性质推出。对于有公共端点的线段p0p1和p1p2,通过计算(p2 - p0) × (p1 - p0)的符号便可以确定折线段的拐向:

若(p2 - p0) × (p1 - p0) > 0,则p0p1在p1点拐向右侧后得到p1p2。

若(p2 - p0) × (p1 - p0) < 0,则p0p1在p1点拐向左侧后得到p1p2。

若(p2 - p0) × (p1 - p0) = 0,则p0、p1、p2三点共线。

具体情况可参照下图:



判断点是否在线段上:

设点为Q,线段为P1P2 ,判断点Q在该线段上的依据是:( Q - P1 ) × ( P2 - P1 ) = 0 且 Q 在以 P1,P2为对角顶点的矩形内。前者保证Q点在直线P1P2上,后者是保证Q点不在线段P1P2的延长线或反向延长线上,对于这一步骤的判断可以用以下过程实现:

ON-SEGMENT(pi,pj,pk)

if min(xi,xj)<=xk<=max(xi,xj) and min(yi,yj)<=yk<=max(yi,yj)

then return true;

else return false;

特别要注意的是,由于需要考虑水平线段和垂直线段两种特殊情况,min(xi,xj)<=xk<=max(xi,xj)和min(yi,yj)<=yk<=max(yi,yj)两个条件必须同时满足才能返回真值。

判断两线段是否相交:

我们分两步确定两条线段是否相交:

(1)快速排斥试验

设以线段 P1P2 为对角线的矩形为R, 设以线段 Q1Q2 为对角线的矩形为T,如果R和T不相交,显然两线段不会相交。

(2)跨立试验

如果两线段相交,则两线段必然相互跨立对方。若P1P2跨立Q1Q2 ,则矢量 ( P1 - Q1 ) 和( P2 - Q1 )位于矢量( Q2 - Q1 ) 的两侧,即( P1 - Q1 ) × ( Q2 - Q1 ) * ( P2 - Q1 ) × ( Q2 - Q1 ) < 0。上式可改写成( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) > 0。当 ( P1 - Q1 ) × ( Q2 - Q1 ) = 0 时,说明 ( P1 - Q1 ) 和 ( Q2 - Q1 )共线,但是因为已经通过快速排斥试验,所以 P1 一定在线段 Q1Q2上;同理,( Q2 - Q1 ) ×(P2 - Q1 ) = 0 说明 P2 一定在线段 Q1Q2上。所以判断P1P2跨立Q1Q2的依据是:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。同理判断Q1Q2跨立P1P2的依据是:( Q1 - P1 ) × ( P2 - P1 ) * ( P2 - P1 ) × ( Q2 - P1 ) >= 0。具体情况如下图所示:



在相同的原理下,对此算法的具体的实现细节可能会与此有所不同,除了这种过程外,大家也可以参考《算法导论》上的实现。

判断线段和直线是否相交:

有了上面的基础,这个算法就很容易了。如果线段P1P2和直线Q1Q2相交,则P1P2跨立Q1Q2,即:( P1 - Q1 ) × ( Q2 - Q1 ) * ( Q2 - Q1 ) × ( P2 - Q1 ) >= 0。

判断矩形是否包含点:

只要判断该点的横坐标和纵坐标是否夹在矩形的左右边和上下边之间。


判断线段、折线、多边形是否在矩形中:

因为矩形是个凸集,所以只要判断所有端点是否都在矩形中就可以了。

判断矩形是否在矩形中:

只要比较左右边界和上下边界就可以了。

判断圆是否在矩形中:

很容易证明,圆在矩形中的充要条件是:圆心在矩形中且圆的半径小于等于圆心到矩形四边的距离的最小值。

判断点是否在多边形中:

判断点P是否在多边形中是计算几何中一个非常基本但是十分重要的算法。以点P为端点,向左方作射线L,由于多边形是有界的,所以射线L的左端一定在多边形外,考虑沿着L从无穷远处开始自左向右移动,遇到和多边形的第一个交点的时候,进入到了多边形的内部,遇到第二个交点的时候,离开了多边形,……所以很容易看出当L和多边形的交点数目C是奇数的时候,P在多边形内,是偶数的话P在多边形外。

但是有些特殊情况要加以考虑。如图下图(a)(b)(c)(d)所示。在图(a)中,L和多边形的顶点相交,这时候交点只能计算一个;在图(b)中,L和多边形顶点的交点不应被计算;在图(c)和(d) 中,L和多边形的一条边重合,这条边应该被忽略不计。如果L和多边形的一条边重合,这条边应该被忽略不计。



为了统一起见,我们在计算射线L和多边形的交点的时候,1。对于多边形的水平边不作考虑;2。对于多边形的顶点和L相交的情况,如果该顶点是其所属的边上纵坐标较大的顶点,则计数,否则忽略;3。对于P在多边形边上的情形,直接可判断P属于多边行。由此得出算法的伪代码如下:

count ← 0;
以P为端点,作从右向左的射线L;
for 多边形的每条边s
do if P在边s上
then return true;
if s不是水平的
then if s的一个端点在L上
if 该端点是s两端点中纵坐标较大的端点
then count ← count+1
else if s和L相交
then count ← count+1;
if count mod 2 = 1
then return true;
else return false;


其中做射线L的方法是:设P'的纵坐标和P相同,横坐标为正无穷大(很大的一个正数),则P和P'就确定了射线L。

判断点是否在多边形中的这个算法的时间复杂度为O(n)。

另外还有一种算法是用带符号的三角形面积之和与多边形面积进行比较,这种算法由于使用浮点数运算所以会带来一定误差,不推荐大家使用。

判断线段是否在多边形内:

线段在多边形内的一个必要条件是线段的两个端点都在多边形内,但由于多边形可能为凹,所以这不能成为判断的充分条件。如果线段和多边形的某条边内交(两线段内交是指两线段相交且交点不在两线段的端点),因为多边形的边的左右两侧分属多边形内外不同部分,所以线段一定会有一部分在多边形外(见图a)。于是我们得到线段在多边形内的第二个必要条件:线段和多边形的所有边都不内交。

线段和多边形交于线段的两端点并不会影响线段是否在多边形内;但是如果多边形的某个顶点和线段相交,还必须判断两相邻交点之间的线段是否包含于多边形内部(反例见图b)。



因此我们可以先求出所有和线段相交的多边形的顶点,然后按照X-Y坐标排序(X坐标小的排在前面,对于X坐标相同的点,Y坐标小的排在前面,这种排序准则也是为了保证水平和垂直情况的判断正确),这样相邻的两个点就是在线段上相邻的两交点,如果任意相邻两点的中点也在多边形内,则该线段一定在多边形内。

证明如下:


命题1:
如果线段和多边形的两相邻交点P1 ,P2的中点P' 也在多边形内,则P1, P2之间的所有点都在多边形内。


证明:
假设P1,P2之间含有不在多边形内的点,不妨设该点为Q,在P1, P'之间,因为多边形是闭合曲线,所以其内外部之间有界,而P1属于多边行内部,Q属于多边性外部,P'属于多边性内部,P1-Q-P'完全连续,所以P1Q和QP'一定跨越多边形的边界,因此在P1,P'之间至少还有两个该线段和多边形的交点,这和P1P2是相邻两交点矛盾,故命题成立。证毕。

由命题1直接可得出推论:
推论2:
设多边形和线段PQ的交点依次为P1,P2,……Pn,其中Pi和Pi+1是相邻两交点,线段PQ在多边形内的充要条件是:P,Q在多边形内且对于i =1, 2,……, n-1,Pi ,Pi+1的中点也在多边形内。

在实际编程中,没有必要计算所有的交点,首先应判断线段和多边形的边是否内交,倘若线段和多边形的某条边内交则线段一定在多边形外;如果线段和多边形的每一条边都不内交,则线段和多边形的交点一定是线段的端点或者多边形的顶点,只要判断点是否在线段上就可以了。
至此我们得出算法如下:

if 线端PQ的端点不都在多边形内
then return false;
点集pointSet初始化为空;
for 多边形的每条边s
do if 线段的某个端点在s上
then 将该端点加入pointSet;
else if s的某个端点在线段PQ上
then 将该端点加入pointSet;
else if s和线段PQ相交 // 这时候已经可以肯定是内交了
then return false;
将pointSet中的点按照X-Y坐标排序;
for pointSet中每两个相邻点 pointSet[i] , pointSet[ i+1]
do if pointSet[i] , pointSet[ i+1] 的中点不在多边形中
then return false;
return true;

这个过程中的排序因为交点数目肯定远小于多边形的顶点数目n,所以最多是常数级的复杂度,几乎可以忽略不计。因此算法的时间复杂度也是O(n)。

判断折线是否在多边形内:

只要判断折线的每条线段是否都在多边形内即可。设折线有m条线段,多边形有n个顶点,则该算法的时间复杂度为O(m*n)。

判断多边形是否在多边形内:

只要判断多边形的每条边是否都在多边形内即可。判断一个有m个顶点的多边形是否在一个有n个顶点的多边形内复杂度为O(m*n)。

判断矩形是否在多边形内:

将矩形转化为多边形,然后再判断是否在多边形内。

判断圆是否在多边形内:

只要计算圆心到多边形的每条边的最短距离,如果该距离大于等于圆半径则该圆在多边形内。计算圆心到多边形每条边最短距离的算法在后文阐述。

判断点是否在圆内:

计算圆心到该点的距离,如果小于等于半径则该点在圆内。

判断线段、折线、矩形、多边形是否在圆内:

因为圆是凸集,所以只要判断是否每个顶点都在圆内即可。

判断圆是否在圆内:

设两圆为O1,O2,半径分别为r1, r2,要判断O2是否在O1内。先比较r1,r2的大小,如果r1
计算点到线段的最近点:

如果该线段平行于X轴(Y轴),则过点point作该线段所在直线的垂线,垂足很容易求得,然后计算出垂足,如果垂足在线段上则返回垂足,否则返回离垂足近的端点;如果该线段不平行于X轴也不平行于Y轴,则斜率存在且不为0。设线段的两端点为pt1和pt2,斜率为:k = ( pt2.y - pt1. y ) / (pt2.x - pt1.x );该直线方程为:y = k* ( x - pt1.x) + pt1.y。其垂线的斜率为 - 1 / k,垂线方程为:y = (-1/k) * (x - point.x) + point.y 。

联立两直线方程解得:x = ( k^2 * pt1.x + k * (point.y - pt1.y ) + point.x ) / ( k^2 + 1) ,y = k * ( x - pt1.x) + pt1.y;然后再判断垂足是否在线段上,如果在线段上则返回垂足;如果不在则计算两端点到垂足的距离,选择距离垂足较近的端点返回。

计算点到折线、矩形、多边形的最近点:

只要分别计算点到每条线段的最近点,记录最近距离,取其中最近距离最小的点即可。

计算点到圆的最近距离及交点坐标:

如果该点在圆心,因为圆心到圆周任一点的距离相等,返回UNDEFINED。

连接点P和圆心O,如果PO平行于X轴,则根据P在O的左边还是右边计算出最近点的横坐标为centerPoint.x - radius 或 centerPoint.x + radius。如果PO平行于Y轴,则根据P在O的上边还是下边计算出最近点的纵坐标为 centerPoint.y -+radius或 centerPoint.y - radius。如果PO不平行于X轴和Y轴,则PO的斜率存在且不为0,这时直线PO斜率为k = ( P.y - O.y )/ ( P.x - O.x )。直线PO的方程为:y = k * ( x - P.x) + P.y。设圆方程为:(x - O.x ) ^2 + ( y - O.y ) ^2 = r ^2,联立两方程组可以解出直线PO和圆的交点,取其中离P点较近的交点即可。

计算两条共线的线段的交点:

对于两条共线的线段,它们之间的位置关系有下图所示的几种情况。图(a)中两条线段没有交点;图 (b) 和 (d) 中两条线段有无穷焦点;图 (c) 中两条线段有一个交点。设line1是两条线段中较长的一条,line2是较短的一条,如果line1包含了line2的两个端点,则是图(d)的情况,两线段有无穷交点;如果line1只包含line2的一个端点,那么如果line1的某个端点等于被line1包含的line2的那个端点,则是图(c)的情况,这时两线段只有一个交点,否则就是图(b)的情况,两线段也是有无穷的交点;如果line1不包含line2的任何端点,则是图(a)的情况,这时两线段没有交点。



计算线段或直线与线段的交点:

设一条线段为L0 = P1P2,另一条线段或直线为L1 = Q1Q2 ,要计算的就是L0和L1的交点。

1. 首先判断L0和L1是否相交(方法已在前文讨论过),如果不相交则没有交点,否则说明L0和L1一定有交点,下面就将L0和L1都看作直线来考虑。

2. 如果P1和P2横坐标相同,即L0平行于Y轴

a) 若L1也平行于Y轴,

i. 若P1的纵坐标和Q1的纵坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;

b) 若L1不平行于Y轴,则交点横坐标为P1的横坐标,代入到L1的直线方程中可以计算出交点纵坐标;

3. 如果P1和P2横坐标不同,但是Q1和Q2横坐标相同,即L1平行于Y轴,则交点横坐标为Q1的横坐标,代入到L0的直线方程中可以计算出交点纵坐标;

4. 如果P1和P2纵坐标相同,即L0平行于X轴

a) 若L1也平行于X轴,

i. 若P1的横坐标和Q1的横坐标相同,说明L0和L1共线,假如L1是直线的话他们有无穷的交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
ii. 否则说明L0和L1平行,他们没有交点;

b) 若L1不平行于X轴,则交点纵坐标为P1的纵坐标,代入到L1的直线方程中可以计算出交点横坐标;

5. 如果P1和P2纵坐标不同,但是Q1和Q2纵坐标相同,即L1平行于X轴,则交点纵坐标为Q1的纵坐标,代入到L0的直线方程中可以计算出交点横坐标;

6. 剩下的情况就是L1和L0的斜率均存在且不为0的情况

a) 计算出L0的斜率K0,L1的斜率K1 ;

b) 如果K1 = K2

i. 如果Q1在L0上,则说明L0和L1共线,假如L1是直线的话有无穷交点,假如L1是线段的话可用"计算两条共线线段的交点"的算法求他们的交点(该方法在前文已讨论过);
ii. 如果Q1不在L0上,则说明L0和L1平行,他们没有交点。
c) 联立两直线的方程组可以解出交点来

这个算法并不复杂,但是要分情况讨论清楚,尤其是当两条线段共线的情况需要单独考虑,所以在前文将求两条共线线段的算法单独写出来。另外,一开始就先利用矢量叉乘判断线段与线段(或直线)是否相交,如果结果是相交,那么在后面就可以将线段全部看作直线来考虑。需要注意的是,我们可以将直线或线段方程改写为ax+by+c=0的形式,这样一来上述过程的部分步骤可以合并,缩短了代码长度,但是由于先要求出参数,这种算法将花费更多的时间。

求线段或直线与折线、矩形、多边形的交点:

分别求与每条边的交点即可。

求线段或直线与圆的交点:

设圆心为O,圆半径为r,直线(或线段)L上的两点为P1,P2。

1. 如果L是线段且P1,P2都包含在圆O内,则没有交点;否则进行下一步。

2. 如果L平行于Y轴,

a) 计算圆心到L的距离dis;
b) 如果dis > r 则L和圆没有交点;
c) 利用勾股定理,可以求出两交点坐标,但要注意考虑L和圆的相切情况。

3. 如果L平行于X轴,做法与L平行于Y轴的情况类似;

4. 如果L既不平行X轴也不平行Y轴,可以求出L的斜率K,然后列出L的点斜式方程,和圆方程联立即可求解出L和圆的两个交点;

5. 如果L是线段,对于2,3,4中求出的交点还要分别判断是否属于该线段的范围内。

凸包的概念:

点集Q的凸包(convex hull)是指一个最小凸多边形,满足Q中的点或者在多边形边上或者在其内。下图中由红色线段表示的多边形就是点集Q={p0,p1,...p12}的凸包。





凸包的求法:

现在已经证明了凸包算法的时间复杂度下界是O(n*logn),但是当凸包的顶点数h也被考虑进去的话,Krikpatrick和Seidel的剪枝搜索算法可以达到O(n*logh),在渐进意义下达到最优。最常用的凸包算法是Graham扫描法和Jarvis步进法。本文只简单介绍一下Graham扫描法,其正确性的证明和Jarvis步进法的过程大家可以参考《算法导论》。

对于一个有三个或以上点的点集Q,Graham扫描法的过程如下:

令p0为Q中Y-X坐标排序下最小的点
为对其余点按以p0为中心的极角逆时针排序所得的点集(如果有多个点有相同的极角,除了距p0最远的点外全部移除
压p0进栈S
压p1进栈S
压p2进栈S
for i ← 3 to m
do while 由S的栈顶元素的下一个元素、S的栈顶元素以及pi构成的折线段不拐向左侧
对S弹栈
压pi进栈S
return S;


此过程执行后,栈S由底至顶的元素就是Q的凸包顶点按逆时针排列的点序列。需要注意的是,我们对点按极角逆时针排序时,并不需要真正求出极角,只需要求出任意两点的次序就可以了。而这个步骤可以用前述的矢量叉积性质实现。

Monday, September 06, 2004

 

国际象棋程序设计

发信人: auntyellow (黄阿姨), 信区: AI
标 题: 国际象棋程序设计(一):引言(转译)
发信站: BBS 水木清华站 (Mon Nov 8 20:46:55 2004), 站内

【 以下文字转载自 Chess 讨论区 】
发信人: auntyellow (黄阿姨), 信区: Chess
标 题: 国际象棋程序设计(一):引言(转译)
发信站: BBS 水木清华站 (Mon Nov 8 20:45:01 2004), 站内

 
国际象棋程序设计(一):引言
 
Fran?ois Dominic Laramée/文
 
  这是国际象棋程序设计连载的第一部分,本连载共有六部分,他们不仅仅是针对象棋【译注:以后如不特别指出,都指国际象棋】的,还可以运用到别的益智类游戏中。
  在人工智能领域中,专家对象棋进行了大量卓有成效的研究,这其中就有电脑对抗卡斯帕罗夫等世界冠军的比赛。象棋在人工智能上的地位,就相当于果蝇在遗传学上的地位,举足轻重。我的连载将着重介绍人工智能的程序设计艺术,这其中包括“深蓝”(Deep Blue)等著名程序。
  我的连载从2000年4月开始,每个月一次,到10月结束的时候,我会用Java写一个简单的程序来实现对弈。到时候你们可以从我的网站上随便下载,耐心地等吧。
 
信息完备的游戏
 
  象棋是“信息完备”的游戏,因为游戏双方面对的局面是同一个局面,任何一方所掌握的棋子及其位置的信息是一样的。除了象棋以外,西洋跳棋(Checkers)、围棋(Go)、五子棋(Go-Moku)【这是我猜的,可能不是,因为五子棋流行于日本,名称好像叫Renju】、西洋双陆棋(Backgammon)、黑白棋(Othello)【也有称Reversi的,可译为“翻棋”】可等也属于这一范畴。但是纸牌游戏却不是,因为你不知道对手手上的牌是什么【在中国的棋类游戏中,陆站棋(起源于欧洲)和四国大战棋也不是】。
  我的连载中将提到各种算法,大多数算法对所有的信息完备的游戏都是有效的,只是细节上有所不同罢了。很明显,无论棋盘、着法、位置等因素有那些,搜索算法就是搜索算法,它不会因为游戏规则而改变。
 
我们需要什么?
 
  能下棋的电脑软件至少要包括下列组件:
 
  1. 棋盘的表示方法,即局面在存储器中的存储方法,程序是根据它来分析局面的;
  2. 掌握规则,即什么样的着法是合理的,如果程序连不合理的着法都不能检测出来,那么对手就可以利用这种着法来欺骗程序;
  3. 找出所有合理着法的算法,这样程序就可以从这些着法中找到最好的,而不是随便找一种着法;
  4. 比较方法,包括比较着法的方法和比较局面的方法,这样程序就可以选择最佳的着法;
  5. 用户界面。
 
  本连载将涉及以上除了用户界面以外的所有内容,用户界面在所有二维棋类游戏中都是差不多的,这里就不作介绍了。接下来将对以上几个部分作逐一介绍,并且引出许多重要的概念。
 
棋盘的表示方法
 
  在早期的程序设计过程中,存储器是非常有限的(有些程序只用8K或更少的存储器),所以最简单、最节省的表示方法就是最有效的方法。一个典型的国际象棋棋盘可以用一个8x8的数组表示,棋盘上的每个格子用一个字节表示——空的格子用0,黑方的王用1,等等。
  如今,象棋程序可以在64位计算机上运行了,精心设计的“位棋盘”表示诞生了。在上世纪60年代后期【原文写于2000年,就当时来说并不能算“上世纪”】,位棋盘在苏联诞生,一个位棋盘由一个64位的字【“字”是计算机中一次运算所涉及的存储单元,我认为当时还没有字长为64位的计算机,所以一个位棋盘应该由多个较短的字来构成,如8个8位的字或4个16位的字,即便是现在的个人电脑上,一个位棋盘也必须由两个32位的字构成】来表示局面中的某个状态,一位代表一个格子。例如,一个位棋盘能表示“所有被黑兵占有的格子”,或者“处于e3格的后可以走的格子”,或者“被黑马攻击的白子所处的格子”,等等。位棋盘用途广泛,并且具有很快的运算速度,因为局面分析时要做大量的逻辑运算【就是“与或非”运算,也称布尔代数】,而一个位棋盘的运算只需要一次操作就可以了。
  这部分内容将在连载的第二部分作详细介绍。
 
着法的产生
 
  所谓棋类游戏的规则,指的就是某一方可以走哪些着法。某些游戏很容易就找到合理着法,例如在井字棋中【Tic-Tac-Toe,在3x3的棋盘上轮流占格子,先在同一条线(横线、纵线或斜线)上占有3枚棋子者得胜】,所有空的格子都是合理着法。但是在象棋中,情况就有些复杂了,每个棋子都有它特定的着法,例如兵吃子时走斜线,而不吃子时走纵线,又例如把王走到被将军的格子是不允许的,还有诸如“吃过路兵”【法语en passant】、兵的升变、王车易位等着法只有在特殊场合才是合理的。
  事实上在象棋程序设计中,着法的产生已经被证实为最复杂和最费时的事。幸运的是,着法的产生有一些预处理的技巧,我还会介绍一些数据结构,它们能显著提高着法产生的速度。
  这部分内容将在连载的第三部分作详细介绍。
 
搜索技巧
 
  对于计算机来说,判断一个着法是好的或坏的,并不是件容易的事。判断着法优劣的最佳办法,就是看它们的后续结果,只有推演以后一系列的着法,才能确定看那步是好的。在保证不犯错误的前提下,我们要设想对手会走出最好的应着。这一基本原理称为“最小-最大”搜索算法,它是所有象棋程序的基础。
  不幸的是,“最小-最大”法的运算量是O(bn)【数学上指它和bn是一个数量级的】,b(分支因子)指平均每步的合理着法【有研究表明,在国际象棋中这个值约为38,中国象棋则更多些,为42(这是中国象棋程序“七星大师”的作者赵德志的研究结果)】,n(深度)指思考的步数(一回合有两步)。所以当步数增长时,运算量以几何级数迅速增长,如果要思考得更深一些,就必须用更为合理的算法。其中,迭代加深的Alpha-Beta搜索、NegaScout搜索和MTD(f)搜索是最基本的算法,这些会在连载的第四部分介绍。除此以外,还要依靠数据结构和启发式算法的帮助,启发式算法是增强棋力的算法,例如换位表(Transposition Tables)、历史启发和将杀启发(History/Killer Heuristic)等。
  在象棋程序设计中,另一个头痛的问题是“水平线效应”(Horizon Effect),它首先由Hans Berliner提出。假设你的程序的搜索深度是8步,并且程序算出对手会在第六步捉死你的后。按照程序自己的设想,它会献出象来延缓后的捉死(假定这样做可以让后在第10步才被捉死),因为程序只能看到8步。从程序的角度看,后是被“保住”了,因为在它的搜索范围内后没有被捉死,但事实上却多丢了一个象。从这个例子可以看出,要把程序的工作重心放置到位,并不是一件简单的事情【意思是,某些变化没有必要搜索得太深,而关键的变化需要更深层次的搜索】,如果把每条变化都搜索到同一深度,那么结果是自取灭亡。很多技术是用来克服水平线效应,在连载的第五部分关于高级搜索的阐述中,将要介绍静态搜索(Quiescence Search)和深蓝(Deep Blue)的单步扩展方法(Singular Extensions)。
 
评价局面
 
  最后,程序必须有一个估计局面(占优或处于劣势)的方法。局面估计方法完全取决于规则(即子的走法)——在象棋中,“子力平衡”(Material Balance)是主导因素,因为一个小小的兵的领先就可能足以保证优势一方取得胜利【而在中国象棋中,这算不了什么,这足以证明本节的观点——局面估计方法完全取决于规则】,而在五子棋(Go-Moku)中却没什么影响,在黑白棋(Othello)里,根据子力上的数值分析局面则完全会成为误导,你可能一直处于领先状态,但最后几步局面却翻了盘。
  建立有效的局面评估方法,这常常会成为程序设计中的难点和焦点。连载的第六部分将详细阐述著名象棋程序的局面评估方法,其中包括Chess 4.5、Cray Blitz和Belle(尤物)。
 
结论
 
  我们已经找到了完成拼版的所需要的碎片,现在是开始动手做的时候了。下个月我将介绍最常用的棋盘表示方法,尽请关注。
 
  Fran?ois Dominic Laramée,2000年4月
 
  出处:www.gamedev.net
  译者:黄晨 (auntyellow@citiz.net)
  类型:全译

上一篇 下一篇


--

※ 修改:·auntyellow 于 Nov 8 20:49:00 修改本文·[FROM: 202.120.224.*]
※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.120.224.*]

发信人: auntyellow (黄阿姨), 信区: AI
标 题: 国际象棋程序设计(二):数据结构
发信站: BBS 水木清华站 (Mon Nov 8 20:50:14 2004), 站内

[以下文字转载自 Chess 讨论区 ]
发信人: auntyellow (黄阿姨), 信区: Chess
标 题: 国际象棋程序设计(二):数据结构
发信站: BBS 水木清华站 (Mon Nov 8 20:50:07 2004), 站内

国际象棋程序设计(二):数据结构
 
Fran?ois Dominic Laramée/文
 
  上个月我简要介绍了象棋程序设计中所需要的知识,其他信息完全的双人游戏也是一
样的。现在我们将讨论一些细节——棋盘的内部表示方法。
  在棋盘表示方法这个理念上,近三十年内没有多大发展,你可能会觉得很吃惊。它的
发展需要智慧的推动,很早就有人提出过绝妙的方案了,但同时也受到制约,因为这些方
案需要数据结构的支持,某些数据结构至今还没有实现。
  尽管如此,我还是会介绍三种数据结构,尽管它们并不是必需的,但是对于提高你的
下棋水平是大有帮助的。其中两种可以加快思考速度(但是其中一种需要无限多的存储器)
,另一种可以加快着法产生速度。【译注:分别指后面要提到的换位表、历史表和着法生
成预处理的数据库。】
  在我们继续讨论之前,我提一句格言:“无论是象棋还是其他游戏,你通常使用的数
据结构,应该是能达到目的的最简单的数据结构。”然而象棋程序设计者提出了很多技巧
,它们能让程序运行的更快,其中相当多的还适用于其他游戏。如果你对你要设计的游戏
不很了解,而且手头的资料很有限,那么你应该好好掌握我所提到的这些技巧,你可以把
这些技巧试验到你的程序上。
 
基本的棋盘表示
 
  在上世纪70年代,个人电脑的存储器是稀有资源,所以棋盘表示得越紧凑越好。很多
人会很自信地说:用一个64字节的数组,每个字节表示棋盘上的一个格子,用一个整数就
可以表示格子的位置了。(任何棋盘的数据结构都必须用一些额外的字节,来记录吃过路
兵的目标格、王车易位权利等信息,但是这里我们暂且忽略它,因为这些因素可以独立处
理,而且处理方法大同小异。)
  后来又流行一些更优化的算法:
 
  1. 早期的SARGON【可能是一个象棋程序】扩展了64字节的数组,在它的外围加了两
圈“虚格”,并在这些格子上作了非法标记。这一技巧能加快着法产生的速度,例如象在
走棋时会延斜线滑行,直到走到虚格上才中止。这样就没有必要用复杂的运算来预先判断
象到达的格子是否会超出存储器上的表示了。第二圈虚格是给马用的,例如位于盘角的马
试图跳出棋盘,这就必须用两圈虚格来保护。
  2. MYCHESS用了相反的方法,它只用32字节表示一个棋盘,每个字节代表一个棋子,
例如代表白方王、黑方王翼马前兵【英文居然是black King's Knight's Pawn,一开始让
我大惑不解】等,它存储的信息是棋盘上的位置,或者已经被吃的标记。这种技术有一个
缺点,它无法描述由兵升变而来的其他棋子(同时这个棋子在棋盘上还有一个)。在后来的
版本中,这个缺点被修正了。【其实这并不难办,一个字节取值从0到255,通常255表示
该子已被吃,从0到63表示该子在棋盘上的位置,兵通常是升变成后的,那么从64到127可
以表示该子已经升变为后,如果升变为车、马或象,则需要额外的字节来处理。】
 
  如今,这种极端吝啬的数据结构只可能出现在掌上电脑、手机或电视机机顶盒上,它
们的80~90%的资源都被操作系统占用,没有额外的空间给游戏使用。但是,某些游戏缺别
无选择地使用这种方法【我也不知道什么游戏非得使用这种方法不可】。
  想更多地了解以前的象棋程序,可以看一下David Welsh在1984年注写的《计算机象
棋》(Computer Chess)一书。
 
位棋盘
 
  用一个数组来表示棋盘,对于很多游戏来说,就找不到更好的办法了。但是对于像象
棋、西洋跳棋之类在64格棋盘上的游戏来说,有一个高明的技巧——“位棋盘” (首先由
苏联的KAISSA制作组提出),在上世纪60年代末诞生了。
  KAISSA是运行在64位处理器上的程序【我很怀疑当时就有64位处理器,或许当时处理
器字长的概念和现在的有所不同】。“64”恰巧是象棋棋盘格子的数目,所以这就有可能
让一个字来表示一个棋盘,以判断某个格子的状态是“是”或者“非”。例如,一个位棋
盘可以回答棋盘的每个格子“是否有白子”。【把位棋盘运用到中国象棋上,这是我将要
进行的一个课题,中国象棋的棋盘有90个格点,可以用3个32位的字来表示。】
  因此,一个完整的局面需要用12个位棋盘表示:白兵、白车、黑兵等等。再加上两个
用来表示“所有白子”和“所有黑子”的位棋盘,以加快运算速度。【其实只需要8个就
可以了,同一兵种(不管黑白)用一个位棋盘,一共是6个,再加上代表“所有白子”和“
所有黑子”的。做得更过分的是,有人把象和后并作一个位棋盘,车和后并作一个位棋盘
,这样又可以减少一个。如果要表示白方的象,只要“所有白子”、“所有车或后”的补
集(用“非”运算)、“所有象或后”这三个位棋盘作“与”运算就可以了。】或许你还想
用一个位棋盘表示被某种子力攻击到的格子,诸如此类,这些位棋可以盘灵活运用在着法
产生的运算过程中。
  位棋盘之所以有效,是因为很多运算可以转化为处理器的一个逻辑指令。例如,假设
你需要确认黑王被白后将军,如果用简单的数组来表示棋盘,那么你需要这样做:
 
  1. 首先找到后的位置,这需要从64个字节中一个一个地找;
  2. 然后在后所能走的八个方向找,直到找到王或者找到后走不到的格子为止。
 
  这些运算是相当花费时间的,如果后碰巧是在数组的最后一格,更糟的是,将军只会
发生在少数情况下【这种运算纯粹是白费时间!】。
  如果用位棋盘,那你只要这样做:
 
  1. 载入“白方后的位置”的位棋盘;
  2. 根据这个位置,从索引数据库中找到被后攻击的位棋盘;
  3. 用这个位棋盘和“黑方王的位置”的位棋盘作“与”运算。
 
  如果结果不是零,则说明黑王被白后将军。假设被后攻击的位棋盘是储藏于存储器中
的【这是上面提到的第二步的前提】,那么整个操作只需要3到4个时钟周期【通常计算机
执行1条指令需要1(算术或逻辑运算)到2(寻址操作)个时钟周期】。
  【这里允许我发挥一下,原作所说的“从索引的数据库中找到”(即上面提到的第二
步),其实并非是简单的一步,对于后的每个位置,都有一定的攻击格子(从边线到中心依
次是21、23、25和27格),但是要考虑被别的子阻挡的情况,程序无法为所有的情况都作
索引,最多只能对某条线(横线、纵线或斜线)的棋子占有情况作索引,这也需要28 =
256 种情况,再加后本身有64种位置,所以即使这样,数据库中也至少要保存256x64 =
16384个位棋盘。另外,横线、纵线和两条斜线的处理方法各不相同,横线只要作简单的
“移位运算”就可以了,而纵线和两条斜线都要用到“位棋盘旋转”的技术,为了提高运
算效率,程序的复杂程度是惊人的,细节可以参考《对弈程序基本技术》专题之《数据结
构——旋转的位棋盘》一文,文中作者多次提示读者用咖啡来提神,以完成烦琐的程序。

  再举一个例子,如果在当前的棋盘上,你要产生白马的所有着法,那么你只要找到当
与前位置相关联的“马能走到的格子”的位棋盘,并“与”(AND)上“所有被白方占有的
格子”的位棋盘的补集(就是对这个位棋盘作“非”(NOT)运算),因为马的着法限制仅仅
在于它不能去吃自己的子。【国际象棋比较简单,而中国象棋中还有“绊马腿”的限制(
还有象也是),这种情况该怎样使用位棋盘,也是我将要研究的课题。】
  如果你想更详细地了解位棋盘(也只是稍微详细一点而已),可以去看看描述CHESS
4.5 (它是由美国西北大学开发的)的文章——Peter Frey写的《人脑和电脑的象棋技巧》
(Ches Skill in Man and Machine),现在至少已经出了两版了,分别出版于1977年和
1981年。
  值得注意的事,到今天为止,几乎还没有真正意义上使用64位处理器的个人电脑,所
以位棋盘的速度优势是要打折扣的。尽管如此,位棋盘的技术仍是行之有效的。【苹果公
司的Macintosh图形工作站据说是64位处理器,但不知有没有针对这种电脑的象棋软件。
时隔4年,到我翻译这篇文章时,还没有什么别的64位处理器用在个人电脑上。因为毕竟
没这个必要,除非你专门用它来玩国际象棋。】
 
换位表
 
  在象棋里,有很多着法可以到达相同的位置。例如,不管你先走 1. P-K4 ... 2.
P-Q4或者1. P-Q4... 2.P-K4,【这里K4和Q4可能就代表e4和d4,在实战中有这样的例子
,1. e4 e6 2. d4和1. d4 e6, 2. e4是形成法兰西防御一种变例的两种途径。】最终局
面是一样的。有不同的路线可以达到同样位置的,这种现象称为“换位”(Transposing)
。【在中国象棋中,换位现象更为普遍,通常用成语“殊途同归”来称呼这种现象。】
  如果你的程序已经对1. P-Q4... 2.P-K4产生的结果竭尽全力作了搜索和评估,那么
你最好记住这个结果,以避免碰到1. P-K4... 2.P-Q4时再作同样的运算。自上世纪60年
代Richard Greenblatt的Mac Hack VI问世以来,所有的对弈程序都会吸纳“换位表”这
一技术,这就是原因所在。
  换位表存储的是已经搜索过的结果,它通常使用类似于散列表(Hash Dictionary)的
数据结构来达到最快的查询速度。在搜索某个局面时,结果(包括局面分析的值、搜索深
度、最佳着法等)就存储到换位表里。当搜索新的局面时,我们先从换位表里找,如果已
经有这种局面,那么就可以利用它,省去重复的搜索。
  这种处理有以下很多好处:
 
  1. 加快速度。在换位情况发生得很多时(特别是残局局面里,棋盘上棋子很少时),
90%以上的局面可以在表中找到。【在中国象棋中,这优势时更为明显,因为它的子力密
度小,在开局阶段就有很多“殊途同归”的现象。】
  2. 任意深度。假设你需要对某个局面搜索到一个指定的深度,例如4步(也就是两个
回合),如果换位表里有这个局面而且已经搜索了6步,那么你不仅可以跳过这次搜索,还
可以得到比预期更精确的结果。
  3. 用途广泛。通常每个象棋程序都配有“开局库”(Opening Book),即包含一些常
见局面及其最好的着法,这些通常是从已有的记载中提炼的【例如大师们写的“象棋开局
大全”或“象棋开局手册”之类的书,而我本人更倾向于从大量对局记录中提炼的结果】
。有了开局库,程序就不必在开局阶段就做傻事了【因为前人已经做过无数次的计算了】
。既然开局库的操作过程和换位表是一样的(即搜索局面),那么为什么不在棋局一开始就
把开局库装入我们的换位表里去呢?如果这样做,即使棋局暂时脱离了开局库,后来又回
到开局库里的局面【要注意,这个局面可以是棋局过程中出现的局面,但更多的情况是搜
索程序推演到的】,那么换位表里保留了这样的局面,我们仍旧有机会用到它。
 
  换位表唯一的缺点就是它贪婪地占用着存储器,无论如何它至少需要存储成千上万个
局面,百万甚至上亿就更好了。如果每个局面用16字节【用最紧凑的办法至少也需要32字
节(用MYCHESS这种吝啬的办法),但是这里可以存放“散列键值”,下面会提到这个技术
】,那么在存储器紧缺的时候这将成为很严重的问题。
  换位表还有其他用途。
  CHESS 4.5还用散列表来存储其他的局面计算结果【指下面提到的兵型、子力平衡等
】,这些计算结果在多数情况下是不会变动的,例如:
  1. 兵型(Pawn Structure)。散列表只存储兵的位置,这需要较小的存储空间,由于
兵的移动不会很频繁,所以99%的兵型局面可以在散列表中找到;【国际象棋的局面分析
中,需要考虑连兵、叠兵、孤兵、通路兵等因素,这些计算是相当费时的,而中国象棋就
没有这个必要了。】
  2. 子力平衡(Material Balance),即棋盘上子力的相对强弱,它只在吃子或兵升变
时变动。
  在CPU速度不快的今天,这些方法或许看来用处不是很大,但是它们还是有指导意义
的,一些稍微花费存储器的预处理可以节省相当多的计算。【因为寻址操作(特别指在若
干M的大范围区域内寻址)所占用的时间要远多于简单的运算指令,如果哪天寻址操作的速
度接近于基本运算了,那么这种技术将会对程序运行速度有很大的提升。】如果你仔细研
究你的程序,或许你会发现这方面是值得改进的。
 
为棋盘产生散列键值
 
  上面提到的换位表的结构,是由散列表来实现的,由此引发了以下课题:你如何快速
而有效地从棋盘来产生散列键值(Hash Key)?
  以下是1970年Zobrist的方案。
  1. 产生12x64个N位的随机数(如果换位表能储存2N个局面),并把他们做成一张表。
每个随机数只跟某个位置上的某种棋子有关(例如H4格的黑车),空的格子用零表示;【因
为棋子总共有12种,棋盘总共有64格,所以是12x64个数,空的格子不用随机数而用0表示
。】
  2. 先把散列键值设为零;
  3. 搜索整个棋盘,每遇到一个子,就在原来的散列键值上“异或”(XOR)它所对应的
随机数,重复这个过程直到整个棋盘被检查一遍。
  这个方案有趣的一面在于,每走一步,散列键值的更新都非常容易,不需要重新搜索
整个棋盘。你知道“XOR图形处理”(XOR-Graphics)吗?某个图形用XOR运算作用到背景上
,然后再作同样一次运算,不就又回到背景了吗?这里也同样这么做。【如果你熟悉图形
操作中的技术,就不难理解了,原文把这个过程比作“位图”(Bitmap)操作,12x64个棋
子的状态就对应12x64张位图,原先的散列键值被比作“背景”(Background),只要在背
景上作位图的粘贴操作(用的是XOR处理)就可以了。】举个H1格的白车吃掉了H4格的黑兵
的例子,要产生这个散列键值,先XOR“在H1格的白车”这个随机数(把这个图形擦掉),
然后是“在H4格的黑兵”(把这个图形也擦掉)和“在H4格的白车”(粘贴一个新的图形,
代表新的车的位置)【其实顺序是无关紧要的】。
  用相同的方法,不同的随机数,可以产生第二个散列键值,或称“散列锁”(Hash
Lock)【在英语中Lock(锁)和Key(钥匙)是对应的】,它是在换位表中存储的真正有用的信
息。这个技术是用来检测冲突的,如果恰巧有两个局面具有相同的散列键值,那么他们具
有同样的散列锁的几率是微乎其微的。
 
历史表
 
  “历史启发”(History Heuristic)是“杀手着法”(Killer Move)【以后的连载会提
到的,但为什么称“杀手着法”我也不清楚】技术的衍生技术。一篇研究性的文章是这么
解释的,历史表用来保存这些着法,在过去的搜中非常有意义(因为使用高效搜索技术的
而对它进行了很深的搜索),这个着法今后还可能用到。历史表由一个64x64的整数数组构
成【着法的起始格和到达格,共有64x64种组合】,记录每种着法的数值,当搜索算法认
为某个着法很有用时,它会让历史表增加这步的数值。表中的数值是用来对着法排序的,
“历史上占优势”的着法会优先考虑。
 
着法产生的预处理
 
  着法的产生(即决定特定位置下那些着法是合理的)和局面的估计一样,是象棋程序设
计中计算量最大的部分。因此,在这个方面的一点预处理会对提高速度大有帮助。
  我个人喜欢Jean Goulet在1984年写的《象棋的数据结构》(McGill大学出版社)一书
中提到的方案,它概括为:
 
  1. 出于着法产生的目的,棋子的颜色是无关紧要的,除了兵以外,它只朝对面走;
  2. 对于基本的子力和它的位置,有64x5=320种组合【指除了兵以外的5种棋子,根据
上一条,这些棋子是不分黑白的】,黑兵有48个格子可以放(他们后面一行是走不到的,
并且一到第八行就会变成别的棋子),白兵也有48个格子;
  3. 从某个格子沿某个方向,可以确定一条着法“射线”,例如,后从H3格朝北走,
这就是一条“射线”;
  4. 每个格子上的每个棋子,都有确定的几条射线可以走,例如位于中央的王可以朝8
个方向走,而位于盘角的象却只有一条逃生的路;
  5. 在开始游戏之前,要计算数据库里在所有格子的所有棋子的所有射线,假设棋盘
是空的(即着法只受到棋盘边缘的限制,不受其他棋子的限制);
  6. 当你为某个格子的某个棋子产生着法时,朝每个方向搜索直到碰到棋子为止。如
果是对方的棋子,最后一种着法就是吃子的着法,如果是本方的棋子,最后一种着法就是
不合理的。
 
  有了恰当的数据库,着法的产生就变成简单得接近于线性的寻找了,几乎用不着什么
计算。整个事情就掌握在这么几千个字节里,只是换位表的一个零头。
 
  以上提到的所有技术(位棋盘、换位表、历史表和预处理数据库)都会反映在我自己的
程序中,当我写完这个连载以后就会发布出来。下个月我会详细介绍着法产生的方法。
 
  Fran?ois Dominic Laramée,2000年6月
 
  出处:www.gamedev.net
  译者:黄晨 (auntyellow@citiz.net)
  类型:全译

上一篇 下一篇


--

※ 修改:·NDD 于 Nov 8 20:51:57 修改本文·[FROM: 202.112.174.3]
※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.120.224.*]

发信人: auntyellow (黄阿姨), 信区: AI
标 题: 国际象棋程序设计(三):着法的产生(转译)
发信站: BBS 水木清华站 (Tue Nov 9 21:31:57 2004), 站内

【 以下文字转载自 Chess 讨论区 】
发信人: auntyellow (黄阿姨), 信区: Chess
标 题: 国际象棋程序设计(三):着法的产生(转译)
发信站: BBS 水木清华站 (Tue Nov 9 21:30:14 2004), 站内

国际象棋程序设计(三):着法的产生
 
Fran?ois Dominic Laramée/文
 
  上个月,我完成了连载的第二部分,介绍了在着法产生的预处理中涉及的数据结构。现在我们把话题回到着法产生,详细介绍两种着法产生的策略,并解释一下在特定的情况下如何在这两个策略中作出选择。
 
困境
 
  不管你怎么对付象棋,它就是一个复杂的游戏,对于电脑来说就更是如此了。
  在通常局面下,棋手要在30多种着法中选择,有些是好的,有些则是自杀棋。对于受过训练的人来说,他能判断出大多数愚蠢和没有目的着法,甚至初学者都知道,后处于被吃的位置时该怎么逃跑。专家(多数是通过直觉而非推理)则知道哪几步棋会比较有力。
  但是,把这些信息(特别是无意识的那些)编写到计算机里去,被证明是极端困难的,连那些最强的象棋程序(除了个别程序以外,例如Hans Berliner的Hitech和它的姊妹程序)都已经放弃这条路线了,取而代之的是“蛮力”——如果你能以足够快的速度分析所有的着法,并且足够深远地预测他们的结果,无论你是否有一个清晰的思路,你最终会走出一步好棋。所以,着法的产生和搜索必须越快越好,以减小蛮力方法的花费。
  搜索技术将在连载的第四和第五部分介绍。这个月,我们会关注着法产生。历史上有以下三条主要的策略:
 
  1. 选择生成:检测棋盘,找到一部分可能的着法,把其他的全不要;
  2. 渐进生成:产生一些着法,希望沿着某个着法下去,可以证明这条路线好到(或坏到)足以中止搜索的程度(而不必再去找其他的着法)【译注:即后面要提到的“截断”】;
  3. 完全生成:产生所有的着法,希望换位表(在第二部分曾讨论过)会包含有关的信息,从而没有必要对这些着法进行搜索。
 
  选择生成(由之衍生出的搜索技术称为“朝前裁剪”(Forward Pruning),上世纪70年代中期以前,几乎所有的程序都这么做的,但是从那以后就突然消失了。另外两个方法代表了一枚硬币的两面——着法产生和搜索之间的权衡。对于那些着法产生简单并且有很多路线可以到达相同局面的游戏(或者具备其中一个特征),例如黑白棋(Othello)和五子棋(GoMoku),完全生成效率会更高些,而当着法产生的规则复杂的时候,渐进生成的速度会更快。不过两种策略都是很好的策略。
  【这里就黑白棋发挥几句。可能原作者认为,凡是只由黑白两子构成的游戏就一定具有这两个特征了,就像围棋和五子棋。但是我曾经做过黑白棋的程序,这个程序已经强到我自己无法赢它了。我发现两个特点,一是着法产生并不像想象中的那么容易,它有点类似于中国象棋中的炮的着法,二是殊途同归的局面比起国际象棋来说少得多,原因就在于走一步棋最多会改变18个格子的颜色,这与原作者的观点大相径庭。】
 
早期的策略:朝前裁剪
 
  在1949年(确实如此),Claude Shannon提出了两个象棋程序的算法:
 
  1. 着眼于对于所有的着法及其应对着法,循环下去;
  2. 只检查“最好”的着法,这个着法由对局面的分析来确定,然后也只选择“最好”的应对着法,循环下去。
 
  起初,第二种选择看上去成功的可能更大。毕竟人就是这么做的,从逻辑上说在每个结点上只考察某些着法,总比考虑所有的着法要快。不幸的是,这条理论被事实推翻了,用选择搜索的程序,棋下得并不怎么样。它们最好的也只能达到中等俱乐部棋手的水平,最坏的情况下还会犯低级错误。打败世界冠军(现实一点,水平发挥得稳定一些)是遥不可及的。
  在上世纪70年代中期,著名的美国西北大学Slate和Atkin的小组决定放弃复杂的“最佳着法”生成办法,后来证明,他们绕过复杂分析所省下来的时间,足以进行全面的搜索(检查所有的着法)。无论怎么说,这项改革善意地把“朝前裁剪”埋葬了。
  下面介绍一下鲍特维尼克的工作。
  上世纪70年代到80年代早期,在前世界冠军鲍特维尼克(Mikhail Botvinnik)的领导下,苏联发展了一个特别的朝前裁剪的例子。鲍特维尼克认为,计算机要达到大师级水平,唯一的途径就是像大师一样,即只考虑少量着法,但是要足够深远足够细致。他的程序试图判定世界级选手才能掌握的局面,还要实现很高水平的作战计划。尽管这个过程中诞生了一些吸引人的著作,揭示了只有鲍特维尼克本人才具备的大师级思路,但是这项工作最终没有达到预期的目标。
 
产生全部着法
 
  自从朝前裁剪被淘汰以后,最直接的实现完全搜索的方法是:

 
  1. 找到局面中所有合理的着法;
  2. 对他们进行排列,想要提高搜索速度就必须选择最佳的顺序;
  3. 对他们逐一进行搜索,直到全部搜索完成或者被截断【运用Alpha-Beta等搜索方法,可以在特定的情况提前中止搜索,以后的搜索就没有必要,这种情况就称为“截断”(Cut-off),连载的第四部分会介绍这类搜索方法】。
 
  早期的程序(例如Sargon)每次都扫描棋盘的每个格子,找有没有可以移动的棋子,然后计算可能的着法。当时存储器是稀有矿产,额外花费CPU的时间每次把着法重新计算一遍,是别无选择的蠢事。
  如今,预处理的数据结构(就像我上个月描述的那个)可以避免大量计算,而复杂的代码会多花费几十KB的空间。当这个超快的着法产生方法和换位表结合在一起的时候,程序员眼前又多了一条思路——如果某些着法已经被搜索过,它的价值(保存在换位表中)足以产生截断,那么根本就不需要搜索任何着法了。很明显,换位表越大,并且换位可能越多(它由游戏规则决定),换位表的作用就越明显。
  这个技术不仅在概念上简单,而且普遍适用于其他游戏(但着法却不是普遍适用的,象棋着法可以分为吃子和不吃子,其他游戏像黑白棋就不那么容易分类了)。因此,如果试图让你的程序不止能玩一种游戏,你应该尽可能地用这个技术来代替下面要介绍的一个技术。
 
一次只产生一步棋
 
  老牌的象棋程序(至少是CHESS 4.5以前的)则采取了相反的策略——一次产生少量着法,然后搜索,如果产生截断,就不需要产生剩下的着法了。
  这种方法的流行是因为下列因素结合在一起了:
 
  1. 搜索是不需要太大的存储器的。上世纪70年代以前的程序只能处理很小的换位表,也没有预处理的数据结构,这些都限制了完全搜索方案(就是上一节提到的方案)的运用。
  2. 在象棋着法产生的预处理比其他游戏复杂得多,有上王车易位、吃过路兵,不同的棋子要区别对待。
  3. 通常,这个方案的说服力(就是某步棋可以产生截断的例子)在于吃子。例如,某棋手送吃他的后,对手就会毫不犹豫地吃掉它,棋局也因此结束了。因为一个局面中能吃子的着法不多,而且产生吃子着法相对要容易一些,所以计算吃子的着法有很多产生截断的机会。
  4. 吃子是静态搜索(Quiescence Search,这个将在后面几部分提到)中需要检查的着法(不是唯一一类着法【可能除了吃子以外就是将军了】),所以单独产生吃子的着法是非常有效的。
 
  所以,很多程序都是先产生吃子的着法的,而且从吃最有价值的子开始,来找到最快的截断。有些技术是专门提高吃子着法的产生速度的,多数运用了位棋盘的技术:
  CHESS 4.5 用了两个组64个的位棋盘,棋盘上的每一格对应一个位棋盘。一组由 “这个格子上的子可以攻击的格子”的位棋盘组成,另一组正好相反,由“可以攻击这个格子的棋子所占的格子”的位棋盘组成。所以,如果程序去找吃黑后的着法,它先从基本位棋盘的数据库中找到黑后的位置,然后用这两组位棋盘来确定【其实只要用后一组就可以了】攻击后的棋子的位置,并且只产生这些子的着法。
  每走一步都需要维护这些位棋盘,这就需要引进很多技术,有一个称为“旋转的位棋盘”(Rotated Bitboard)的作用最显著。对于第一组位棋盘的产生办法,我见过的最好的论述是由James F. Swafford写的,这篇文章是在网上找到的,网址是:http://sr5.xoom.com/_XMCM/jswaff/chessprg/rotated.htm。
  【可以参阅我从Allan Liu那里整理的译文《对弈程序基本技术》专题之《数据结构(二) ——旋转的位棋盘》,现在Swafford教授的那个网站关了(这至少是5年以前的网站了),我正在考虑写eMail给他,向他索取原文。】
 
对着法排序以加快搜索速度
 
  我们下次要提到,搜索效率取决于搜索着法的顺序。着法排列的好坏直接影响到效率 好的排列方法可以产生很多的截断,大大减小搜索树的大小减小,其结点数只有用最坏的排列的搜索树的平方根那么多。
  不幸的是,可以证明,最好的顺序应该从最佳着法开始。当然,如果你知道哪个着法是最佳的,你还有必要做搜索吗?不过仍旧有一些“猜”的方法能确定可能比较好的着法。例如,你可以从吃子、兵的升变(它会大幅度改变子力平衡),或者是将军(它的应对着法很少)。紧接着是前面搜索过的在搜索树的同一层【肯定是在搜索树的不同分枝上】上产生截断的着法(即所谓的“杀手着法”),然后是剩下的。这就是迭代加深(Iterative Deeping)的Alpha-Beta搜索(下个月会详细讨论的)和历史表(上次讨论过了)的原理。要注意的是,这些技巧区别于朝前裁减 所有的着法最终是被检测的,那些坏的着法只是排在后边,而不排除在考虑范围以外。
  最后要注意的是,在象棋中,有些着法因为被将军而是非法的。但是这些状况毕竟是罕见情况,可以证明判断着法的合理性需要花费很多运算量。更有效的办法是所有的着法都搜索完了再来作检查,例如某步棋走完后有个吃王的应对着法,这时才来裁定这步棋为非法,搜索就此中止。很明显,如果搜索到这步棋以前,就产生截断了,那就不会对这步棋的合法性作出判断了【这部分的时间不就省下来了吗】。
 
我的选择
 
  在我的象棋程序里,我选择产生所有的着法,只是因为以下几个原因:
  1. 我想让这个程序作为其他游戏的基础,这些游戏没有像象棋一样的吃子着法;
  2. 我有足够的存储器来运行这个游戏;
  3. 这个技术需要的代码写起来比较容易,也比较看得懂;
  4. 已经有很多免费的程序,可以实现只产生吃子的着法,有兴趣的读者可以去看Crafty的源程序,还有James Swafford的Galahad。
 
  我的程序的整个表现似乎比别人的稍差了些,我的程序(是用Java写的,没有用别的)不想和深蓝去比,所以我感觉这并不算太坏。
 
下一个月
 
  现在我们准备探索象棋程序的核心部分——搜索技术了。这是一个很大的专题,需要两篇文章。我们从所有游戏最基本的搜索算法开始说起,然后才是最新发展起来的专门针对象棋的优化方法。
 
  Fran?ois Dominic Laramée,2000年7月
 
  出处:www.gamedev.net
  译者:黄晨 (auntyellow@citiz.net)
  类型:全译

上一篇 下一篇


--
http://cchessengine.512j.com (电脑象棋世界)
http://auntyellow.yculblog.com (万事通先生)


※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.120.224.*]

发信人: auntyellow (黄阿姨), 信区: AI
标 题: 国际象棋程序设计(四):基本搜索方法(转译)
发信站: BBS 水木清华站 (Tue Nov 9 21:32:01 2004), 站内

【 以下文字转载自 Chess 讨论区 】
发信人: auntyellow (黄阿姨), 信区: Chess
标 题: 国际象棋程序设计(四):基本搜索方法(转译)
发信站: BBS 水木清华站 (Tue Nov 9 21:30:50 2004), 站内

国际象棋程序设计(四):基本搜索方法
 
Fran?ois Dominic Laramée/文
 
  这个烦琐、没有代码、像胶水一样的连载,已经进入第四部分了,你们还在看下去吗?如果是的,就写eMail给我,我就可以找到写这些东西的理由了。
  无论如何,这个月的主题是策略类游戏的双向搜索(Two-Agent Search)【译注:意思是站在两个立场上的搜索,我也不知道该用什么比较确切的术语】,要了解它们有什么作用,如何来做,对电脑的程序意味着什么。我们要讨论的技术在所有的游戏中都很重要,但是仅仅靠它们是不足以下象棋的。下个月,我会介绍一些高级的技术,它们能显著增强棋力,同时提高搜索效率。
 
为什么要搜索?
 
  简单地说,因为我们还没有聪明到可以抛弃搜索的地步。

  一个真正聪明的程序可以只依靠棋盘局面来确定,哪一方处于领先以及领先多少,并且制定作战计划让这个优势变为胜果。不幸的是,需要考虑的局面类型太多了,再加上那么多的规则和特例,就是再聪明的程序也不擅长做此类事情。而它们擅长的则是计算。因此对象棋程序来说,与其只根据棋盘的局面来决定好的着法,不如使用它们的蛮力——考虑每一种着法,然后为对手考虑这些着法的所有应对着法,循环下去,直到处理器吃不消为止。
  比起掌握复杂的策略,深入的搜索是教电脑下棋的比较简单的方法。例如,考虑马的捉双问题,走一步棋就可以同时攻击两种棋子(例如一个车和一个后)。掌握这种类型的走法是需要花一些时间的,更复杂些,我们还要判断这个格子有没有保护。然而,一个愚钝的3步的搜索就可以学会捉双了,程序最终会尝试让马走到捉双的格子,并探索对手对于捉双的回应,然后吃掉没有逃跑的那个棋子,从而改变了子力平衡。由于全面搜索可以看到每一步,所以不会错过任何机会。如果经过5步棋后可以产生杀棋或捉死后(无论怎样不容易看到),只要电脑的搜索得足够深,就会看到这个着法。因此,搜索得越深,电脑就会施展越复杂的作战计划。
 
爷爷时代的“最小-最大”原理
 
  所有双向搜索算法的最基本的思想都是“最小-最大”(Minimax)原理。它可以追溯到中世纪(Dark Ages),但我相信它最早是由冯-诺依曼(Von Neumann)【应该是John von Nuoma,1903-1957,美籍匈牙利数学家】在60年前完整描述的:
 
  1. 假设有对局面评分的方法,来预测棋手甲(我们称为最大者)会赢,或者对手(最小者)会赢,或者是和棋。评分用数字表示,正数代表最大者领先,负数代表最小者领先,零代表谁也不占便宜;
  2. 最大者的任务是增加棋盘局面的评分(即尽量让评分最大)。
  3. 最小者的任务是减少棋盘局面的评分(即尽量让评分最小)。
  4. 假设谁也不会犯错误,即他们都走能让使局面对自己最有利的着法。
 
  那么这该怎么做呢?设想一个简单的游戏,每方只走一步,每步只有两种着法可供选择。评分函数只和最后棋盘的局面有关,即评分是最大者和最小者着法综合的结果。
最大者的着法 最小者的着法 评分
A C 12
A D -2
B C 5
B D 6

  最大者假设最小者会下出最好的棋,因此他知道,如果他选择着法A,那么他的对手会回应D,使最终评分变成-2(即获胜)。但是,如果最大者走的着法B,那么他就会获胜,因为最小者的最佳着法仍然是正数(5)。所以按照“最小-最大”算法,最大者会选择着法B,即使他选择A并且最小者走错时评分还会更高。
  “最小-最大”原理有个弱点,从简单的例子中还不能明显地看出来——要检查的各种路线的数量是指数形式的,这就意味者工作量会以几何级数增长。
 
  1. 每方有多少种可能的着法,这个数称为分枝因子(Branch Factor),用b表示;
  2. 考虑的深度用n表示,通常说“n层”,n是整数,“层”(Ply)表示一个棋手走的一步棋。例如在上面介绍的迷拟游戏中,搜索深度是2层。每个棋手走1步。
 
  例如在象棋中,通常在中局阶段分枝因子大约为35种着法,在黑白棋中大约为8。由于“最小-最大”算法的复杂度是O(bn),所以对一个局面搜索4层就需要检查150万条路线,这是多大的工作量!再增加上去,5层就会把搜索树膨胀到5000万,6层则达到18亿!【原作者这里写的是8层150万、9层5000万、10层18亿,不知为何多算了4层。】
  幸运的是,有办法能在精确度不打折扣的情况下大幅度削减工作量。
 
Alpha-Beta搜索——让“最小-最大”法成为现实(也只是有一点点现实)
 
  设想你在迷拟游戏中已经搜索了着法B,结果你知道最大者在整个游戏中最高得分是5。
  现在假设你开始搜索着法A了,并且一开始寻找的路线是A-D,这条线路的得分是-2。对于最大者来说,这是非常糟糕的,如果他走了A,那么结果肯定会是-2,因为最小者总是走得最好的。这是因为,如果A-C比A-D更好,那么最小者会选择A-D,如果A-C更坏(比如说-20),那么最小者就会选择这条路线。所以,没有必要再去看A-C以及其他由A产生的路线了——最大者必须走B,因为到此位置的搜索已经能证明,无论如何A是个更糟的选择。
  这就是Alpha-Beta算法的基本思想——只要你有一步好的着法,你就能淘汰其他可能导致灾难的变化,而这样的变化是很多的。如果再跟前面介绍的换位表结合起来,当不同路线的局面发生重复时可以节省下分析局面的时间,那么Alpha-Beta就能产生无限的能量——在最好的情况下,它处理的结点数是纯粹的“最小-最大”搜索的平方根的两倍,从1500万可以减少到2500。
  【又遇到可以发挥的地方了。普遍认为,Alpha-Beta搜索的结点数是死办法(即不用Alpha-Beta搜索的办法)的平方根那么多,我想办法证明了这个结论。对于n层分枝因子为b的搜索树,死办法搜索的结点个数是bn,这是显而易见的。那么Alpha-Beta搜索的结点数又是多少呢?我想到用两个递归函数来解决这个问题。
  Alpha-Beta搜索是完全搜索,如果某个结点是完全搜索的,那么这个结点称为Alpha结点,显然根结点是Alpha结点。那么Alpha结点的分枝又是什么呢?至少有一个Alpha结点,这是肯定的,最好的情况下,剩余的结点都可以产生截断,这些结点称为Beta结点。Beta结点有个特点,只要它的分枝中有一个Alpha结点产生作用,那么剩下的结点就没有搜索的必要了,我们还是取最好的情况,分枝中只有一个Alpha结点。
  现在我们来构造递归函数,设Alpha结点下需要搜索的结点数为Alpha(n),n为该结点的深度,那么这个函数的递归表达式是:
Alpha(n) = Alpha(n -1) + (b x 1) x Beta(n - 1)
  用同样的方法可以构造一个Beta(n)的函数:
Beta(n) = Alpha(n - 1)
  把它代入前面的Alpha(n)函数中(注意,n要替换成n - 1,n - 1要替换成n - 2),就可以得到下面的函数:
Alpha(n) = Alpha(n - 1) + (b - 1) x Alpha(n - 2)
  加上初始了条件Alpha(0) = Beta(0) = 1(即Alpha(0) = 1,Alpha(1) = b)后,这个方程是可以解出来的(利用一些递归函数的技巧,关键时刻来几杯咖啡就可以了)。但是这里用一个投机取巧的办法——再做一次n替换成n - 1的事情,这个公式就变成了:
Alpha(n) = b - Alpha(n - 2) + (b - 1) x Alpha(n - 3)
  这样就看出些名堂了吧,Alpha(n - 3)肯定和Alpha(n - 2)不在同一数量级,尽管放心把它舍去吧(投机取巧之所在),最后公式变成了:
Alpha(n) = b x Alpha(n - 2)
  这下总算豁然开朗了,相比起死办法的结点数:
Search(n) = b x Search(n - 1)
  其结果为bn,那么Alpha-Beta搜索的结点数不正是bn/2,即bn的平方根吗?原作者认为是2bn,可能把舍去Alpha(n - 3)这一项的因素也考虑进去了,他估计这会比预期要多一倍,一点也不过分。】
 
对着法排序来优化Alpha-Beta搜索
 
  可是,我们如何才能达到预期的效果呢?我们是否还需要做其他事情?
  的确是的。只要Alpha-Beta搜索可以找到比其他着法好的着法,它就能对搜索树作出非常有效的裁减,这就意味着,关键在于首先搜索好的着法。当我们在搜索其他着法以前先搜索到最好的着法,那么最好的情况就发生了。然而最坏的情况,搜索着法的顺序是按评分递增的,即每次搜索到的着法都比曾经搜索的着法要好,那么这种情况下的Alpha-Beta搜索就无法作出任何裁减,这种搜索将退化为极其浪费的“最小-最大”搜索。【这就是前一章的标题中写道“也只是有一点点现实”的原因。】
  对搜索进行排序是相当重要的。让着法随便排列肯定不行,我们必须找到更聪明的办法。不幸的是,如果有简单的办法知道最好的着法,那还有搜索的必要吗?因此我们必须用“猜最好的办法”来对付。
  有很多技术可以让着法的顺序排列成尽可能好的顺序:
 
  1. 用评估函数对着法打分,然后排序。直觉上这会起到作用,评估函数越好,这个方法就越有效。不幸的是在象棋中它一点也不起作用,因为下个月我们将了解到,很多局面是不能准确评估的。
  2. 找到在换位表中已经存在的局面,如果它的数值足够好,就会产生截断,这样就不必再进行其他搜索了。
  3. 尝试特定类型的着法。例如,后被吃掉肯定是最坏的想法,所以先检查吃子的着法是行之有效的。
  4. 把这个思路进行拓展,关注已经在同一层深度产生过截断的着法。“杀手启发”(Killer Heuristic)是建立在很多着法是次序无关的基础上的。如果你的后被攻击了,不管你把H2兵挺一格还是两格,对手都会吃掉你的后。因此,如果在搜索H2-H3着法时,“象吃掉后”的着法会产生截断,那么在搜索H2-H4着法时,“象吃掉后”很有可能也产生截断,当然应该首先考虑“象吃掉后”这一步。
  5. 再把杀手启发拓展到历史表上。如果在前面几回合的搜索中,发现G2-E4的着法很有效,那么很有可能现在仍然很有用(即便原来的格子是象而现在变成了后),因为棋盘其他位置的情况不太可能有多少变化。历史启发的的实现非常简单,只需要一个64x64的整数数组,它可以起到很可观的效果。
  现在已经谈了所有宝贵的思想,然而最有效的方法却稍稍有背于人的直觉,这个方法称为“迭代加深”(Iterative Deepening)。
 
迭代加深的Alpha-Beta搜索
 
  如果你正在搜索6层的局面,那么理想的着法顺序应该由同样层数搜索的结果来产生。既然这明显是不可能做到的,那么能否用稍浅的搜索(比如说5层)来代替呢?
  这就是迭代加深方法背后的思想——一开始搜索2层,用这样种搜索产生的着法顺序来搜索3层,反复如此,直到到达规定的深度。
  这个技术会受到一般人的质疑——大量的努力是重复的(8到10次乃至更多),不是吗?
  那么考虑一下搜索树的深度n和分枝因子b好了。搜索树在第1层的结点数为b,第2层是b2,第三层是b3,等等。如果b很大(记住中局时在35左右),那么绝大多数工作量取决于最后一层。重复搜索(n - 1)的深度其实是小事一桩,即便迭代加深一点也不起作用,它也只会多花4%的时间(在通常的局面上)。
  但是,它的优势是非常可观的——由浅一层搜索的结果排列得到的顺序,在层数加深时可以大幅度增加截断率。因此,迭代加深的Alpha-Beta搜索实际上找的结点数,会比直接的Alpha-Beta搜索的少很多。在使用换位表后,它的收效就更可观了——重复搜索浅的部分就几乎不需要时间了,因为这些结果在换位表里都有,没有必要重新计算了。
 
电脑下棋的风格
 
  迭代加深的Alpha-Beta搜索和换位表(并且在历史表的推动下)能让计算机对局面搜索到相当的深度,并且可以下国际象棋了。应该这么说,它的祖先“最小-最大”算法决定了那台电脑(曾经在世界上有惊人之举的那台电脑【即冯-诺依曼的ENIAC】)下棋的风格。
  例如,设想电脑能对一个局面搜索8层,通常在考虑某一步时,这种让人不解的模式会让让它战胜对手。只有少数一些看不清的、复杂的、迷惑人、超出直觉局面,才能让对手抓住一线机会取得胜利,而对于人类棋手(甚至大师)来说,这样的局面陷阱已经可以写到书里去了。
  然而,如果电脑找到了一个导致和棋的无聊着法,它就会绕过陷阱,因为它假设对手会作出正确的应对,无论那种可能性有多小,只要电脑认为平局是最高的期望。
  结果你可能会说,电脑下棋会极端谨慎,就像对手都是世界冠军一样。如果考虑到电脑算不到出人类棋手布置的陷阱那个深度,人类就会绞尽脑汁布设陷阱,让电脑犯错误。(人类棋手会研究对手的下棋风格,如果卡斯帕罗夫有机会和深蓝下一百盘棋,他可能会找到深蓝的弱点并且打败它。但是我们不知道有没有这种可能性。【现在看来,卡斯帕罗夫战胜深蓝是不在话下的,因为近几年他一直在和水平更高的电脑较量。】)
 
下一个月
 
  在第五部分,我们会讨论直接或改变深度的Alpha-Beta搜索的局限。我们还会讨论如何利用一些技术,诸如无意义着法启发 (Null-Move Heuristic)、静态搜索(Quiescence Search)、期望搜索(Aspiration Search)、MTD(f)搜索,以及让深蓝名声显赫的“单步拓展”(Singular Extensions)技术,它们会提高下棋水平。坚持住,我们快要结束了!
 
  Fran?ois Dominic Laramée,2000年8月
 
  出处:www.gamedev.net
  译者:黄晨 (auntyellow@citiz.net)
  类型:全译

上一篇 下一篇


--
http://cchessengine.512j.com (电脑象棋世界)
http://auntyellow.yculblog.com (万事通先生)


※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.120.224.*]

发信人: auntyellow (黄阿姨), 信区: AI
标 题: 国际象棋程序设计(五):高级搜索方法(转译)
发信站: BBS 水木清华站 (Wed Nov 10 23:58:24 2004), 站内

【 以下文字转载自 Chess 讨论区 】
发信人: auntyellow (黄阿姨), 信区: Chess
标 题: 国际象棋程序设计(五):高级搜索方法(转译)
发信站: BBS 水木清华站 (Wed Nov 10 23:57:22 2004), 站内

国际象棋程序设计(五):高级搜索方法
 
Fran?ois Dominic Laramée/文
 
  哇,看上去好像有很多人在看我的连载,我的脸都红了!
  这是倒数第二篇文章,我们会介绍和搜索有关的高级技术,他们既能提高速度,又能增强棋力(或者只有一个作用)。他们中有很多,概念上(程序代码可能不行)可以运用到任何2人游戏中,然而让它们用到一些具体问题上,对很多读者来说还需要加工。
 
干吗要那么麻烦?
 
  到此为止,我们知道的所有搜索算法,都把局面推演到固定的深度。但是这未必是件好事。例如,假设你的程序最多可以用迭代加深的Alpha-Beta算法搜索到5层,那么来看下这几个例子:
 
  1. 沿着某条路线,你发现在第3层有将死或逼和的局面。显然你不想再搜索下去了,因为游戏的最终目的达到了。搜索5层不仅是浪费时间,而且可能会让电脑自己把自己引入不合理的状态。
  2. 现在假设在5层你吃到了兵。程序可能会认为这个局面稍稍有利,并且会这么走下去。然而,如果你看得更深远些,可能会发现吃了兵以后你的后就处于被攻击的状态,完了!
  3. 最后,假设你的后被捉了,不管你怎么走,她会在第4层被对手吃掉,但是有一条路线可以让她坚持到第6层。如果你的搜索深度是5,那么后在第4层被吃掉的路线会被检测出来,这些情况会评估成灾难局面,但是唯一能使后在第6层(超出了搜索树)捉到的那条路线,对于电脑来说被吃是不能被发现的,因此它会认为后很安全,从而打一个较高的分数。现在,为了让后被吃的情况排除在搜索树以外,唯一的办法就是调虎离山,这样做是很冒险的——牺牲一些局面,还是有可能让对手犯下错误让你的后溜掉的。那么如果你要通过牺牲一个车来延缓后的被吃呢?对电脑来说,在第4层丢车要比丢后损失小,所以在这个搜索水平上,它情愿丢一个那么大的子,来推迟那个可怜的后的被吃了。(当然在随后一回合里,电脑会发现无论怎么走,它的后会在第4层被吃掉,并且车丢得莫名其妙。)很早以前Hans Berliner就把这个情况称为“水平线效应”,这在很大程度上可以通过后面即将介绍的“静态搜索”来改善。
 
  最后要说一句:象棋中的很多局面(其他游戏也一样)太不可预测了,实在很难恰当地评估。评价函数只能在“安静”的局面下起作用,即这些局面在不久的将来不可能发生很大的变化。这将是我们介绍下一个内容。
 
请安静!
 
  有两种评估局面的办法——动态评估(看局面会如何发展)和静态评估(看它像什么样子,不去管将来怎样)。动态评估需要深入的搜索。我们刚刚提到,局面在不久的将来不可能发生很大的变化的情况下,静态评估才是可行的。这些相对稳定的局面称为“安静”(Quiet)或“寂静”(Quiescent)的局面,它们需要通过“静态搜索”(Quiescence Search)来达到。
  静态搜索的最基本的概念是指:当程序搜索到固定深度时(比如6层),我们选择性地继续各条路线,只搜索“非静态”的着法,直到找到静态着法为止,这样才开始评估。
  找到静态局面是需要游戏知识的。例如,什么样的着法可能引起棋盘上子力平衡的巨大改变?对于象棋来说,子力平衡会导致局面的剧烈变化,所以任何改变子力的着法就是——吃(特别是吃主要棋子)、兵的升变都是,而将军也是值得一看的(仅仅是能导致将死的将军)。【译注:我认为任何将军都应该考虑进去,因为它会导致抽吃、长将等决定性局面的产生】。在西洋棋里,吃子和升变【西洋棋的棋子分兵棋(Man)和王棋(King),兵棋冲到底线就变成王棋,因此我断定它是国际象棋的前身】都是选择。在黑白棋中,每一步都必须吃子,并且“子力平衡”【仅仅指目前棋子的多少,它和最终棋子的多少没多大联系】在短时间内翻覆无常,所以可以说它根本不存在“静态局面”!
  我自己的程序用了简单的静态搜索,它只考虑所有带吃子着法的线路(在x层完全搜索以后)。由于通常局面下没有太多合理的吃子着法,所以静态搜索的分枝因子非常小(平均在4-6,双方在吃子后会迅速下降到0)。但是,静态搜索算法要分析大量的局面,它可能会占用整个处理器一半以上的时间。当你的程序使用这个方案以前,你要确定你是否需要用它。

  当没有吃子发生时,我的程序才开始评价局面。其结果就是将层数固定的搜索树作选择性的扩展,它能克服大多数由“水平线效应”产生的后果。
 
重要的空着
 
  有个加快象棋程序速度的有效方法,就是引入空着的概念。
  简而言之,空着就是自己不走而让对手连走两次。大多数局面中,什么事都不做显然不是办法,你总是必须做点事情来改善局面。(老实说,有一些“走也不是,不走也不是”的局面,空着确实是你的最佳选择,但不能走,但是这种 “被迫移动”(Zugzwang)局面是没有指望的,所以不必对电脑感到失望。)
  在搜索中让电脑走空着,可以提高速度和准确性。例如:
 
  1. 假设局面对你来说是压倒性优势,即便你什么都不走,对手也无法挽回。(用程序的术语来说,你不走棋也可以产生Beta截断。)假设这个局面本来准备搜索N层,而空着取代了整个搜索树(你的所有合理着法用空着取代了),并且你的分枝因子是B,那么搜索空着就相当于只搜索了一个N-1层的分枝,而不是B个这样的分枝。在中局阶段通常B=35,所以空着搜索只消耗了完整搜索所需的3%的资源。如果空着搜索表明你已经强大到没有必要再走棋(即会产生截断)的地步,那么你少花了97%的力气。如果没有,你就必须检查合理的着法,这只是多花了3%的力气。平均来说,收益是巨大的。【当然,空着搜索对于处理“被迫移动”局面还是有负面作用的,特别是在残局中,这个作用相当明显。可以参考《对弈程序基本技术》专题之《高级搜索方法——空着裁剪》一文。】
  2. 假设在静态搜索中,你面对一个只有车吃兵一种吃子着法的局面,然而接下来对手就会走马吃车。你最好不去吃子而走其他不吃子的着法对吗?你可以在静态搜索中插入空着来模拟这种情况,如果在某个局面下空着比其他吃子着法有利,那么你继续吃子就是坏的选择。并且由于最佳着法是静态着法,所以这个局面就是评估函数可以作用的局面。
 
  总的来说,空着启发会减少20%到75%的搜索时间。这当然值得,特别是当你把这个方法用在静态搜索算法上的时候,就像改变“走子的一方”这种代码一样简单,用不了十行就行了。
 
期望搜索和MTD(f)
 
  普通的老式Alpha-Beta搜索对某个局面最终的“最小-最大”值没有假设。看上去它考虑到任何情况,无论有多反常。但是,如果你有一个非常好的主意(例如由于你在做迭代加深,从而想到前一次的结果),你就会找出那些和你预期的差得远的路线,预先把它们截断。
  例如,假设一个局面的值接近于0,因为非常均衡。现在来假设对一个内部结点作先前的评价,它的值在+20,000【这里的单位应该是“千分兵值”, 即1000相当于一个兵的价值,那么马和象等于3000,车5000,后9000,其他因素也折算成这个值,而UCI协议中则用“百分兵值”,因为没有必要过于精确】,那么你可以有充分信心对它截断。
  这就是“期望搜索”(Aspiration Search)背后的思想,一个Alpha-Beta搜索的变种,开始时用从负无穷大到正无穷大来限定搜索范围,然后在期望值附近设置小的窗口。如果实际数值恰好落在窗口以内,那么你赢了,你会准确无误地找到路线,并且比其他的路线快(因为很多路线都被截断了)。如果没有,那么算法就失败了,但是这个错误是很容易被检测的(因为“最小-最大”值就是其中一条边界),你必须浪费一点时间,用一个更大的窗口重新搜索。如果前面的情况比后面的情况多,那么总体上你还是赢了。很明显,你预先猜的数值越好,这个技术的收效就越大。
  在上世纪90年代中期,研究员Aske Plaat把期望搜索拓展为一个逻辑问题:如果你把带期望的Alpha-Beta搜索的窗口大小设定成0,将会发生什么事?它当然永远不会成功。但是如果它成功了,那速度将是惊人的,因为它把几乎所有的路线全都截断了。现在,如果失败意味着实际数值低于你的估计,那么你用稍低点的宽度为零的窗口再试一次,重复下去。这样,你就等于用Alpha-Beta搜索来做某个“最小-最大”值的拆半查找(Binary Search),直到你最终找到那个宽度为零的窗口。
  这个伟大的设想发表在一个网站上:http://theory.lcs.mit.edu/~plaat/mtdf.html,它的具体实现称为MTD(f)搜索算法,只有十多行。加上Alpha-Beta搜索和换位表的运用,MTD(f)呈现出惊人的效率,还善于做并行计算。它在“粗糙”(简单且快速)的局面分析中运行得更好,很明显,如果局面评估的最小单位越大(例如从0.001个兵增加到0.1个兵),它搜索的步数就越少。
  在Alpha-Beta搜索的变种当中,还有很多具有广泛用途的算法(例如声名显赫的NegaScout,我宁可给白痴讲广义相对论,也不想给你们讲这些),但是Plaat坚持认为MTD(f)是至今为止效率最高的算法。我就信了他的话,所以我的程序里用了MTD(f),你们可能会感叹这个算法是多么简短啊!
 
单步拓展
 
  在我们结束这个主题以前,这是最后一个话题。在象棋中,有些着法明显比其他的好,这样就可能没必要搜索其他的变化了。
  例如,假设你在迭代加深过程中正在做深度为N-1的搜索,发现某步的评分为+9000(即你吃了对方的后),而其他都低于0。如果像比赛一样想节约时间,你会跳过前面的N层搜索而对这步进行N层搜索【对于这步来说,搜索加深了一层,对于优势局面来说,优势应该是越来越大的,所以加深一层后评分应通常要高】,如果这步额外搜索的评分不比预期的低,那么你可以假设这步棋会比其他着法都好,这样你就可以提前结束搜索了。(记住,如果平均每层有35种合理着法,那么你就可能节省97%的时间!)
  深蓝的小组发展了这个思想并提出了“单步拓展”(Singular Extension)的概念。如果在搜索中某步看上去比其他变化好很多,它就会加深这步搜索以确认里边没有陷阱。(实际过程远比这里说的要复杂,当然基本思想没变。)单步拓展是耗费时间的,对一个结点增加一层搜索会使搜索树的大小翻一番,评估局面的计算量同时也翻一番。换句话说,只有深蓝那种硬件水平才吃得消它,我那笨拙的Java代码肯定不行。但是它的成效是不可否认的,不是吗?【原作者的意思可能是指,单步拓展技术会明显提高棋力,同时也会增加搜索时间。】
 
下一个月
 
  在第六部分中,我们会着重讨论局面评估函数,它才真正告诉程序一个局面是好是坏。这个主题具有极其广泛的内容,可以花几年时间来改进评估方法(也确实有人这样做),因此我们必须对这些内容进行彻底讨论,包括它们的可行性和重要程度。【在这篇普及型的连载中,作者怎么可能给你们讲那么多呢?】如果任何事情都按照计划进行,我就该用一些Java代码来给你们填饱肚子,但是这很难办到,不是吗?
 
  Fran?ois Dominic Laramée,2000年9月
 
  出处:www.gamedev.net
  译者:黄晨 (auntyellow@citiz.net)
  类型:全译

上一篇 下一篇


--
http://cchessengine.512j.com (电脑象棋世界)
http://auntyellow.yculblog.com (万事通先生)


※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.120.189.*]

发信人: auntyellow (黄阿姨), 信区: AI
标 题: 国际象棋程序设计(六):局面评估函数(转译)
发信站: BBS 水木清华站 (Wed Nov 10 23:58:31 2004), 站内

【 以下文字转载自 Chess 讨论区 】
发信人: auntyellow (黄阿姨), 信区: Chess
标 题: 国际象棋程序设计(六):局面评估函数(转译)
发信站: BBS 水木清华站 (Wed Nov 10 23:58:16 2004), 站内

国际象棋程序设计(六):局面评估函数
 
Fran?ois Dominic Laramée/文
 
  已经六个月了,我知道你们有人觉得我不会闭嘴,但是你们错了,这是我的国际象棋程序设计连载的最后一篇。还有,我的Java象棋程序(看上去很烂)已经做好了,和这篇文章一起上传给了GameDev网站,这个程序还是可以验证这些连载内容的。
  这个月的话题——局面评估函数——确实很特别,搜索技术大同小异,着法产生可以只根据规则来处理,而局面的评估则需要很深入彻底的分析。可以想象,如果我们不知道某个局面会导致哪方获胜,那么评价这个局面的相对强弱将是不可能的。因此,很多要讨论概念对于其他游戏来说就不是这么回事了,有的则根本不能用。对于你自己的游戏,考虑用什么样的评估方法,这是你作为程序员应该知道的。【译注:对于中国象棋要特别注意,很多概念不能从国际象棋照般,我写过《中国象棋和国际象棋比较研究》一文,详细阐述过这个问题。】
  抓紧时间,让我们来看一些局面评价的尺度,并且需要了解它们有什么作用。
 
子力平衡
 
  简单地说,子力平衡(Material Balance)就是指双方各有哪些棋子。根据象棋文献,后的价值是900分,车500,象325,马300,兵100,王是无价的。计算子力平衡是非常简单的,每方的子力价值就是:
 
MB = Sum (Np x Vp)
 
  这里Np是棋盘上这种类型的子的数目,Vp是子的价值。如果你在棋盘上的子力价值比对手多,那么你的形势好。【说句提外话,外国人把“吃”说成“抓获”(Capture),意思是棋子并非消失了,而是暂时退出战场了,所以说子力价值时一定要强调“棋盘上”。】
  看上去非常简单是不是?但是这和象棋的局面评价还差很大距离呢。CHESS 4.5的作者估计了很多位置上的因素,例如机动性和安全性差不多接近1.5个兵。实际上,用不着考虑别的,这就足够可以下出好棋了。【注意,在把“兵值”这个概念运用到中国象棋的时候,最好也把车设成500,这时机动性和安全性的因素就可以参考国际象棋,也不超过150分。具体的子力价值可参考《中国象棋和国际象棋比较研究(二)——子力价值》一文。】
  的确,有些情况下为了通过子力交换让局面得到进展,你必须牺牲某些棋子(甚至是后)。然而最好是通过搜索来发现,例如弃后可以导致3步杀,你的搜索函数不需要额外的代码就会找到杀棋(前提是它看得足够深远)。如果你硬是要在评价函数里写特别的代码,来确定是否应该弃子,这种事情将是噩梦。
  很少有程序会用像我开始所说的那个评价函数。由于计算过于简单,人们会在上面增加点东西,都是这么做的。举一个众所周知的例子,当你子力上处于领先时,交换相等的子力是有利的。交换一个兵是不错的选择,因为它为你的车开放棋盘,但是你必须在棋盘上保存一些兵直到残局,以构筑防御屏障或者升变成后。最后,如果开局库里走出弃子的开局,你不用为程序担心,因此你要把“藐视因子”(Contempt Factor)加到子力平衡的评价中。例如当子力落后150分甚至更多时,你仍然让程序觉得是领先的。
  要注意,子力平衡在象棋和西洋棋里具有很高的地位,但是在黑白棋里却是欺骗性的。的确,棋局最后你必须控制更多的格子才能赢,但是你最好在中局阶段控制子的个数。在其他游戏像五子棋【Go-Moku确实应该是五子棋,我想不出还有什么不吃子的黑白棋类了】及其变种N子棋(Connect-N)【具体怎么下我也不知道】,子力平衡是不会变化的,因为始终没有被吃的子。
 
机动性和对棋盘的控制
 
  将死的特征之一是没有合理的着法。直觉上,好像选择余地越大约好,比如选手在30种着法内找出一步好棋,这种可能总要比限定在3步内高。
  在象棋中,机动性是很好评估的 计算同一局面下每方的合理着法,你已经能做到了【还要复习一下《着法的产生》吗?】。然而这个数字仅仅占一小部分。为什么呢?就因为很多着法是漫无目的的。例如你每次让车向后退一格,着法是合理的,但不产生作用。另外,不惜代价试图限制对手的机动性,会让程序进行一系列漫无目的的将军,同时摧毁自己的防线。由于解除将军通常只有3到4种合理着法,所以基于机动性的程序会走出劣着去将军对方,过会儿就会发现什么事也没干成,并且自己的兵力也成一盘散沙了。【我认为这种结果的根源在于没有把将军着法考虑进“静态搜索”中,如果考虑进去了,那么将军的时候不做局面评价,根本不存在对手机动性很低的假象。】
  但是,有些明智的机动性评估方法,会起点作用。我的程序就“坏象”给予罚分,即象的行动路线被一系列同色格的兵阻挡的情况,当马太靠近棋盘边缘时也同样处理。另一个例子是车,在开放或半开放线(即没有兵或只有一个兵的纵线)上价值更高。
  和机动性有密切联系的是棋盘的控制能力。在象棋中,如果一方对某个格子产生攻击的棋子数量超过对方,那么这一方就控制了这个格子。走到受控制的格子通常是安全的,走到被对方控制的格子则是危险的。(有一些例外,把后走到被敌方兵攻击的格子里,不管你有多少子可以吃他的兵,这无论如何不是好主意。还有,你故意把子送到对方嘴里,但是对方有更重要的格子需要保护。)在象棋中,控制中心是开局的基本目标。但是,控制能力在某种程度上是很难计算的,它需要在任何时候都更新数据库,来记录棋盘上所有被攻击的格子。很多程序都这么做,但我的没有。
  机动性对于象棋程序来说并不是非常重要的,但在黑白棋里却非常重要(在残局中有很少子可走的一方会陷入很深的困境)。而对围棋而言,对棋盘的控制则是胜利的标致。
 
局势发展
 
  有个教条,下象棋时轻子(象和马)要尽早投入战斗,王要尽早易位,车和后尽量少动,直到关键时刻作出决定性的攻击。这是有很多原因的,马和象(还有兵)能控制中心,来支持后的火力,把它们调动出去能为底线疏通车的路线。随着棋局的进行,车就可以跑到第七行(即开始对对方的兵动手),形成巨大的破坏力。
  我的程序用了一些因子来衡量局势的发展。首先,任何王和后前没有动过的兵都要扣分,阻挡车的马和象也要扣分,这样可以让后在其他子力出动后才开始动,如果对手还有后,那么王易位到安全位置时则给予很大的加分(有易位权但是没有易位的也给予少量加分)。
  你可以看到,局势发展的因素在开局阶段很重要,但是马上将失去意义。在大约10回合以后,要衡量的因素基本上都发生过了【即能加分的都加了,要扣分的都扣了】。
  注意,在西洋棋之类的游戏中,倾向于局势发展可能很不好。事实上,先走的一方要空出后面一行的空位,这就已经吃亏了,而在这些地方避免局势发展,通常是不错的选择。
 
兵形

 
  象棋大师门常说,兵是象棋的灵魂。因此新手很难体会的是,强手在对局时会因为一个兵的损失而早早认输。
  象棋书籍中提到很多兵的类型,有些是有利的,有些是有害的。我的程序考虑了以下几点。
  1. 叠兵或三叠兵,一方两个或多个兵在同一列上是很坏的,因为它们的移动相互阻碍了;
  2. 对兵,双方两个兵“头碰头”互相阻挡去路,会造成很大的障碍;
  3. 通路兵,当兵进展到不会有对方兵攻击或阻碍时【即同一列和相邻列里都不能有对方的兵】,就会变得非常强大,因为它们更容易到达底线实现升变;
  4. 孤兵,两边都没有同伴兵保护的兵,最容易受到攻击,最需要寻求保护;
  5. 满兵。棋盘上有太多的兵会影响机动性,为车开放一条纵线才是好主意。
  最后兵形上要注意的是:后面跟了车的通路兵是非常危险的,因为任何吃掉它的子都会成为车的盘中餐。如果有一个车在通路兵的后面(同一列),那么我的程序给予极高的加分。
 
王的安全和取向
 
  我们很早就谈到过王的安全了,在开局和中局里,保护王是最重要的,易位是最好的办法。
  但是在残局里,王身边的很多子都没了,他转眼间变成了攻击性子力!把它留在兵阵的后面简直是浪费资源。
  “取向”(Tropism)在这里衡量的是一个子攻击对方王的难易程度,通常用距离来衡量。取向的计算规则跟兵种有关,不过通用的规则是,你越靠近对方的王,你对他的压力就越大。
 
确定权重
 
  现在我们确定了有那些因素是需要衡量的,但是我们怎么决定它们的权重呢?
  这是个非常有价值的问题,可以花几年时间(也确实有人在做)用线性组合的办法来调整评估函数,有时把机动性设得多一些,有时更强调安全性,等等。我当然希望有一个绝对的答案,可惜没有,因为再好的评价函数都会碰到麻烦和失误。如果你的程序足够强,那很好。如果不是,那么试试别的方案,让它和你原来的程序下,如果能赢下大多数,那么新的方案就是一个进步。
  有三种方法可以试试:
  1. 通过优化评估函数取得的成绩,要达到加深一层搜索所达到的同样效果,这是非常困难的。如果你很疑惑,那么宁可把评估函数设得简单些,把更多的处理器资源留给Alpha-Beta搜索。【有关资料表明,加深一层搜索大约可以使棋力提高200分(ELO),这是相当可观的。】
  2. 除非你想和世界冠军去比,否则你的局面评价函数不必要特别有效。
  3. 如果你的程序确实很快,你可以花些时间用适当的算法来改进评估方法。但是对象棋来说,花上几千年时间都是有可能的。【这里指用适当的算法来调整权重,例如线性回归分析、神经网络算法等,每做一步调整,都需要用大量的对局来试验,所以工作量非常大。】
 
下一个月
 
  好了,没有下一个月了,就这些了。
  如果我要把这个连载拖得长一些,我可以写一些关于开局库(Opening Book)、残局库(Endgame Library)、特别针对象棋的硬件,以及很多很多其他的内容。我当然写得出来,但是我才不写呢。我打算把一部分内容保留到我今年秋天要写的书里,其他内容我也不知道到底有没有用。还有一个原因,我也懒得写下去了。
  我希望你们喜欢看我的东西,希望你们能学到两三个有用的技巧。如果真的学到了,那么明年看我写的别的东西吧(GDC或E3)【我也不知道是什么学科,GDC好像是图形显示控制芯片,反正和象棋没任何关系】,并且在你公司里的工程师或程序员面前好好夸我,好吗?
  太高兴了!
 
  Fran?ois Dominic Laramée,2000年10月
 
  【译后注:我猜F. D. Laramée可能是计算机方面的教授,总的来说他写的东西还是比较好浅显的,没有代码和过于专业的知识(即便是有,我也已经在译注中说明了)。但是或许是我英语水平的问题,他的某些表述并不能理解,因此即便很别扭地翻译出来了,还是要在译注中加上自己的理解,这让我非常吃力。不过总算一切都结束了。
  与此同时,我还收集了很多专题方面的文章,大概有三十来篇,本来是想翻译的,以展示我在程序设计方面的造诣,但是没有时间了(况且在Laramée的文章里我也发挥过瘾了)。我相信读者看了这六篇连载后一定觉得还不够,至少对于想设计象棋引擎的读者来说,仅仅看这么点东西是远远不够的,因此我把这些原文放在我的网站上,相信对于学过程序设计的读者来说,看这些文章应该是没有问题的。
  如果你读到有疑问的地方,不妨和我交流,或许你的疑问是很就价值的。如果你找到文中明显的错误(包括错别字),一定要写信给我,我的工作是无偿为象棋爱好者和程序设计师做的,所以也需要你们的帮助。】
 
  出处:www.gamedev.net
  译者:黄晨 (auntyellow@citiz.net)
  类型:全译

上一篇 下一篇


--
http://cchessengine.512j.com (电脑象棋世界)
http://auntyellow.yculblog.com (万事通先生)


※ 来源:·BBS 水木清华站 smth.org·[FROM: 202.120.189.*]

This page is powered by Blogger. Isn't yours?