《人工智能》第2章问题求解智能体_1.pdf

《人工智能》第2章 问题求解智能体(1) 丁嵘 dingr@buaa.edu.cn 北航软件开发环境国家重点实验室 大纲  问题求解智能体  问题形式化  无信息的有哪些信誉好的足球投注网站  有信息的有哪些信誉好的足球投注网站  约束满足问题  博弈论中的对抗有哪些信誉好的足球投注网站 2014/3/12 2 例：连连看!  环境  环境大小: 12 * 7  方块类型: 21 * 4  行动  连接两个相同的动物方块，并删除它们  性能和目标  删除所有的方块  时间最少 2014/3/12 3 例：旅行 2014/3/12 4 问题求解智能体  一种基于目标的智能体  三个步骤  问题形式化  有哪些信誉好的足球投注网站（Search ）  执行（Execute ） 2014/3/12 5 问题形式化  问题分为四个元素  初始状态  如：at Arad  后续函数S(x) = 行动-状态对集合  如：S(Arad) = {(Go(Sibzu),In(Sibiu)), (Go(T imisoara), In( Tzmisoara))…}  目标测试  明确的, x = At(Bucharest)  含糊的, Checkmate(x)  路径耗散  如：距离的和、行动的数量等 2014/3/12 6 问题形式化  问题的解  从初始状态到目标状态的行动序列  解的质量由路径耗散函数度量  最优解（optimal solution ）  具有最低路径耗散的解 2014/3/12 7 例: 国际象棋  初始状态  如右图  后续函数  移动棋子  目标测试  Checkmate：判断谁赢  路径耗散  步数、时间 2014/3/12 8 例: 真空吸尘器  初试状态  灰尘和吸尘器位置  后续函数  目标测试  所有位置没灰尘  左移、右移、吸尘  路径耗散  每个动作路径开销为1 2014/3/12 9 例：八数码  初始状态  如右上图  后续函数  通过产生一步行动（上下左 右移）到达的合法状态  目标测试  与目标状态匹配？  路径耗散