E（x）=v* g（x）+ w* h（x）
其中，v、w为权系数，g (x)为已付出的价值，h（x）为将要付出的价值。
当w↗、v↘表明强调“启发性信息”的作用和“纵向深入”的搜索。 当w↘、v↗表明强调“历史信息”的作用和“横向扫描”的搜索。 在E（x）中，g（x）的系数v增大，搜索过程倾向于广广度优先搜索，强调了横向扫描，有利于搜索过程的完备性，但抑制了纵向深度前进的速度，降低了搜索过程的启发性，不利于提高搜索效率。
对广度优先搜索法：
相当于w=0，h（x）=0，v=1
E（x）=g（x）=d（x）
无启发性信息 对深度优先搜索法：
相当于v=0，g（x）=0，w=1
E（x）=h（x）=N（x）
三
当知识表达方式采用“与或”树图时，知识推理也要采用“与或”树图搜索法。
对于采用“与或”树图表达式的知识的问题求解过程，也就是寻求“解树”的过程，将初始问题，通过有关的分解和变换转换成为某个或某些本原问题，从而可以求得初始问题的解。 1.“与或”树代价驱动搜索法
采用“代价最小，优先扩展”的控制策略，寻求最小代价的解树。
A） 与结点代价计算
a）最大代价： h（x）=max[c（x，xi）+h（xi）]
c（x，xi）——从x到xi的实际代价； h（xi）——对结点xi的估计代价。
b）代价和： h（x）=? B）或结点的代价计算
h（x）=min[c（x，xi）+h（xi）]
c(x,xi)?h(xi)
C) 端结点代价定义： h（x）=0 （可解结点） h（x）=∞ （不解结点）
根据代价计算结果，对结点进行排序，按照“代价最小，优先扩展”的原则，逐步扩展搜索树，求解树，并进行总代价计算，从而通过比较求得代价最小的最优解树。
2.“与/或”树最好优先搜索法
Nillson 算法，1971年提出。引入了启发信息，帮助估计结点x的代价h（x），故称为启发函数。根据估计代价，可以估计最优解树（最小代价树）的近根部分——希望解树。
利用希望解树，可以沿有希望的方向进行搜索，对子结点进行扩展，有助于提高搜索效率，通过部分状态空间求得最优解树。 希望树定义:
① So在希望解树中；
② 或结点在希望解树中，则有最小代价 h（x）=min[c（x，xi）+h（xi）] ③ 与结点在希望解树中，最大代价 h（x）=max[c（x，xi）+h（xi）]
四.博弈问题求解
博弈（Game playing）是一种对策性游戏，是一类竞争性的智能活动。此处仅讨论简单的情况——二人、零和、非偶然性、全信息的博弈活动。 二 人——二人对抗
零 和——即双方利益完全对立，你胜我负，我胜你负
非偶然性——博弈双方完全根据自己的得失，选择每一步，决不“碰运气” 全 信 息——格局的当前和过去历史双方是具知的 其输赢函数: φ1+ φ2=0 平局时： φ1=φ2
博弈树是采用“与/或”树进行知识表达的一种特殊的“与/或”搜索树。博弈过程是由双方轮流实施其控制对策的过程，有敌我双轮流进行扩展的，新生成的子结点是双方交替出现的，即由“与结点”和“或结点”交替出现的。“与/或”树u，其中与结点为敌方结点，因敌方必然选取最不利于我方的一着，扩展
其子结点，只要有一着不利，该结点就对我方不利。而“或结点”是属于我方结点，因为扩展我方结点的主动权在我方手中，可以选取最有利于我方的一步，只要可走的走步中有一步对我方有利该结点就是有利的。另外，所有使我方获胜的终局，都是本原问题，相应的端结点是“可解结点”，所有使敌方获胜的终局对我方是“不可解结点”。且先走一方的初始状态相应于根结点So。
在博弈中经常采用的是保险策略，即每方都是立足于在最坏的情况下去争取最好的结局，对i方来说（i=1,2……），它按照 max[minφi (d1,d2)] d1∈D1,d2∈D2
初始棋局
第一棋手着棋 初始棋局 第二棋手着棋
初始棋局 博弈树可形象化表达如下：
对第一个选手而言，可下的棋着为或结点（可凭他任意选择），当然他应选择最优奇招。而第二个棋手的棋着对第一个棋手而言是与结点，即第一个棋手要考虑第二个棋手的所有走棋状态。
博弈问题求解通常采用极大极小搜索法和α-β剪枝技术两种方法：
1. 极大极小搜索法：（Max、Min）
极大极小搜索法和最小代价的与/或树搜索法相似。其博弈过程是极大极小值搜索过程，此过程生成的树称为博弈树。采用“与小或大”原则，所谓“与小”即取最少走步；所谓“或大”即争取最大得分。博弈树的生成特征有： ①凡是对MAX有利的棋局取较大的启发式函数的估计值；对MIN有利的棋局去较小的启发式函数的值。这种估值称为静态估值。
②我们称由某结点的估值推算出父结点的估值为倒退值。为了采取保险策略——立足于最坏情况，争取最大得分（对己方MAX而言），所以，对或结点来说应取各支路中的一个最小的估值。因此，与结点也称MIN结点。在博弈树中，静态估计和倒退值又称结点的得分。
2 2 -1 2 B 6 0 -1 -1 2 A -1 -1 6 -1 0 -5 -2 -1 -7 -1 2 9 5 1 -1 -1 3 6 8 -1 2 0 3 -5 7 4 -2 6 -1 8 7 -1 4 3 倒退值的算法：
如图，A是与结点，取其三个子结点的静态估值2、9、5中最小一个值作为倒退值，估A的估值为2；B是或结点，取其子结点中最大的一个估值作为倒退值，所以B的估值为2，其它结点依此类推。
博弈树问题每一个棋局的违法可能很多，博弈树上每一个结点的分支数可能很大，因此会生成一颗很大的博弈树。试图利用完整的博弈树来进行MIN、MAX分析，实际上是不可能的。可行的办法是，以一定深度生成博弈树，而后应用静态估值函数推算出各端点的静态估值，再按极大极小原则选取倒退值为内点的估值，从而选择当前的最佳走棋。
例：图示九个空格，由MAX和MIN对弈，轮到谁走棋，就往空格上放上自己的一只棋子，谁先使自己的棋子组成三子成一线，谁就能胜利。
设MAX——x，MIN——o
设搜索深度为2，即每一次扩展二级，其静态估值函数定义如下： 设棋局为P时，静态估值函数：
若P是MAX必胜的棋局：e（p）=+∞ e（p）= 若P是MIN必胜的棋局：e（p）=-∞
若P是胜负未定棋局，e（p）=e（+p）-e（-p） 其中，e（+p）表示棋局P所有空格都放上x之后，“x”成三子一线的数目。 e（-p）表示棋局P所有空格都放上o之后，“o”成三子一线的数目。 如图所示，MAX开义的最优一着为G，如果MIN是精通博弈者，那么MIN应走出这一着，因为这一着的估价小，对MAX不利，若他不精通博弈，他选了I这一着，下面又轮到MAX走棋，MAX又采用极大极小分析法产生深度为2的博弈过程（即第二着棋）。
x
欠一个图
2. α-β剪枝法：
在上述极大极小分析法中，将生成部分博弈树和计算估价函数分开进行，这样作效率较低。如果能边生成结点，便计算估价，并根据情况随时删除不需要的结点，就可以减少许多计算和搜索工作量，这可使用α-β剪枝技术。
例：如图所示，为一颗博弈树。先对其端点进行静态 估值，设先估值e(C)=2,e(D)=7,e(E)=1,而尚未对e(F)估 值，若此时就计算倒退值，则倒退值为：