算法设计与分析ch7 Tree searching strategies.pptVIP

A*算法本质—已经发现的解是优化解 定理1. 使用Best-first策略有哪些信誉好的足球投注网站树, 如果A*选择的节点是 目标节点, 则该节点表示的解是优化解. 证明. 令n是任意扩展到的节点, t是选中目标节点. 往证f(t)=g(t)是优化解代价. (1). A*算法使用Best-first策略, f(t)?f(n). (2). A*算法使用h(n)?h*(n)估计规则, f(t)?f(n)?f*(n). (3). {f*(n)}中必有一个为优化解的代价, 令其为f*(s). 我们有f(t) ?f*(s). (4). t是目标节点h(t)=0, 所以f(t)=g(t)+h(t)=g(t)?f*(s). (5). f(t)=g(t)是一个可能解, g(t)?f*(s), f(t)=g(t)=f*(s). A*算法的规则 (1). 使用Best-first策略有哪些信誉好的足球投注网站树; (2). 节点n的代价函数为f(n)=g(n)+h(n), g(n)是 从根到n的路径代价, h(n)是从n到某个目 标节点的优化路径代价; (3). 对于所有n, h(n)?h*(n); (4). 当选择到的节点是目标节点时, 算法停止, 返回一个优化解. 应用A*算法求解最短路径问题 问题的输入: A*算法的执行全过程 S V3 V2 V1 V4 V5 T 2 3 4 3 2 2 2 2 3 5 1 S V3 V2 V1 V4 V5 T 2 3 4 3 2 2 2 2 3 5 Step 1 S V1 V3 V2 2 4 3 g(V1)=2 g(V3)=4 g(V2)=3 h(V1)=min{2,3}=2 h(V3)=min{2}=2 h(V2)=min{2,2}=2 f(V1)=2+2=4 f(V3)=4+2=6 f(V2)=2+2=5 4 6 5 1 S V3 V2 V1 V4 V5 T 2 3 4 3 2 2 2 2 3 5 Step 2. 扩展V1 g(V4)=2+2=4 g(V2)=2+3=5 h(V4)=min{3,1}=1 h(V2)=min{2, 2}=2 f(V4)=4+1=5 f(V2)=5+2=7 S V3 V2 2 4 3 4 6 5 V4 V2 V1 2 3 1 5 7 S V3 V2 V1 V4 V5 T 2 3 4 3 2 2 2 2 3 5 Step 3. 扩展V2 g(V4)=3+2=5 g(V5)=3+2=5 h(V4)=min{3,1}=1 h(V5)=min{5}=5 f(V4)=5+1=6 f(V2)=5+5=10 S V3 2 4 3 4 6 5 V4 V2 V1 2 3 1 5 7 V4 V5 2 2 V2 6 10 S V3 V2 V1 V4 V5 T 2 3 4 3 2 2 2 2 3 5 Step 4. 扩展V4 g(V5)=2+2+1=5 g(T) =2+2+3=7 h(V5)=min{5}=5 h(T)=0 f(V5)=5+5=10 f(V2)=7+0=7 S V3 2 4 3 4 6 5 V2 V1 2 3 1 5 7 V4 V5 2 2 V2 6 10 V5 T 1 3 V4 7 10 S V3 V2 V1 V4 V5 T 2 3 4 3 2 2 2 2 3 5 Step 5. 扩展V3 g(V5)=4+2=6 h(V5)=min{5}=5 f(V5)=6+5=11 S V3 2 4 3 6 5 1 V4 V5 2 2 V2 6 10 4 V2 V1 2 3 5 7 V5 T 1 3 V4 7 10 V5 2 11 S V3 V2 V1 V4 V5 T 2 3 4 3 2 2 2 2 3 5 Step 6. 扩展V4 g(V5)=3+2+1=6 g(T) =3+2+3=8 h(V5)=min{5}=5 h(T)=0 f(V5)=6+5=11 f(T)=8+0=8 S V3 2 4 3 6 5 1 4 V2 V1 2 3 5 7 V5 T 1 3 V4 7 10 V5 2 11 V5 T 1 V4 V5 2 2 V2 6 10 3 11 8 S V3 V2 V1 V4 V5 T 2 3 4 3 2 2 2 2 3 5 Step 7. 扩展T 因为T是目标节点, 所以我们得到解: S?V1 ?V4?T S V3 2 4 3 6 5 1 4 V2 V1 2 3 5 7 V5 T 1 3 V4 7 10 V5 2 11 V5 T