內(nèi)容啟發(fā)式搜索

1、Heuristic Search啟發(fā)式搜索譯 by()必要條件遞歸算法主要概念啟發(fā)式搜索的主要目標(biāo)是使用一個估價函數(shù)去判斷所有狀態(tài)的“好壞”，以提高搜索找到解的效率。通常，估價函數(shù)表示成一個函數(shù)或是一個狀態(tài)，這個函數(shù)叫做“估價函數(shù)”例如：迷宮尋找出路的時候，到出口的距離D=(xI-xj)2+(yI-yj)21/2。 式中，D 是點(diǎn)i 和點(diǎn)j 之間的距離； xI xj是第i 個點(diǎn)的坐標(biāo)；yI yj 是第j 個點(diǎn)的坐標(biāo)。（譯者注）當(dāng)嘗試在一場跳棋比賽中獲勝時，能對手的最多棋子子設(shè)計估價函數(shù)直觀地看，估價函數(shù)越優(yōu)秀，搜索就更好（快）。問題是：怎么評價估價函數(shù)的好壞呢？估價函數(shù)的好壞，取決于它評估一個

2、狀態(tài)好壞的能力。例如，迷宮的例子，怎么計算到出口的距離？能繞很多的路：距離也許非常的壞，甚至是非常小的迷宮，它也可一般來說，估價函數(shù)越好，搜索就越快。一般來說，搜索時間和估價函數(shù)的準(zhǔn)確性如下圖：注意！一個似乎很“傻”的估價函數(shù)可以大大地提高程序的效率！（如果它非常完美地被使用）另一個重要概念是“可接受”，一個可接受的估價函數(shù)表示對于每個點(diǎn)都不存在“低估”的情況。例如，迷宮的例很清楚地說明了這一點(diǎn)。距離啟發(fā)函數(shù)是“低估”的，剛才的圖方法 1：啟發(fā)式剪枝最簡單也是最常用的啟發(fā)式搜索是利用估價函數(shù)來剪枝。假設(shè)是要求找最小總花費(fèi)。對于一個可接受的估價函數(shù)，當(dāng)前花費(fèi)是 A，啟發(fā)函數(shù)返回了 B，當(dāng)前子問的

3、最優(yōu)解是A+B。如果找到的一個解一個花費(fèi)是 C，CA+B，這個狀態(tài)就不必要搜索了。這樣編寫和調(diào)試也比較簡單（假設(shè)一個狀態(tài)需要長時間而被剪掉），且可以極大地提高程序效率。它對DFS 尤其有效。方法 2：最佳優(yōu)先搜索這種方法好比就是貪心算法。每次不擴(kuò)展所有子結(jié)點(diǎn)，而是按“好壞程度”來擴(kuò)展。與貪心不同的是，貪心只嘗試“最優(yōu)”路徑，但是BFS 首先擴(kuò)展“希望大”的，再擴(kuò)展“希望小”的，如果結(jié)合上述描述，搜索會得到很好的結(jié)果。Idea #3: A* Search方法 3：A*法A*法是類似貪心 BFS 的。BFS 一般擴(kuò)展最小耗費(fèi)的點(diǎn)。A*算法在另一方面，擴(kuò)展最有希望的點(diǎn)（估價函數(shù)返回值最優(yōu)）。狀態(tài)被保存在一個優(yōu)先隊列中，按照 Cost*價值排列。每一次，程序處理最低優(yōu)先的點(diǎn)，且把它的孩子按照適當(dāng)順序處理。對于一個可容許的估價函數(shù)，第一個找到的狀態(tài)保證是最優(yōu)的。例題騎士覆蓋傳統(tǒng)問題一個n*n 的棋盤，問最少放多少騎士，使整個棋盤被擊）（騎士所在點(diǎn)不被攻分析：可行的：啟發(fā)函數(shù)總共被的點(diǎn)/8（每個騎士最多可以用上面任何方法實現(xiàn)，經(jīng)管 A*存在一點(diǎn)小問題。8 個方各）這8 數(shù)碼問題傳統(tǒng)問題大家熟悉的 8 數(shù)碼 3*3 的方格，有一個空格，可以把四個方向數(shù)移動到空，最后到目標(biāo)狀態(tài)5 _ 46 1 87 3 25 1 46 _ 87 3 2要求步數(shù)最少1 2 34 5 67 8 _啟發(fā)函數(shù)：