请阐述状态空间的一般搜索过程.OPEN表与CLOSED表的作用是什么?人工智能课后习题

Question

请阐述状态空间的一般搜索过程.OPEN表与CLOSED表的作用是什么?
人工智能课后习题

Answer 1

状态空间的一般搜索过程
OPEN表：用于存放刚生成的节点
CLOSE表：用于存放将要扩展或已扩展的节点
1) 把初始节点S0放入OPEN表,并建立只含S0的图,记为G
OPEN：=S0,G：=G0（G0=S0）
2) 检查OPEN表是否为空,若为空则问题无解,退出
LOOP：IF（OPEN）=（） THEN EXIT（FAIL）
3) 把OPEN表的第一个节点取出放入CLOSE表,记该节点为节点n
N：=FIRST（OPEN）,REMOVE（n,OPEN）,ADD（n,CLOSE）
4) 观察节点n是否为目标节点,若是,则求得问题的解,退出
IF GOAL（n） THEN EXIT（SUCCESS）
5) 扩展节点n,生成一组子节点.把其中不是节点n先辈的那些子节点记作集合M,并把这些节点作为节点n的子节点加入G中.
EXPAND（n）-->M（mi）,G：=ADD（mi,G）
针对M中子节点的不同情况,分别进行如下处理
对于那些未曾在G中出现过的M成员设置一个指向父节点（n）的指针,并把它放入OPEN表
对于那些先前已在G中出现过的M成员,确定是否要修改指向父节点的指针
对于那些先前已在G中出现,并且已经扩展了的M成员,确定是否需要修改其后继结点指向父节点的指针
6) 按某种搜索策略对OPEN表中的节点进行排序
7) 转第2步