下面看看有信息搜索和无信息搜索的PK
宽度优先特点:
深度优先特点:
vOPEN is a FIFO queue, i.e., new successors go at end
(把n的后继节点放入OPEN表的末端)
(把n的后继节点放入OPEN表的末端)
vComplete
vOptimal when cost actions positive and identical for all actions
vNumber of nodes visited (where
b is max. branching factor and d is depth of solution)
b is max. branching factor and d is depth of solution)
v对n应用一个算符以产生该节点的一个后继节点放入OPEN表的前端
vComplete for FINITE (implicit) NETS (LOOP-checking )
vdoes NOT find the shortest path
vMemory: 深度约束的线性函数
下面是一个重要的算法,整合了深度优先和宽度优先的优点(迭代加深算法)
迭代加深算法特点
1深度逐渐加深
2时间复杂度略大于宽度优先
3空间复杂度为深度(跟深度优先一样)
下面是有信息搜索
下面用 有信息搜索来解决8数码问题。
A*算法解决8数码难题
一下的几个是无解的:
A*算法在某种程度,又跟深度优先相似