哇！講個"爬坡"演算法

mp.weixin.qq.com

昨天女朋友問我這樣一個問題：

有一個很大的矩陣，要找出其中所有的峰值（即比周圍四個值都大的點），邊界不算。

這個問題很自然的想法就是遍歷矩陣中每個點，然後對每個點做4次比較，得到結果，計算次數太多。需要4*n*n次比較。

很自然的優化措施是保存兩個相鄰值之間比較的結果，這樣的話將比較次數由4*n*n次降低到了2*n*n次。

想想看能不能更少呢，答案肯定是可以的，如果某一點在第一次與相鄰值比較時就」失敗「，那剩下的幾次比較是不必要的。然而基於這個思路的剪枝效果並不很棒。

反過來想一想，如果比較發現周圍有個值比當前點的值大，那這個大的點是不是更有可能是」峰值「呢。

完善一下上述想法，構想出這樣的演算法：隨機選一點開始」爬坡「，直至到」山頂「，並一路標記走過的點。再隨機選一個未被標記的點，重複」爬坡「過程，得到新的」山頂「。

因為也是基於遍歷的演算法，所以」山頂「的」找全性「是可以得到保證的，演算法做的就是剪枝。核心代碼如下：

運行結果輸出：

剪枝在人機棋類博弈中也會用到，我大學時寫過一個下五子棋的程序，其中也大量用到剪枝優化。

本文代碼可以在知識星球下載。

https://t.zsxq.com/aiYzByV (二維碼自動識別)

歡迎關注我的公眾號：

http://weixin.qq.com/r/ii8lPdDEHI1jrZRe93qY (二維碼自動識別)