回溯搜索這種算法那是相當?shù)挠杏�，而且對于初學者來說還很簡單。學習它的前提是你必須先理解一下遞歸是怎么回事。。如果不知道你可以上百度搜一搜或是在空間里找到關(guān)于我寫的遞歸的那篇文章。。如果已經(jīng)理解了遞歸那么理解回溯搜索就是一件很簡單的事了。
回溯是怎么回事呢？說簡單了就是“一條路搜到黑”，當無法再繼續(xù)搜下去時我就返回上一步。有點像左手法則，總是最終的結(jié)果就是會從左到右的（或從右到左）遍歷整個樹（即遍歷所有情況）。
那么，既然是說明算法那么總得舉幾個例子來看看吧。這里有一道“經(jīng)典”的題目：
輸入一個長度=15的字符串(此處示范為"342589062876256")，在其中插入5個“+”號，盡量使得最終結(jié)果最小。該怎么寫呢？
這里使用VBScript做一個示范吧：
Dim ax, ex
ax=10^10
ex=""
Function Rec (Str1, InsertAt, Plus_N)
'注釋：Str1：當前字符串。InsertAt：當前指針的位置。Plus_N:剩余的加號數(shù)量
Dim a, StrA, StrB, StrC
If InsertAt = Len(Str1) Then '如果搜索到了字符串的末尾
If Plus_N = 0 Then '如果剩余加號數(shù)量為0，（而不是負數(shù)或正數(shù)）
a = Eval(Str1) '計算結(jié)果值 if a<ax Then '如果小于“最優(yōu)值” ax = a '儲存他
ex = Str1
End If
Else
Exit Function
End If
Else
StrA = Mid (Str1, 1, InsertAt)'把字符串分段
StrB = Mid (Str1, InsertAt + 1, Len(Str1) - InsertAt)
Rec StrA & "+" & StrB, InsertAt + 2, Plus_N - 1 '先嘗試在其中插入加號的情況
Rec StrA & StrB, InsertAt + 1, Plus_N '再嘗試不插入加號的情況。這樣就能遍歷所有的情況了。
End If
End Function
Rec "342589062876256", 1, 5 '調(diào)用函數(shù)
msgbox ex & "=" & ax '儲存結(jié)果
當然，你會發(fā)現(xiàn)這段代碼存在的問題也很大，有很大的優(yōu)化空間，題目要求只能插入5個加號，但有時候我們插入了更多，有時候我們一個也沒有插入。對這些情況的搜索浪費了相當多的時間。你可以通過加一個計數(shù)器來計算這個程序一共遍歷了多少個節(jié)點。而實際上有許多借點可以丟棄。如何來優(yōu)化它？方法就是就是剪枝。我們下一次再討論。
|
QQ好友和群
QQ空間
騰訊微博
騰訊朋友
收藏
淘帖
頂
踩
