【概述】

啟發式搜索算法，就是在狀態空間中的搜索對每一個搜索的位置進行評估，得到最好的位置，再從這個位置進行搜索直到目標。

有時我們會遇到這樣的一類題：題目描述的是一道時間復雜度很高的 NP 問題，我們要找到其中的最優解，顯然不可能在短時間內找到最優解。

此時我們可以利用啟發式搜索算法，來進行求解。

在程序設計競賽中，啟發式搜索的題目并不是很多，但啟發式搜索算法在數據建模競賽中應用的比較廣泛。

【隨機數據生成】

在開始學習啟發式搜索算法之前，首先了解一下隨機數據生成。

在 C++ 中，隨機數據生成是利用 <cstdlib> 來調用 rand() 與 srand() 函數，來生成偽隨機數序列，其中：

• rand() 函數：返回 0~RAND_MAX 間的隨機整數
• srand(unsigned int seed)：根據 seed 的值，來初始化偽隨機數序列

在 windows 環境下，RAND_MAX=32767，當利用 srand() 初始化時，如果 seed 的值不變，那么利用 rand() 生成的隨機整數將一直相同，因此，我們需要利用一個時刻改變的變量對其進行初始化

在 <ctime> 中，有一個 time(time_t *t) 函數，其可以獲取當前系統時間，因此，在實際應用中，常利用以下方式來生成隨機序列：

srand(time(0)); int num=rand(); cout<<num<<endl;

【常見的啟發式搜索算法】

常見的啟發式搜索算法有：A* 算法、蟻群算法、遺傳算法、模擬退火、禁忌搜索、爬山法等，但在程序設計競賽中，常用的是 A*算法、模擬退火、爬山法。

A* 算法：點擊這里

模擬退火：點擊這里

爬山法：點擊這里

【例題】

平衡點 / 吊打XXX（洛谷-P1337）(模擬退火)：點擊這里

Buried memory（HDU-3007）(爬山法)：點擊這里

總結

以上是生活随笔為你收集整理的搜索 —— 启发式搜索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。