(3.1)--PPT-启发式搜索机器学习模型与算法.ppt

《(3.1)--PPT-启发式搜索机器学习模型与算法.ppt》由会员分享，可在线阅读，更多相关《(3.1)--PPT-启发式搜索机器学习模型与算法.ppt（8页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、启发式搜索问题与认知目标问题：给定多个城市之间的交通图，如何找到任意两个城市（从城市A到城市K）之间行驶时间最短路线？认知目标：了解启发式搜索基本概念掌握贪婪最佳优先搜索和A*算法在搜索的过程中利用与所求解问题相关的辅助信息，其代表算法为在搜索的过程中利用与所求解问题相关的辅助信息，其代表算法为贪婪最佳优先搜索贪婪最佳优先搜索(Greedy best-first search)和和A*搜索搜索。搜索算法：启发式搜索搜索算法：启发式搜索(有信息搜索有信息搜索)问题：寻找从城市问题：寻找从城市A A到城市到城市K K之间行驶时之间行驶时间最短路线？间最短路线？搜索算法：启发函数与评价函数搜索算法：

2、启发函数与评价函数辅助信息所求解问题之外、与所求解问题相关的特定信息或知识。评价函数（评价函数（evaluation functionevaluation function）f(n)f(n)下一个结点是谁？下一个结点是谁？启发函数（启发函数（heuristicheuristic function function）h(n)h(n)完成任务还需要多少代价完成任务还需要多少代价？贪婪最佳优先搜索贪婪最佳优先搜索(Greedy best-first search)(Greedy best-first search)：评价函数：评价函数f(n)f(n)=启发函数启发函数h(n)h(n)状态状态ABCD

3、EFGHIJKLh(n)131061278536306每个状态（城市）所对应启发函数取值 搜索算法：搜索算法：贪婪最佳优先搜索贪婪最佳优先搜索贪婪最佳优先搜索贪婪最佳优先搜索(Greedy best-first search)(Greedy best-first search)：评价函数：评价函数f(n)f(n)=启发函数启发函数h(n)h(n)图3.4 贪婪最佳优先搜索的过程贪婪最佳优先搜索算法时间和空间复杂度贪婪最佳优先搜索算法时间和空间复杂度状态状态ABCDEFGHIJKLh(n)131061278536306每个状态（城市）所对应启发函数取值不只是搜索自己的子节点，而是所有的边缘集合

4、搜索算法：搜索算法：A*算法算法状态状态ABCDEFGHIJKLh(n)131061278536306每个状态（城市）所对应启发函数取值 搜索算法：搜索算法：A*算法算法图图3.5 A*算法的搜索过程算法的搜索过程状态状态ABCDEFGHIJKLh(n)131061278536306每个状态（城市）所对应启发函数取值课后题ABCDEFGHI13312124315状态状态ABCDEFGHI启发函数543255210考虑考虑图中的问题，给定每个状态的启图中的问题，给定每个状态的启发函数如下表所示。若以状态发函数如下表所示。若以状态A A为初始为初始状态，状态状态，状态I I为终止状态，请根据为终止状态，请根据A*A*搜搜索的方法画出搜索树。若有多个节点索的方法画出搜索树。若有多个节点拥有相同的扩展有限度，则优先扩展拥有相同的扩展有限度，则优先扩展对应路径字典序较小的节点。对应路径字典序较小的节点。