数学问题与模式探求第28题 围棋决赛

第28题 围棋决赛 　　设A、B两人进行三战二胜制围棋决赛。问比赛共有多少种可能的进程？如果进行五战三胜制决赛，比赛又有多少种可能的进程？ 　　分析：可以用树形图来帮助计数。 　　图中第一条路线A—A—→A表示第一盘和第二盘都是A胜，A已胜二局，比赛结果A为胜者，第二条路线A—B—A—→A表示第一盘A胜，第二盘B胜，第三盘A胜，比赛结果A为胜者(如果第三盘B胜，则得到第三条路线，结果B为胜者)。 　　用此种树形图可以帮助我们毫无遗漏地把各种可能的进程都画出来，便于最后计数。 　　解：三战二胜制共有6种可能的进程。 　　五战三胜制共有20种可能的进程。 　　将上面第一盘为A取胜的树形图中的“A”换成“B”，“B”换成“A”，就可以对称地得到第一盘为B取胜的各种可能进程的树形图。两者均有10种可能的进程，因此，合起来共有20种可能的进程。 　　回顾：对于某些问题，为了解决它们，必须在许多可能状态中进行搜索。对于这些可能状态，我们也可以用树形图来表示，从而便于搜索。下面举一个投资问题来说明树形图的另一种应用。 　　某公司有10百万元资金和14万平方米土地准备投资搞项目，可供选择的项目有A、B、C三项，它们所需的资金、土地以及每年的收益如下表所示： 　　问搞哪几个项目可使年收益最高？ 　　如果用x1，x2，x3等于1或0分别表示项目A、B、C搞或不搞，那么上述问题就归结为求x1，x2和x3的值，它们满足下列条件： x1，x2，x3=0或1 (3) 　　并使 4x1＋3x2＋3x3 (4) 　　取得最大值(其中(1)和(2)分别表示所投资的项目所需的资金和土地不超过公司所拥有的资金的土地，(4)式表示所投资项目的年收益)。 　　我们用树形图(图28-1)来表示(x1，x2，x3)可取的23=8种状态。 　　图28-1中最右端的两个分支分别表示x1=1，x2=1，x3 =0和x1=1，x2=1，x3=1(图28-2)。此时7x1+5x2=7+ 5＞10，所以此两组解不满足条件 7x1+5x2＋2x3≤10 　　应予放弃。 　 　　接着，搜索图28-3实线所示的分支，此时x1=1，x2=0，x3=1，将它们分别代入(1)和(2)式，条件都满足，因此是一个可行解(即满足投资条件(1)和(2)式的解)。 　　由于图28-3实线所示的分支是一个可行解，它左边的虚线所示的分支的x1，x2的值相同，只是x3的值改为0，显然也满足条件(1)和(2)式，因此，x1=1，x2=0，x3=0也是一个可行解。但是，将图28-3所示的两组解代入(4)式，显然，右边分支所示的解的年收益高，因此，可以将左边分支舍弃。 　　同样，对图28-4实线所示的分支，加以计算，可知x1 =0，x2=1，x3=1是可行解，于是，将它左边虚线所示的3个分支也因年收益较低而予以舍弃。 　　比较图28-3和图28-4实线分支所示的解的年收益，前者为4＋3=7，后者为3＋3=6，因此，应选择前者，也就是说，投资项目A和C，年收益最大，每年收益7百万元。 　　注：树形图是图论中“树”的概念的直观化。在组合数学中有许多问题可以用树作为数学模型，把各种状态的搜索过程形象地表示出来，特别在状态总数很大时更具优越性。 　　投资问题就是寻找满足形如(1)和(2)式的约束条件的可行解中使形如(4)式的目标函数取得最大值(或最小值)的最优解的问题。由于变量x1，x2，x3只取0、1两种值，我们把这类问题叫做0—1规划。如果变量可取非负整数，那么这类问题称为整数规划。 　　在解投资问题的过程中，我们对图28-1所示的树，从顶向下，自右向左进行搜索。对于图28-2所示的分支，从x1=1搜索到x2=1就发现不满足约束条件(1)就予以放弃了。对于图28-3所示的分支，虽然都是可行解，但是，我们发现，右边的解总是优于左边的解，因此，也把左支“剪”去了。对于图28-4所示的4个分支，同样，由于最右端的分支是可行解，我们把左边的各支都“剪”去了。如何在搜索过程中找到良好的判别条件，使得剪去的分支尽可能的多，这就是计算机算法所研究的问题。 　　由以上讨论，我们可以看到，在解决投资问题时，要联系到图论、0—1规划和计算机算法三方面的知识。一般地，我们所说的数学联系，就是指概念与概念、概念与、方法与方法、数学的这一分支与那一分支、数学与其他学科、数学与实践等等之间的相互联系。对提高数学素质而言，了解和掌握这些联系是十分重要的。有了这种了解和掌握，在解决问题时，就能从多角度、多方面来考察，问题解决的手法就会更加灵活多样。特别地数学上许多惊人的突破性工作，往往出自于人们找到了意想不到的数学联系。因此，在学习数学时，必须把数学看作一个统一的整体，逐步建立数学知识之间相互联系的网络结构，以至能在同一实际问题或同一数学概念的不同表示之间进行转化和灵活应用，从而提高自己的数学思想境界和解决问题的能力。 练习28 　　1．设A、B两人进行七战五胜制围棋决赛。问比赛共有多少种可能的进程？ 　　2．某运输公司为一家工厂运输3个分别装有机器A、B、C的大箱子。公司为了获利最大，尽可能地用飞机装运，而把余下的箱子再用卡车装运。飞机有8单位的容积，载重量为10单位，而A、B、C箱子的体积分别为2单位、6单位、3单位，重量分别为5单位、4单位、4单位，运输的收益分别为3单位、5单位、4单位。问飞机在飞行时如何运载，收益最大？ PAGE 1