[2017年整理]第二章 与或图有哪些信誉好的足球投注网站问题.pptVIP

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * 极大极小分析法：一子棋 一子棋游戏：估价函数定义如下 设棋局为P，估价函数为e(P)： 1. 若P是A必胜的棋局，则e(P)＝＋?； 2. 若P是B必胜的棋局，则e(P)＝－?； 3. 若P是胜负未定的棋局，则e(P)=e(+P)-e(-P)。其中， e(+P)表示在棋局P上添上所有的a后直线的数目， e(-P)表示在棋局P上添上所有的b后直线的数目。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 极大极小分析法：一子棋 A的第一着棋生成的博弈树。每一着棋都要导致博弈树深度加2：一层是自己，一层是对方。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * ?-?剪枝 上述的极小极大分析法，实际是先生成一棵博弈树，然后再计算其倒推值，致使极小极大分析法效率较低。于是在极小极大分析法的基础上提出了α-β剪枝技术。 α-β剪枝技术的基本思想或算法是，边生成博弈树边计算评估各节点的倒推值，并且根据评估出的倒推值范围，及时停止扩展那些已无必要再扩展的子节点，即相当于剪去了博弈树上的一些分枝，从而节约了机器开销，提高了有哪些信誉好的足球投注网站效率。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * ?-?剪枝 S0 A B E D C H G F N M L P Q X X I S R X J T X K U X X X 2 8 4 1 -2 5 9 1 -5 2 ?1 ?-2 ?2 5 ?2 ?5 ?1 ?-5 ?1 ?1 ?2 “与”节点G的?值不能升高其父节点C的?值，则对节点G以下的分枝可停止有哪些信誉好的足球投注网站，并使G的倒推值为?。这种剪枝称为?剪枝 “或”节点D的?值不能降低其父节点A的?值，则对节点D以下的分枝可停止有哪些信誉好的足球投注网站，并使D的倒推值为?。这种剪枝称为?剪枝。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * (1) 对于一个与节点MIN，若能估计出其倒推值的上确界β，并且这个β值不大于 MIN的父节点(一定是或节点)的估计倒推值的下确界α，即α≥β，则就不必再扩展该 MIN节点的其余子节点了(因为这些节点的估值对MIN父节点的倒推值已无任何影响 了)。这一过程称为α剪枝。(2) 对于一个或节点MAX，若能估计出其倒推值的下确界α，并且这个α值不小于 MAX的父节点(一定是与节点)的估计倒推值的上确界β，即α≥β，则就不必再扩展该MAX节点的其余子节点了(因为这些节点的估值对MAX父节点的倒推值已无任何影响 了)。这一过程称为β剪枝。 Evaluation only. Created with Aspose.Slides for .NET 3.5 Client Profile 5.2.0.0. Copyright 2004-2011 Aspose Pty Ltd. * 从算法中看到：　(1) MAX节点(包括起始节点)的α值永不减少；　(2) MIN节点(包括起始节点)的β值永不增加。在有哪些信誉好的足球投注网站期间，α和β值的计算如下：　(1) 一个MAX节点的α值等于其后继节点当前最大的最终倒推值。　(2) 一个MIN节点的β值等于其后继节点当前最小的最终倒推值。 Evaluation only. Created with Aspose