第1章搜索问题

第1章搜索问题内容摘要：

t, if the subgraph does not contain the goal node, we continue to expand it, until the subgraph is large enough to include the goal node , and we find the solution path from the initial node to the goal node. The procedure GRAPHSEARCH input : the production system(the initial nose, production rule, goal node) output: the solution path from the initial node to a goal node 人工智能 吉林大学珠海学院计算机科学与技术系 Procedure GRAPHSEARCH 1 G=s, OPEN=(s)。 G为搜索图 , 初始化为问题的初始状态 s, 建立 OPEN表 ,初始化为只含初始状态 s. 2. CLOSED = (),建立 CLOSED表 ,初始化为空表 . 3. LOOP: IF OPEN=(), THEN EXIT(FAIL) 4. n=FIRST(OPEN), REMOVE(n, OPEN), ADD(n, CLOSED)。 称n为当前节点 . 5. IF GOAL(n) THEN EXIT(SUCCESS)。 由 n循指针返回 s, 可以获得解路径 . 6. EXPAND(n)→mi, G=ADD(mi, G), 子节点集 {mi}中不包含 n的父辈节点 . 人工智能 吉林大学珠海学院计算机科学与技术系 7 标记和修改指针 ADD(mj, OPEN), 并标记 mj连接到 n的指针 , mj是未在 OPEN和 CLOSED中出现过的子节点 . 计算是否需要修改 mk, ml到 n的指针。 mk是出现在 OPEN表中的子节点 , ml是出现在 CLOSED表中的子节点 , {Mi}={Mj}∪{Mk}∪{M l} 计算是否需要修改 mi到其后记节点的指针 . OPEN表中的节点按某种原则重新排序 . LOOP. 人工智能 吉林大学珠海学院计算机科学与技术系 对 GRAPHSEARCH算法的几点说明 : 1. 两个图 , G: 搜索图 , 它是记录算法访问过的所有节点的图 ,初始化为问题的初始状态 s, 在搜索过程中不断地扩展 . T: G的有向支撑树 , 与 G有同样的节点 , 由指针定义 . 记录由该节点到 s的最短路径 , 在搜索过程中需要不断调整 . 2. 两个表 : OPEN和 CLOSED, OPEN表记录搜索图的前沿 , CLOSED表记录已经扩展过的节点 . 3. 树 T的指针的建立和调整 . 树 T中节点的指针记录从该节点到初始节点 s的最短路径 , 随着算法的进行 , 图的扩展 , 这些指针需要不断地调整 . 对新产生的节点 , 为其建立指针 . 对 OPEN和 CLOSED表中的节点 , 需要考虑调整其指针 , 对于 CLOSED表中节点 , 还需要考虑调整其后继节点的指针 . 人工智能 吉林大学珠海学院计算机科学与技术系 Notes about the procedure GRAPHSEARCH 1. Two graphs: G: The explicit part of the graph generated by the production system, its initial node is the initial state, it is expanded constantly. T: the directed support tree of G, it has same nodes as the graph G, his arc(only one outgoing arc from a node) direct the shortest path from one node to another node. The arcs are marked by pointers. In order to preserve the character, the procedure need to readjust the arcs of the tree constantly. 人工智能 吉林大学珠海学院计算机科学与技术系 2. Two list: OPEN the frontier nodes of graph G, from which, we select a node to expand. CLOSED the interior nodes of graph G, the node have been expanded. 3. The establishment and readjustment of the pointers of tree T. For the newly generated nodes, we need to establish the pointer for them. For the nodes in the lists on OPEN and CLOSED , we need to consider to readjust their pointers. For the nodes of CLOSED, we need to consider the readjustment of their descendants, for the adjustment of the nodes of CLOSED may influence their descendant’s pointers 人工智能 吉林大学珠海学院计算机科学与技术系 s 1 2 人工智能 吉林大学珠海学院计算机科学与技术系 1 2 人工智能 吉林大学珠海学院计算机科学与技术系 无信息的图搜索过程 深度优先和宽度优先 深度优先和宽度优先的思想在数据结构中已经讲过 , 在数据结构中是作为树的遍历的方法讲的 , 人工智能中在状态空间中搜索解的过程也类似于遍历 . 所不同的是这里搜索的是图而不是树 .所以这里我们只讨论与解有关的问题 宽度优先在搜索解的过程中总是在探索了层数小于或等于 n的节点之后才进入到 n+1层节点的探索 , 所以这中方法获得的解具有最短的解路径 .但如果图的分枝系数很高 , 或者解路径很长 ,效率会很低 . 深度优先可以很快地使实验解路径延伸到很长 , 如果刚好在延伸的过程中遇到解 , 这种方法的效率会很高 , 但不能保证找到有最短的解路径 . 甚至即使在原问题有解的时候 , 也会发生会在错误的方向上无限延伸下去而找不到解的情况 , 人工智能 吉林大学珠海学院计算机科学与技术系 深度优先算法 Procedure DEPTHFIRTST SEARCH 1 G=s, OPEN=(s), CLOSED = (). 2 LOOP: IF OPEN=(), THEN EXIT(FAIL) 3 n=FIRST(OPEN)。 4 IF GOAL(n) THEN EXIT(SUCCESS)。 5 REMOVE(n, OPEN), ADD(n, CLOSED)。 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 7 ADD(mi, OPEN), 并标记 mi到 n的指针 , 把不在 OPEN和 CLOSED 中的节点放在最前面 , 使深度大的节点可以优先扩展 . 8 GO LOOP 人工智能 吉林大学珠海学院计算机科学与技术系 使用 DEPTHFIRSTSEARCH搜索的例 D6 C4 B4 A5 H3 G4 F5 E5 O2 J I K P3 T S K K L M N goal 人工智能 吉林大学珠海学院计算机科学与技术系 为保证深度优先算法在问题有解的情况下总能找到解 , 需要增加深度限制 , 而且深度限制必须超过解的长度 . 人工智能 吉林大学珠海学院计算机科学与技术系 启发式搜索 4。 0 简介 heuristic Of or relating to a usually speculative formulation serving as a guide in the investigation or solution of a problem: 探索的 ,做为调查或解决问题的向导的一种通常为推测性系统阐述 回溯式搜索， 深度优先和宽度优先都不使用领域知识， 效率很低。 启发式搜索使用关于领域的信息指导， 使搜索向着有利于获得解的方向进展。 如果应用得好，可以明显地缩小搜索空。