《（本科）P2C3搜索问题求解ppt课件.pptx》由会员分享，可在线阅读，更多相关《（本科）P2C3搜索问题求解ppt课件.pptx（46页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、课程主讲人：（本科）P2C3-搜索问题求解ppt课件人工智能原理人工智能原理Principles of Artificial Intelligence某某大学某某学院某某某3第3章 搜索问题求解人工智能原理n 有这样一类问题：n 具有初始状态和目标状态n 每个状态可看作是一个黑盒子n 其状态空间可表示为一棵树或一张图n 可通过搜索找到一个从初始到目标状态的最短路径n 但无法用传统的数学方法进行求解n 这类问题称为搜索问题n 其求解过程是搜索第3章 搜索问题求解引言4人工智能原理第3章 搜索问题求解目录5o 搜索问题o 搜索问题的要素o 搜索问题的实例化o 搜索求解的方式o 无信息搜索o 有信息
2、搜索人工智能原理n 八数码难题（8-Puzzle）搜索问题智力游戏问题6初始状态目标状态 33的棋盘，九个格子上摆有八个棋子，每个棋子上有1至8中的某个数字，不同棋子上的数字不相同。棋盘上余下一个空格，与空格相邻的棋子可以移到空格中。一个状态就是八个棋子在棋盘上的一种摆法。某个棋子移动后，状态就会发生改变。 给定初始和目标状态，目的是找出一种步骤，使之从初始到目标状态所需移动的步数最少。人工智能原理n 八数码难题属于滑块难题（Sliding block puzzles） NP完问题!搜索问题智力游戏问题7n滑块难题又属于二维组合谜题（2D combination puzzle）n此外，还有三维
3、组合谜题（3D combination puzzle），例如魔方（Magic cube）华容道英语拼词漫画人物魔方人工智能原理n 八皇后难题（Eight queens puzzle）搜索问题智力游戏问题8国际象棋棋手马克斯贝瑟尔（Max Bezzel）于1848年提出：在国际象棋的88棋盘上摆放八个皇后，使其不能发生互相攻击（即，任意两个皇后都不能处于同一行、同一列或同一斜线上）。有多少种摆法？上图中七个皇后之间是否有攻击的现象？八皇后难题示例人工智能原理n 传教士和食人族（Missionaries and cannibals）搜索问题智力游戏问题9三个传教士和三个食人族来到一条河的左岸，他们
4、想过河。岸边有一条小船，只能供两个人乘坐：可以是两个传教士、一个传教士和一个食人族，或两个食人族。但无论在船上或岸边，若食人族超过传教士，就会把传教士吃掉。怎样用这条船将其摆渡过河？推而广之，可以考虑N个传教士和N个食人族的问题传教士和食人族人工智能原理n 最短路径问题（Shortest path problem）搜索问题现实世界问题10快递网点间距离问题：某个快递网点布局图，其中：每个节点表示一个快递网点，连接两个节点的边表示快递网点间的路径，边上面的数字表示该条路径的代价。 任意两点间的最短距离？其它实例：v 超大规模集成电路布局（VLSI layout）问题v 机器人导航（Robot n
5、avigation）问题v 等等。快递网点布局图人工智能原理第3章 搜索问题求解目录11o 搜索问题o 搜索问题的要素o 搜索问题的实例化o 搜索求解的方式o 无信息搜索o 有信息搜索人工智能原理n 状态是问题在不同时期或条件下的形态：n 初始状态（Initial state）：问题提出的状态n 目标状态（Goal state） ：问题预期的状态n 搜索问题的状态表征：原子式表征（Atomic representation）搜索问题的要素状态表征12原子式表征：状态的表征是个黑盒子，不考虑其内部结构。这是因为，最短路径问题所关心的是两点之间的路径，而不是节点的内部结构。人工智能原理n 状态空间
6、是问题在不同时期或条件下的所有状态。通常可抽象为一张图（Graph）或一棵树（Tree）。搜索问题的要素状态空间13人工智能原理n搜索问题的要素形式化14人工智能原理n 搜索问题的解是从初始到达目标状态的路径，其求解就是寻找该路径的动作。搜索问题的要素求解的方法15agent SIMPLE-PROBLEM-SOLVING input percept output an action state GET-CURRENT-STATE(state, percept) if seq is empty then goal FORMULATE-GOAL(state) problem FORMULATE-P
7、ROBLEM(state, goal) seq SEARCH(problem) if seq = failure then return a null action action FIRST(seq) seq REST(seq) return action人工智能原理第3章 搜索问题求解目录16o 搜索问题o 搜索问题的要素o 搜索问题的实例化o 搜索求解的方式o 无信息搜索o 有信息搜索人工智能原理n搜索问题的实例化八数码难题17状态迁移人工智能原理n搜索问题的实例化八皇后难题：增量形式化（Incremental formulation）18对角线的皇后？八皇后难题的全态形式化（Comple
8、te-state formulation）方法将在第4章介绍人工智能原理n搜索问题的实例化传教士和食人族问题19人工智能原理n 传教士和食人族问题属于渡河难题类似问题：搜索问题的实例化渡河难题（River crossing puzzles）20n 吃醋丈夫问题（Jealous husbands problem）n 火炬过桥问题（Bridge and torch problem）n 狐狸、鹅与豆袋难题（Fox, goose and bag of beans puzzle）n 船夫与羊、狼和白菜（Goat, wolf and cabbage riddle）人工智能原理n搜索问题的实例化最短路径问题
9、21人工智能原理第3章 搜索问题求解目录22o 搜索问题o 搜索问题的要素o 搜索问题的实例化o 搜索求解的方式o 无信息搜索o 有信息搜索人工智能原理n 用搜索树来寻找一条从快递网点A到终点M的路径。搜索求解的方式树搜索23v A为根节点、M为叶节点。v 虚线表示节点尚未生成。v 粗实线为已生成节点。v 已扩展节点加阴影表示。第1步第2步第3步第4步人工智能原理搜索求解的方式树搜索24agent TREE-SEARCH input problem output a solution, or failurelocal frontier, to store the set of all leaf
10、 nodes initialize the frontier using the initial state of problem loop do if the frontier is empty then return failure choose a leaf node and remove it from the frontier if the node contains a goal state then return the solution expand chosen node, adding resulting nodes to the frontier loop end通用的树
11、搜索（tree search）算法。其中，局部变量 frontier 是一个数据结构，被称为开放表（open list），用于存储所有的叶节点。人工智能原理搜索求解的方式图搜索25agent GRAPH-SEARCHinput problem output a solution, or failure local frontier, to store the set of all leaf nodes; explored, to remember every expanded nodes initialize the frontier using the initial state of pr
12、oblem; initialize the explored to be empty loop do if the frontier is empty then return failure choose a leaf node and remove it from the frontier if the node contains a goal state then return the solution; add the node to explored expand chosen node, adding resulting nodes to frontier; only if not
13、in frontier or explored loop end通用的图搜索（graph search）算法。其中，增加的局部变量 explored 也是一个数据结构，称为封闭表（closed list），用于存储每个扩展节点。人工智能原理n 用搜索图来寻找一条从快递网点A到终点M的路径。搜索求解的方式图搜索26第1步第2步第3步第4步人工智能原理第3章 搜索问题求解目录27o 搜索问题o 搜索问题的要素o 搜索问题的实例化o 搜索求解的方式o 无信息搜索o 有信息搜索人工智能原理n 无信息搜索n 搜索过程中无其它信息，每一步只是生成后继、并判断是否是目标节点。n 亦称：盲目搜索（Blind
14、search）、蛮力搜索（Brute-force search）、穷举搜索（Exhaustive search）。n 搜索策略n 宽度优先搜索n 深度优先搜索n 迭代深化搜索n 回溯深度优先搜索n 双向搜索无信息搜索无信息搜索（Uninformed search）28人工智能原理n 搜索策略扩展最浅的未扩展节点。n 实现方法先进先出（First-In First-Out, FIFO）队列。无信息搜索宽度优先搜索（Breadth-first search）29搜索顺序是节点上所标注的英文小写字母的顺序人工智能原理无信息搜索宽度优先搜索（Breadth-first search）30agent B
15、READTH-FIRST-SEARCH input problem; output a solution, or failurenode a node with State = problem.INITIAL-STATE; PATH-TEST = 0frontier a FIFO queue with node as the only element; explored an empty setloop do if EMPTY ? (frontier) then retunr failure node POP(frontier) / chooses the shallowest node in
16、 frontier add node.STATE to explored for each action in problem.ACTIONS(node.STATE) do child CHILD-NODE(problem, node, action) if child.State is not in explored or frontier then if problem.GOAL-TEST(child.State) then return SOLUTION(child) frontier INSERT(child, frontier) for endloop end人工智能原理n无信息搜索
17、宽度优先搜索（Breadth-first search）31DepthNodesTimeMemory21100.11 milliseconds107 KB (kilobyte)411,11011 milliseconds10.6 MB (megabyte)61061.1 seconds1 GB (gigabyte)81082 minutes103 GB (gigabyte)1010103 hours10 TB (terabyte)12101213 days1 PB (petabyte)1410143.5 years99 PB (petabyte)161016350 years10 EB (ex
18、abyte)人工智能原理无信息搜索汉诺塔（Tower of Hanoi）32 传说印度的婆罗门庙里有3根柱子，第一根柱子上有64块金盘，要通过第二根柱子将这些金盘移动到第三根柱子上。移动的规则很简单： 1）每次仅能移动一块金盘， 2）仅能移动最上面的金盘， 3）大的金盘不能放在小的金盘上面。寺庙里的祭司一直在移动这些金盘，据说当移动最后一块金盘时，世界将会毁灭！人工智能原理n 搜索策略扩展最深的未扩展节点。n 实现方法后进先出（Last-In First-Out, LIFO）队列。无信息搜索深度优先搜索（Depth-first search）33搜索顺序是节点上所标注的英文小写字母的顺序。没有
19、后继的节点从内存中删除人工智能原理n 深度受限搜索（Depth-limited Search）n 用预设的深度限制l，防止深度优先搜索沿着某分枝一直搜索下去。n 亦称：深度受限深度优先搜索（Deep-limited depth-first search）n 问题：设目标节点的深度为d。若ld，则找不到目标。n 故，选择深度限制l非常重要。但d在搜索之前不得而知。n 迭代深化搜索将深度优先与宽度优先相结合n 逐步增加l，直到找到目标。n 迭代内部，执行深度优先搜索。n 迭代之间，相当于宽度优先搜索。亦称：迭代深化深度优先搜索（Iterative deepening depth-first sea
20、rch）无信息搜索迭代深化搜索（Iterative deepening search）34人工智能原理无信息搜索迭代深化搜索（Iterative deepening search）35agent ITERATIVE-DEEPENING-SEARCH input problem output a solution, or failure root = MAKE-NODE(problem.INITIAL-STATE) for limit = 1 to do result DEPTH-LIMITED-SEARCH(root, problem, limit) if result cutoff then
21、 output result end for迭代深化搜索算法 ITERATIVE-DEEPENING-SEARCH。其中，深度限制limit从1开始调用DEPTH-LIMITED-SEARCH函数（下一页）。而该函数是一个递归函数，在其内部完成深度受限搜索。人工智能原理无信息搜索迭代深化搜索（Iterative deepening search）36function DEPTH-LIMITED-SEARCH(node, problem, limit) if problem.Goal-Test(node.State) then return Solution(node) if limit = 0
22、 then return cutoff / no solution cutoff_occurred false for each action in problem.ACTIONS(node.STATE) do child CHILD-NODE(problem, node, action) result DEPTH-LIMITED-SEARCH(child, problem, limit 1) if result = cutoff then cutoff_occurred true else if result failure then return result end for if cut
23、off_occurred then return cutoff / no solution else return failure人工智能原理第3章 搜索问题求解目录37o 搜索问题o 搜索问题的要素o 搜索问题的实例化o 搜索求解的方式o 无信息搜索o 有信息搜索人工智能原理n 有信息搜索n 依据问题提供的或动态生成的信息，沿着有希望的搜索路径尽快找到目标。n 评价函数用于代价估计，优先扩展最低代价的节点。有信息搜索有信息搜索（Informed search）38人工智能原理n有信息搜索统一代价搜索（Uniform cost search）39人工智能原理有信息搜索统一代价搜索（Unifor
24、m cost search）40agent UNIFORM-COST SEARCH input problem; output a solution, or failure loop do if EMPTY(frontier) then return failure node POP(frontier) / chooses the lowest-cost node in frontier if problem.GOAL-TEST(node.State) then return Solution(node) add node.STATE to explored for each action i
25、n problem.ACTIONS(node. STATE) do child CHILD-NODE(problem, node, action) if child. STATE is not in explored or frontier then frontier INSERT(child, frontier) else if child.STATE is in frontier with higher PATH-COST then replace that frontier node with child end for end loop人工智能原理n有信息搜索贪婪最佳优先搜索（Gree
26、dy best-first search）41人工智能原理有信息搜索贪婪最佳优先搜索（Greedy best-first search）42各节点到目标节点M之间的直线距离 首先对起始节点A进行扩展，得到后继节点B、C和D。由右上表可知，这三个节点到达目标节点M的直线距离分别为329、253和374。其中节点C到达M的直线距离最小，扩展C得到后继F、G和J。类似的，节点J到达M的直线距离最小，扩展J得到目标节点M。人工智能原理n有信息搜索43人工智能原理有信息搜索44各节点到目标节点M之间的直线距离人工智能原理n 本章论述了搜索问题的要素及其形式化方法。n 搜索空间可表示为树或图，与其对应的搜索方式就是树搜索和图搜索。n 根据是否具有问题提供的信息来生成评价函数，又分为无信息搜索和有信息搜索。n 无信息搜索策略包括：宽度优先、深度优先、迭代深化搜索。n 有信息搜索策略包括：统一代价搜索、贪婪搜索、A*搜索。第3章 搜索问题求解小结45Q & A46