3-4启发式搜索策略.ppt

*算法肾暗但宾皮由汗馅挨千迢哼吓茧峰矿饥谋壕府碱篇砚拔渡响篱射柿犁戏田3-4启发式搜索策略3-4启发式搜索策略宽度优先、深度优先搜索属于盲目搜索(按规定的路线搜索)。盲目搜索效率低,耗费过多的计算空间与时间。(NOT按规定的路线盲目搜索),则搜索效率将会大为提高。BackgroundandQuestions:.,whichone,thechildrenA,BandCofS,etgoalwithlittlecost?***3-4启发式搜索策略3-: 与具体问题求解相关的控制性知识。:Expressionoftheusefulinformation 估计OPEN表中各扩展节点的重要程度,给它们排定扩展次序。伞锤钨锯阉误蒋血匡设肇抡筷啮铀涧存令晴驼波贮扮啃目钧塞应旁饮乘心3-4启发式搜索策略3-4启发式搜索策略*定义评价函数/估计函数f:f(n)=g(n)+h(n)其中n是被评价的节点。g(n):表示从初始节点S到节点n的路径的代价;h(n):表示从节点n到目标节点G的路径的代价;f(n表示从初始节点S经过节点n到目标节点G的路径的代价。闺竣闷依决秃误疏义贺橙伸瘪磐横环甘绵音显蛾拖吨取诵防踏翌抵州遗册3-4启发式搜索策略3-4启发式搜索策略33…n11定义一个评价函数f…gnhnfn鞭芹箕助斋泛蒲皮囊臼湍飞叶瘦棚耕顿助忠跳氖疚带澄尖国黑边茂违娇阔3-4启发式搜索策略3-4启发式搜索策略33…xn11定义一个评价函数f…gnhnfn远袋期除猩战扳谨当金歉苏平秒芜遣备企勋这群叼随申疡辕罢霓旁栏导***3-4启发式搜索策略3-: 当一个节点扩展后,在它的所有子节点中,选估价函数f(n)最优者作为下一个考察的节点。翅钨獭能厂蓑认跑浚恐撑炉雅互娱蜜贺铱诅闲绣矣海隶岸痞卜讳港途烫涂3-4启发式搜索策略3-4启发式搜索策略例1:用局部择优搜索策略求解八数码问题。估价函数定义为f(n)=g(n)+h(n)。其中,g(n)=d(n)表示搜索depth,等代价时,g(n)(n)issamewhensearchingamongthechildren. h(n)=w(n)表示结点n的格局与目标结点D格局相比位置不符的数码个数。So,估价函数定义为f(n)=w(n)。千牵鹊哨隔蚊镊宇址鞭溉皮集疵蔽狭籽执燎陵曲驯明芳网疚扩幢恼烫椿奇3-4启发式搜索策略3-4启发式搜索策略例1局部择优搜索树-,选估价函数f(n)最优者等代价时,g(n)-4启发式搜索策略3-4启发式搜索策略例1局部择优搜索树-2:城奎粥吭泄哺悄破猪色到挣狸梭他私开敞诺鸡澎睡膀黔熬幕仕入挛撇淄茵3-4启发式搜索策略3-4启发式搜索策略