Heuristic Search 16, March, 2012

Report
Heuristic Search
16, March, 2012
9717133 林煥博
15 – Puzzle Problem
• 我們利用空格移動格子 達到全部15個格子
都照順序排好
• Uva 10181 (請參照題目)
Heuristic Function
• Heuristic Function是對於目前局面的評估值
• 依照問題需求訂出相對應的Function
• 如果是15-Puzzle Problem
• Heuristic( x ) = (猜測還要走幾步)
Heuristic Function
• 一種參考的定法, 我們定義一個15 – puzzle
的Heuristic Function, H(x)
• H(x)評估方法為 – 計算15個格子到自己正確
位置的曼哈頓距離
Heuristic Function
• Heuristic Search的效果好壞一大部分的效果
取決於Heuristic Function
• 若找到的H(x)越接近事實(Best Cost under x),
則效果越好
A*
• 相當類似BFS, 但我們使用的Queue不是普通
的Queue, 採用的是Priority Queue
• 我們dequeue時, 取出的東西為當前Queue中
Actual Cost + Heuristic Cost最小的
IDDFS
• Iterative Depthening DFS, 非常類似DFS, 我們
一直用DFS順序搜尋下去
• 唯一的差別在於IDDFS有深度限制, 並且不
斷增長
IDDFS
• IDDFS邏輯概念
• DFS(int depth)
•
if(depth > limit) failed, return ;
•
…
• While(DFS not succeed) limit increase
IDA*
• 基本上就是加上Heuristic Search性質的IDDFS
• 因為limit是一種限制
• 故IDA*的H(x)比A*的多出一項限制
• H ( x ) + Actual Cost (真正走了幾步) <= Best
Cost under x (x為一局面)
IDA*
• 之所以有 H ( x ) + Actual Cost (真正走了幾步)
<= Best Cost under x (x為一局面) 的限制
• 是因為我們不能”誤判”x此局面會超出limit
而誤刪了此局發展, 就不符合IDDFS的目標了

similar documents