与或树

来自计算思维百科
跳转至: 导航搜索
与或树1.png

当我们将大问题分解成小问题时,需要使用与或树表示大问题与小问题、小问题与小问题之间的关系。

基本概念

对于一个复杂问题,可以使用与或树对问题分解或者等价变换。分解就是把一个复杂问题分解为若干个较为简单的子问题,每个子问题又可能续分解为若干个更为简单的子问题,重复此过程,直到不需要再分解或者不能再分解为止。然后对每个子问题分别进行求解,最后把各子问题的解复合起来就得到了原问题的解。

问题的分解过程可用一个树表示出来。例如,问题P可分解为P1、P2、P3,三个子问题只有同时解出来P才可解答。这时候称P1、P2、P3存在“与”关系,用一条弧把各条边连接起来。节点P、P1、P2、P3所构成的树为“与树”。

与或树2.png

问题的等价变换过程,也可用树来表示。例如,问题P被等价变换为问题P1、P2、P3,其中新问题P1、P2、P3中只要有一个可解,问题P就可解。称P1、P2、P3存在或关系,节点P、P1、P2、P3所构成的树为“或树”。

与或树3.png

上述两种方法结合起来使用构成的树,称为“与或树”。

与或树4.png

与或树中,如果子问题是或关系,则只需要解决其中一步就可以解决上一步大问题。

应用范围

与或树可以用于问题的化简和转换,从而提高问题的解决效率。如旅行时的路线选择问题,活动项目的选择问题等等

使用方法及步骤

1 将大问题分解为若干个子问题;

2 将子问题分解为更小的子问题;

3 重复第2步直到问题不能再分解;

4 解决最小的问题然后再一步一步往回解决大问题。

应用案例

应用1- 三阶梵塔问题

案例:.三阶梵塔问题,即有A、B、C 3个金片即3根钢针,3个金片按自上而下从小到大的顺序在1号钢针上,要求把它们全部移到3号钢针上,而且每次只能移动一个金片,任何时候都不能把大的金片压在小的金片上面。

 

解决步骤:

1)想要把3个金片全部移到3号针上,必须先把金片C移到3号针上。

2)为了移动金片C,必须先把金片A和B移到2号针上。

3)把金片C移到3号针上后就可以把A、B从2号针移到3号针,这样就可以完成问题求解。

由此得到问题的三个子问题,其中问题1和3又分别可以分为3个子问题。

用与或树把问题的分解过程表示出来,如下:

与或树5.png

 

与或树6.png

应用2-A市申请小学学位的流程表示

A市某年规定符合如下条件的适龄儿童可以申请小学学位。

必须具备的基本条件为:

P1:年满六周岁

P2:在B区合法居住

P3:有学习能力

以上三个基本条件一起设为P0

只需要符合其中一个条件的为:

P4:A市户籍儿童

P5:享受相关政策优惠人员的子女

P6:符合市政府“1+5”文件规定,父母在B区连续居住一年以上,且能提供相关真实、准确信息材料的非户籍人员子女

具备小学学位申请资格的人用P表示,用与或树来表示这个规定就是:

与或树7.png

从上图看出,P0、 P4、P5、P6是或关系,只要满足其中的任何一个就可以达到条件P,即可以申请小学学位。P1、P2、P3条件之间是与关系,也即要达到P0条件,就必须同时满足P1、P2、P3。

可以体现的计算思维

与或树将问题的分解和等价变换过程用“树”的形式表现出来,使得问题的条件更加清晰,求解思路也容易找到,体现了抽象的计算思维。