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