首页 » 算法技术手册 » 算法技术手册全文在线阅读

《算法技术手册》假设

关灯直达底部

我们假设问题的局面状态都可以高效地表示,并且在博弈树或者搜索树的节点上,只有有限多个可行走法。搜索空间事实上可能是一个图,而不是一棵树,因为到达同一个状态可能有多种走法。即便这样,我们也在一个类似于树而不是图的结构上使用寻路算法,并且评价线性的走法序列。

我们假设存在这样一个问题,我们叫它Tiny-Puzzle,作为深度优先搜索,广度优先搜索以及A*搜索的伪代码所描述的例子。在Tiny-Puzzle中,一个棋面状态包含两个非负数,s0和s1。每一个棋面状态存在两种可行走法——(1)增加s0,以及(2)增加s1,所以这个游戏的分支因子是2。例如,给定初始状态<s0=0,s1=0>,目标状态<s0=1,s1=2>能够在3步内达到:增加s1,增加s0,然后增加s1。