評價函數
評價函數
在搜索過程中，關鍵的一步是如何確定要擴展的節點，不同的確定方法就形成不同的搜索策略。如果在確定節點時能充分利用與問題求解有關的特性信息，估計出節點的重要性，就能夠在搜索時選擇重要性較高的節點進行擴展，從而求得最優解。而啟髮式搜索正是這種利用問題自身的某些特性信息，指導搜索朝著最有希望有方向前進的一種方法。
目錄
在啟髮式搜索中，用於評價節點重要性的函數叫做評價函數。評價函數的主要任務就是估計等搜索結點的重要程度，以確定結點的優先順序程度。評價函數的一般形式為
f(x)=g(x)+h(x)
其中g(x)為初始節點S0到節點x已經實際付出的代價。當希望有較高的搜索效率，且只關心到達目標節點的路徑時，g(x)可以忽略，但此時會影響到搜索的完備性。h(x)為節點x到目標節點Sg的最優路徑的估計代價，它體現了總是的啟發性信息，又稱為啟發函數，其形式要根據總是的特性而定。啟發函數h(x)所攜帶的啟發性的信息越多，搜索時擴展的節點數就越少，搜索的效率就越高。因此在確定f(x)時，要使得g(x)與h(x)各占適當的比率。
在實際問題求解時，g(x)可以根據已經搜索的節點信息計算出來，而啟發函數h(x)依賴於人們的經驗。它來源於我們對問題的某些特性的認識。
構造和選擇合適的啟發函數h(x)是啟髮式搜索的關鍵。在構造h(x) 時，應滿足兩個方面的要求：首先，啟發函數要簡單易算；其次，函數要有較高的精確度，能夠反應問題的實際情況。而在實際問題中，這兩個方面的要求是相互制約的，很難同時得到滿足。若將啟發函數設計得簡單易算，那麼此函數的精度往往不會很高，產生的誤差也大；若將啟發函數設計得有較高的精確度，那麼函數會很複雜，計算也需較長時間。所以構造一個好的啟發函數，要綜合考慮這兩個方面的因素。