清華大學人工智能導論課程電子教案143-資料下載頁

　　

【正文】 。 112 s(10) A(1) B(5) C(8) G 目標 6 3 1 1 1 8 前面的例子： OPEN表 CLOSED表 fm s(0+10) s(0+10) 10 A(6+1) B(3+5) C(1+8) s(0+10) C(1+8) 10 A(6+1) B(2+5) s(0+10) C(1+8) B(2+5) 10 A(3+1) s(0+10)C(1+8)B(2+5)A(3+1) 10 G(11+0) 113 h的單調化方法 ?如果令： f(n) = max(f(n的父節點 ), g(n)+h(n)) 則容易證明，這樣處理后的 h是單調的。 114 IDA*算法 (Iterative Deepening A*) ?基本思想：回溯與 A*的結合 ?算法簡介（非嚴格地） 1，設初始值 f0； 2，集合 S＝ NULL； 3，用回溯法求解問題，如果節點 n的 f值大于 f0，則將該節點放入集合 S中，并回溯； 4，如果在 3中找到了解，則結束； 5，如果 3以失敗結束，則 f0＝ S中節點的最小 f值； 6，返回到 2。 115 知識的靈活應用 例：如何轉動，使得每個扇區數字和為 12。 1 3 5 5 1 4 4 1 3 3 2 5 2 3 1 2 3 1 2 2 5 5 2 3 4 2 5 4 3 4 3 3 分析： 陰影部分數字和： 48 直徑部分數字和： 24 轉 45176。改變陰影部分 轉 90176。改變直徑部分 但不改變陰影部分 轉 180176。改變扇區部分 但不改變陰影部分 也不改變直徑部分 116 4，其他的搜索算法 ?爬山法（局部搜索算法） 117 其他的搜索算法（續 1） ?隨機搜索算法 ?動態規劃算法 如果對于任何 n，當 h(n)=0時， A*算法就成為了動態規劃算法。 118 動態規劃 S0 t S1 S2 S3 Sn …… …… …… W0 W1,1 W1,2 W2,1 W2,2 W2,3 W3,3 W3,2 W3,1 Wn,1 Wn,2 Wn,3 Wn+1 119 其中： Q(Wij)表示到點 Wij的最佳路徑值 D(Wi1,j, Wi,k)表示 Wi1,j到 Wi,k的距離 ? ????????????0i00i)W,W(D)W(Qmin)W(Qj,ik,1ik,1ikj,i120 5，搜索算法實用舉例 ?漢字識別后處理 ?一個例子 我錢線載哦栽哉裁劣綏 優仍們仿倫奶砧犯扔妨 要耍密窮安壁駐努窯垂 扳報叔嵌奴振技寂敘蔽 奮夯杏蠶香脊秀吞吝番 精猜指潔括治捐活冶桔 種神襯祥科鐘拌樣拎補 121 漢字識別后處理 ????niii PSP111 )...|()( )()|()()|( OPSOPSPOSP ?二元語法時： ????niii wwPSP11 )|()()(OP為常量 )|( SO用識別信度代替 問題變為求 ???niiii wCFwwP11 )()|(最大 122 第三章 與或圖的搜索 目標 目標 初始節點 s a b c 123 基本概念 ?與或圖是一個超圖，節點間通過連接符連接。 ? K連接符： …... K個 124 耗散值的計算 k(n, N) = Cn+k(n1, N)+…+k(n i, N) 其中： N為終節點集 Cn為連接符的耗散值 …... i個 n n1 n2 ni 125 目標 目標 初始節點 ? 解圖： 126 能解節點 ?終節點是能解節點 ?若非終節點有“或”子節點時，當且僅當其子節點至少有一能解時，該非終節點才能解。 ?若非終節點有“與”子節點時，當且僅當其子節點均能解時，該非終節點才能解。 127 不能解節點 ?沒有后裔的非終節點是不能解節點。 ?若非終節點有“或”子節點，當且僅當所有子節點均不能解時，該非終節點才不能解。 ?若非終節點有“與”子節點時，當至少有一個子節點不能解時，該非終節點才不能解。 128 普通圖的情況 f(n) = g(n) + h(n) 對 n的評價實際是對從 s到 n這條路徑的評價 n s 129 與或圖 : 對局部圖的評價 目標 目標 初始節點 a b c 130 兩個過程 ?圖生成過程，即擴展節點 – 從最優的局部途中選擇一個節點擴展 ?計算耗散值的過程 – 對當前的局部圖新計算耗散值 131 AO*算法舉例 其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0 設： K連接符 的耗散值為 K 目標 目標 初始節點 n0 n1 n2 n3 n4 n5 n6 n7 n8 132 目標 目標 初始節點 n0 n1 n2 n3 n4 n5 n6 n7 n8 初始節點 n0 n1(2) n4(1) n5(1) 紅色： 4 黃色： 3 133 目標 目標 初始節點 n0 n1 n2 n3 n4 n5 n6 n7 n8 初始節點 n0 n4(1) n5(1) 紅色： 4 黃色： 6 n1 n2(4) n3(4) 5 134 目標 目標 初始節點 n0 n1 n2 n3 n4 n5 n6 n7 n8 紅色： 5 黃色： 6 初始節點 n0 n4(1) n5(1) n1 n2(4) n3(4) 5 n6(2) n7(0) n8(0) 2 135 目標 目標 初始節點 n0 n1 n2 n3 n4 n5 n6 n7 n8 紅色： 5 黃色： 6 初始節點 n0 n4(1) n5(1) n1 n2(4) n3(4) 5 n6(2) n7(0) n8(0) 2 1 136 博弈樹搜索 ?博弈問題 – 雙人 – 一人一步 – 雙方信息完備 – 零和 137 分錢幣問題 （ 7） （ 6,1） （ 5,2） （ 4,3） （ 5,1,1） （ 4,2,1） （ 3,2,2） （ 3,3,1） （ 4,1,1,1） （ 3,2,1,1） （ 2,2,2,1） （ 3,1,1,1,1） （ 2,2,1,1,1） （ 2,1,1,1,1,1） 對方先走 我方必勝 138 中國象棋 ?一盤棋平均走 50步，總狀態數約為 10的161次方。 ?假設 1毫微秒走一步，約需 10的 145次方年。 ?結論：不可能窮舉。 139 1，極小極大過程 0 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 0 3 3 3 3 2 1 3 6 3 0 3 1 6 0 1 1 極大 極小 a b 140 ??剪枝 ?極大節點的下界為 ?。 ?極小節點的上界為 ?。 ?剪枝的條件： – 后輩節點的 ?值 ≤祖先節點的 ?值時， ?剪枝 – 后輩節點的 ? 值 ≥祖先節點的 ?值時， ?剪枝 ?簡記為： – 極小 ≤極大，剪枝 – 極大 ≥極小，剪枝 141 ??剪枝（續） 0 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 0 0 3 0 3 3 0 5 4 1 1 3 1 6 6 1 a b c d e f g h i j k m n 142 ??剪枝的其他應用 ?故障診斷 A B C D ?風險投資 143 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH