二、数学模型的建立和比较
. Z# [+ D1 p$ k由于考虑问题的角度不同，面对同一个实际问题，可能建立起各种各样的数学模型。在各种数学模型中，我们要寻找的是效率高的模型。模型的效率同模型的抽象化程度有关，下面从一个实例中来分析它们之间的具体关系。
+ G1 n& v' G: p2 t" c$ F, c; E% Y【多边形分割问题】将一个凸n边形用n-3条互不相交的对角线分割为n-2个三角形,求分割方案的总数.
这道题可用以下几种方法来求解:
<1>.搜索法:
显然，一组n-3条互不相交的对角线对应于一种分割方案，因此可把问题看作是求不同的对角线组的数目。
$ v6 z' Z& ?% v* X/ Z' }5 |将n边形的n个顶点按顺时针方向编号为1、2、3……n，则一条对角线可表示为一个数对(a1,a2)，a1、a2分别表示对角线两端顶点的序号，a1<a2，a1为对角线的始端，a2为末端。
$ m6 F3 s G/ o, T* P3 I. m对角线在对角线组中的顺序是无关紧要的，因此，一个对角线组是一个集合，它的元素是对角线。
判断两条对角线是否相交是一个必须解决的问题。设两条对角线分别为(a1,a2)与(b1,b2)，若把表示对角线的数对看作开区间，那么两条对角线不相交的充要条件是两个区间有包含关系或他们的交集为空集。
于是，我们建立起解决本问题的第一个数学模型：
3 ?* c; Z( q. D( R+ i$ B已知：n的值,
/ C* ?2 k- G6 K) {+ q9 `/ G' w# H一个集合由(n-3)个不同的开区间(i,j)组成,
i∈{1..n-2}, j∈{i+2..n},(i≠1)或(j≠n)
同一个集合中任两个不同的开区间(i1,j1),(i2,j2)满足：
- d( U2 Y0 ^! | f7 c! y7 r((i1,j1)∩(i2,j2)=空集)或((i1,j1)包含(i2,j2))或((i2,j2)包含(i1,j1))
- M+ D4 X5 b& `3 h* {0 N求：不同的集合的个数
搜索时，先考虑以顶点1为始端的对角线，可以不连任何对角线(图一中A)，也可以连(1,3)(图一中B)，或连(1,4)(图一中C)，或同时连(1,3)(1,4) (图一中D)。对于每一种情况，再考虑以顶点2为始端的对角线，依此类推。当得到n-3条互不相交的对角线时，便找到了一种方案
5 ~; x; P; Y) F7 ^( ?2 K* K4 T在考虑以顶点i为始端的对角线时，有以下几条规则必须遵循：
$ J+ t( _* E, L U1.与原有对角线相交的对角线不得选取。
2.当i>=3时，若顶点i-1为始端的对角线一条都未连，则对角线(i-2,i)必须是已经连的。
8 T9 I: b0 L4 ~: c/ c3.对角线的末端顶点序号必须大于i。否则，顶点i将成为对角线的末端，另一个顶点j(j<i)成为对角线的始端，这条对角线已在考虑以顶点j为始端的对角线时考虑过了，再考虑将引起重复。
* m, _5 ?( P% Y/ |按照以上三条规则，即可得到如图一的搜索树(图中打√的叶结点为不同的分割方案)。
) x: F3 u+ t% {/ y- |% l# o6 A搜索法的数学模型较为复杂，用它可以求出具体方案，但它的抽象化程度不高，导致了求解时的低效率。为了使用上面的规则2来提高效率，求解过程还是从多边形及其对角线本身来考虑的，数学模型的作用仅体现在判断对角线是否相交上。用该方法编制的程序在n稍大时速度就很慢。(n=12时已需运行时间16.2秒(486DX2/80)，测试结果见附表一。)
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) | Powered by Discuz! X2.5 |