4 有界深度优先搜索
(1)提出：解决深度优先搜索不完备的问题，避免搜索过程陷入无穷分支的死循环而提出有界深度优先搜索
(2)基本思想：对深度优先搜索引入搜索深度的界限（设为dm),当搜索深度达到了深度界限，而尚未出现目标节点时，就换一个分支进行搜索。
(3)搜索过程
<1>把初始节点S0放入OPEN表中，置S0的深度d(S0)=0；
<2>如果OPEN表为空，则问题无解，退出；
<3>把OPEN表中的第一个节点(记为n)取出放入CLOSE表；
<4>考察节点n是否为目标节点，若是求得问题的解，退出；
<5>如果节点n的深度d(节点n)=dm,则转第<2>步；
<6>若节点n不可扩展，则转第<2>步；
<7>扩展节点n，将其子节点放入OPEN表的首部，并为其配置指向父节点的指针，然后转第<2>步；
<1> OPEN:=S0,di:=d(S0)=0
<2> LOOP:IF OPEN=( ) THEN EXIT(FAIL)
<3> n:=FIRST(OPEN),REMOVE(n,OPEN),ADD(n,CLOSE)
<4> IF GOAL(n) THEN EXIT(SUCCESS)
<5> IF d=dm GOTO LOOP
<6> IF EXPAND(n)=( ) GOTO LOOP
<7> EXPAND(n)->M(mi),ADD(mi,OPEN),mi^->n,
GOTO LOOP
(4)关dm的讨论:
如果问题有解，且其路径长度<=dm,则搜索过程一定能求得解
dm太大时，搜索时将产生许多无用的子节点，即浪费了计算机的存储空间与时间，又降低了搜索效率。
dm的选择：先任意给定一个较小的数作为dm,进行有界深度的优先搜索，当深度达dm时仍未发现目标节点，且CLOSE表中仍有待扩展节点时，将这些节点送回OPEN表，同时增大深度界限dm,继续向下搜索。只要有解，一定可以找到。
为找最优解，可增设一个表（R),每找到一个目标节点Sg后，就把它放入到R的前面，并令dm等于该目标节点所对应的路径长度，然后继续搜索。由于最后求得的解的路径长度不会超过先求得的解的路径长度，所以最后求得的解一定是最优解。