《人工智能》搜索技术

第四章搜索技术状态空间法问题归约法博弈树搜索局部搜索Howtofindthebestpathingame?迷宫问题s-----ssssss-----s-----s-----ss-----s-----s-----ssssssss-----s-----s-----s-----sS0Sg搜索的挑战—组合爆炸魔方问题博弈问题皇后问题行商问题排课问题（调度问题）背包问题…………数码问题1238456712384567（目标状态）（初始状态）八数码难题（8-puzzleproblem）426183574.1状态图概念状态图的概念状态图(状态空间图)实际上是一类问题的抽象表示。许多智力问题(八数码问题、梵塔问题、旅行商问题、八皇后问题、农夫过河问题等)。实际问题（如路径规划、定理证明、演绎推理、机器人行动规划等）都可以归结为在某一状态图中寻找目标或路径的问题。农夫过河问题有一个农夫带一条狼、一只羊和一棵白菜过河。如果没有农夫看管，则狼要吃羊，羊要吃白菜。但是船很小，只够农夫带一样东西过河。问农夫该如何解此难题？农夫过河问题状态空间法表示以向量（人，狼，羊，菜）表示状态，其中每个变元可取0或1，取0表示在左岸（出发点），取1表示在右岸初态是：（0，0，0，0）终态是：（1，1，1，1）非法中间状态有：（0，0，1，1），（0，1，1，0），（0，1，1，1），（1，1，0，0），（1，0，0，1），（1，0，0，0）。（1，0，0，1）（0，0，0，0）（1，0，1，0）（1，1，0，0）（0，0，1，0）（1，1，1，0）（1，0，1，1）（0，1，1，0）（0，0，1，1）（人，狼，羊，菜）（0，0，0，1）（1，1，0，1）（0，1，0，1）（1，1，1，1）4.2状态空间法问题的状态空间表示(状态图表示)状态空间的三元组(S,O,G)表示.S:初始状态集合;O:操作集合;G:目标状态集合状态空间的搜索策略(状态图搜索)广度优先搜索,深度优先搜索,启发式搜索状态空间表示的概念例如下棋、迷宫及各种游戏。OriginalStateMiddleStateGoalState三数码难题123123123312312312初始棋局目标棋局1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345八数码难题的宽度优先搜索树13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567状态图搜索图搜索是指在状态图中寻找目标或路径的搜索。所谓搜索，顾名思义，就是从初始节点出发，沿着与之相连的边试探地前进，寻找目标节点的过程(也可以反向进行)。问题状态图搜索解解是由初始状态到目标状态的路径状态图搜索—相关问题状态选择解的性质：存在、分布、质量搜索策略图搜索策略图搜索控制策略一种在状态图中寻找路径的方法。图中每个节点对应一个状态，每条连线对应一个操作符。图搜索涉及两个主要数据结构：open表closed表OPEN表OPEN表是一种动态数据结构，专门登记当前待考查（待访问）的节点，也叫未扩展节点表。节点父节点编号OPEN表open表中，每个节点信息还包括指向父节点的返回指针（即父节点地址）CLOSED表Closed表是一种动态数据结构，记录访问过的节点，也叫已扩展节点表，其初始为空表。编号节点父节点编号CLOSED表开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图搜索过程框图是是否否搜索策略即体现在这里按搜索轨迹分类图式搜索：搜索过程中，搜索路径允许形成回路。树式搜索：搜索过程中，搜索路径不允许形成回路。线式搜索：扩展节点每次只扩展一个节点。SGSG搜索树的概念一个可以搜索出某个可行解的问题，如“农夫、白菜、羊、狼”和“八数码难题”等，虽然从表面上看上去和“树”这种结构无关，但是整个搜索过程中的可能试探点所行成的搜索空间总可以对应到一颗搜索树上去。将各类形式上不同的搜索问题抽象并统一成为搜索树的形式，为算法的设计与分析带来巨大的方便。22178634582736451827163452282763451238276345114687634512787345126152163458782345817631645827931458276171621786345381635472108354276181654273813542761821786345481356247128456217381546273138136274521202178365452178634511119（1，0，0，1）（0，0，0，0）（1，0，1，0）（1，1，0，0）（0，0，1，0）（1，1，1，0）（1，0，1，1）（0，1，1，0）（0，0，1，1）（人，狼，羊，菜）（0，0，0，1）（1，1，0，1）（0，1，0，1）（1，1，1，1）由于搜索具有探索性，所以要提高搜索效率(尽快地找到目标节点)，或要找最佳路径(最佳解)就必须注意搜索策略。对于状态图搜索，已经提出了许多策略，它们大体可分为盲目搜索（blandsearch)和启发式搜索（heuristicsearch）两大类。盲目搜索是无向导搜索。启发式搜索是有向导搜索，即利用启发信息（函数）引导去寻找问题解。搜索策略分类盲目搜索盲目搜索又叫做无信息搜索，一般只适用于求解比较简单的问题。种类：宽度优先搜索深度优先搜索等代价搜索图搜索策略宽度优先深度优先启发式搜索一种在图中寻找路径的方法。宽度优先搜索策略优先搜索状态空间中离初始状态近的节点(状态特点:具有完备性,占用空间搜索算法数据结构:OPEN表:先进先出队列,存放待扩展的节点.节点(状态)父节点编号(返回指针)CLOSED表:存放已被扩展过的节点.编号节点父节点编号开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的末端，提供返回节点n的指针失败成功宽度优先算法框图是否是否算法否宽度优先搜索算法Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN表中第一个节点N放入CLOSED表中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,将生成的一组子节点配上指向N的指针后,放入OPEN表尾部,转Step2;例子八数码难题（8-puzzleproblem）1238456712384567（目标状态）（初始状态）规定：将牌移入空格的顺序为：从空格左边开始顺时针旋转。不许斜向移动，也不返回先辈节点。从图可见，要扩展26个节点，共生成26个节点之后才求得解（目标节点）。1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345图八数码难题的宽度优先搜索树13456123845671238456712384567123845671238456723242526271236782212384567123845671238456712384567123845671238456712384567141516171819202112384567宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(1)CLOSED=()6789101112131415宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(2,3)CLOSED=(1)6789101112131415宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(3,4,5)CLOSED=(1,2)6789101112131415宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(4,5,10,11)CLOSED=(1,2,3)6789101112131415宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(5,10,11,6,7)CLOSED=(1,2,3,4)6789101112131415宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(10,11,6,7,8,9)CLOSED=(1,2,3,4,5)6789101112131415宽度优先搜索(Breadth-FirstStrategy)新的节点被插入到栈OPEN的后部12345OPEN=(11,6,7,8,9,12,13)CLOSED=(1,2,3,4,5,10)6789101112131415深度优先搜索策略新节点优先扩展,直到达到一定的深度限制.若找不到目标或无法在扩展时,回溯到另一节点继续扩展.特点:需要深度限制,需要回溯控制,省空间探索算法:数据结构:OPEN表:后进先出队列,存放待扩展的节点.CLOSED表:存放已被扩展过的节点.除扩展后的子节点应放入到OPEN表的首部以外,与宽度优先算法一样.深度优先算法框图算法开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表是否有后继节点为目标节点？扩展n，把n的后继节点放入OPEN表的前端，提供返回节点n的指针失败成功是否是否深度优先搜索算法Step1:把初始节点S0放入OPEN表中;Step2:若OPEN表为空,则搜索失败,退出.Step3:移出OPEN中第一个节点N放入CLOSED表中,并标以顺序号n;Step4:若目标节点Sg=N,则搜索成功,结束.Step5:若N不可扩展,则转Step2;Step6:扩展N,将生成的一组子节点配上指向N的指针后,放入OPEN表首部,转Step2;深度优先搜索(Depth-FirstStrategy)新的节点被插入到栈OPEN的前部12345OPEN=(1)CLOSED=()6789101112131415Depth-FirstStrategy新的节点被插入到栈OPEN的前部12345OPEN=(2,3)CLOSED=(1)6789101112131415Depth-FirstStrategy新的节点被插入到栈OPEN的前部12345OPEN=(4,5,3)CLOSED=(1,2)6789101112131415Depth-FirstStrategy新的节点被插入到栈OPEN的前部12345CLOSED=(1,2,4)67OPEN=(6,7,5,3)89101112131415Depth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6)OPEN=(7,5,3)12131415Depth-FirstStrategy新的节点被插入到栈OPEN的前部1234567891011CLOSED=(1,2,4,6,7)OPEN=(5,3)1213