e第彐章图搜索与问题求解 要电大营出版283电数大学 4|S 765 283 84|S1 217 86 5345 要65765 765 83 765 65 65 7655学 品要电子故大8418画要电大学 765 要电大学23 S|7 23大学 765 6 图3-8八数码问题的全局择优搜索
第 3 章 图搜索与问题求解 图 3-8 八数码问题的全局择优搜索
e第彐章图搜索与问题求解 例3.5用全局择优搜索法解八数码难题 初始棋局和目标棋局同例3。蕌 解设启发函数h(x)为节点x的格局与目 标格局相比数码不同的位置个数。以这个函 数制导的搜索树如图3-8所示。此八数问题的 解为:S。S1,S2S3,S
第 3 章 图搜索与问题求解 例 3.5 用全局择优搜索法解八数码难题。 初始棋局和目标棋局同例3。 解 设启发函数h(x)为节点x的格局与目 标格局相比数码不同的位置个数。以这个函 数制导的搜索树如图3-8所示。此八数问题的 解为：So , S1 , S2 , S3 , Sg
e第彐章图搜索与问题求解 31.5加权状态图搜索 加权状态图与代价树蕌 例3.6图3-%(a)是一个交通图,设A城是出发地E城 是目的地,边上的数字代表两城之间的交通费。试求 从A到E最小费用的旅行路线
第 3 章 图搜索与问题求解 3.1.5 加权状态图搜索 1.加权状态图与代价树 例3.6 图3-9(a)是一个交通图,设A城是出发地,E城 是目的地, 边上的数字代表两城之间的交通费。试求 从A到E最小费用的旅行路线
e第彐章图搜索与问题求解 要4B6要3O4 AO OE oc B 安电 版画 D D2 O Er 3 Q B2 O D3 E E 2 dD学出 E B C (b) 图3-9交通图及其代价树
第 3 章 图搜索与问题求解 图 3-9 交通图及其代价树
e第彐章图搜索与问题求解 代价树的搜索。所谓代价,可以是两点之间的距 离、交通费用或所需时间等等。通常用g(x)表示从 初始节点S到节点x的代价,用C(x1x)表示父节点x到 子节点x的代价,即边(xx)的代价。从而有 g(xi =g(xi)tc(x;s x) 而 g(S。)=0
第 3 章 图搜索与问题求解 代价树的搜索。所谓代价,可以是两点之间的距 离、交通费用或所需时间等等。通常用g(x)表示从 初始节点So到节点x的代价, 用c(xi,xj)表示父节点xi到 子节点xj的代价,即边(xi,xj)的代价。从而有 g(xj)＝g(xi)＋c(xi, xj) 而 g(So)＝0