人工智能导论-第一章-21101861.pptVIP

* 汉字识别后处理 一个例子 我钱线载哦栽哉裁劣绥 优仍们仿伦奶砧犯扔妨 要耍密穷安壁驻努窑垂 扳报叔嵌奴振技寂叙蔽 奋夯杏蚕香脊秀吞吝番 精猜指洁括治捐活冶桔 种神衬祥科钟拌样拎补 * 汉字识别后处理 二元语法时： 为常量 用识别信度代替 问题变为求 最大 * * * * * * * * * * A算法的思想，从open中选择一个节点 * * * * * * 突破口：H值估计的要合理，即应该满足单调条件。考虑到h满足A*条件，所以父子节点的h值差，应该小于等于c才合理。 * * * * 2，最佳图有哪些信誉好的足球投注网站算法A*（A*算法） 在A算法中，如果满足条件： h(n)≤h*(n) 则A算法称为A*算法。 * A*条件举例 8数码问题 h1(n) = “不在位”的将牌数 h2(n) = 将牌“不在位”的距离和 2 8 3 1 6 4 7 5 1 2 3 4 5 7 6 8 将牌1：1 将牌2：1 将牌6：1 将牌8：2 * 定义h函数的一般原则 放宽限制条件，在宽条件下，给出估计函数。 例：传教士与野人问题 思路：放宽约束条件，在宽约束条件下得到一个估计值。 假设只有乘船人数的约束没有其他约束 从左岸到右岸至少需要的摆渡次数： * 从右岸到左岸至少需要的摆渡次数： M+C 综合在一起，所需的最少摆渡次数： M+C-2b 以该最小摆渡次数作为启发函数h，从推到可知，该h满足A*条件 * * A*算法的两个主要结论 定理 (可采纳性定理)： 若存在从初始节点s到目标节点t有路径，则A*必能找到最佳解结束。 定理：设对同一个问题定义了两个A*算法A1和A2，若A2比A1有较多的启发信息，即对所有非目标节点有h2(n) h1(n)，则在具有一条从s到t的路径的隐含图上，有哪些信誉好的足球投注网站结束时，由A2所扩展的每一个节点，也必定由A1所扩展，即A1扩展的节点数至少和A2一样多。 简写：如果h2(n) h1(n) (目标节点除外)，则A1扩展的节点数≥A2扩展的节点数 * * 注意： 上述定理4，评价指标是“扩展的节点数”，也就是说，同一个节点无论被扩展多少次，都只计算一次。 * 思考题 定理（简写）：如果h2(n) h1(n) (目标节点除外)，则A1扩展的节点数≥A2扩展的节点数 为什么条件不能是h2(n) ≥ h1(n) ？什么情况下会出现问题？能否给定理在增加条件，使得定理在h2(n) ≥ h1(n) 条件下也成立？ * 对h的评价方法 平均分叉数 设共扩展了d层节点，共有哪些信誉好的足球投注网站了N个节点，则: 其中，b*称为平均分叉数。 b*越小，说明h效果越好。 实验表明，b*是一个比较稳定的常数，同一问题基本不随问题规模变化。 * 对h的评价举例 例：8数码问题，随机产生若干初始状态。 使用h1： d=14, N=539, b*=1.44; d=20, N=7276， b*=1.47； 使用h2： d=14, N=113, b*=1.23; d=20, N=676, b*=1.27 * A*的复杂性 一般来说，A*的算法复杂性是指数型的，可以证明，当且仅当以下条件成立时： abs(h(n)-h*(n)) ≤ O(log(h*(n))) A*的算法复杂性才是非指数型的，但是通常情况下， h与h*的差别至少是和离目标的距离成正比的。 * 3，A*算法的改进 问题的提出： 因A算法第6步对ml类节点可能要重新放回到OPEN表中，因此可能会导致多次重复扩展同一个节点，导致有哪些信誉好的足球投注网站效率下降。 * s(10) A(1) B(5) C(8) G 目标 6 3 1 1 1 8 一个例子： OPEN表 CLOSED表 s(10) s(10) A(7) B(8) C(9) A(7) s(10) B(8) C(9) G(14) A(5) C(9) G(14) C(9) G(12) B(7) G(12) A(4) G(12) G(11) B(8) s(10) A(5) B(8) s(10) C(9) A(5) s(10) B(7) C(9) s(10) A(4) B(7) C(9) s(10) * 出现多次扩展节点的原因 在前面的扩展中，并没有找到从初始节点到当前节点的最短路径，如节点A。 问题的突破口？ s(10) A(1) B(5) C(8) G 目标 6 3 1 1 1 8 * 解决的途径 对h加以限制 能否对h增加适当的限制，使得第一次扩展一个节点时，就找到了从s到该节点的最短路径。 对算法加以改进 能否对算法加以改进，避免或减少节点的多次扩展。 * 改进的条件 可采纳性不变 不多