回溯搜索算法的程序 - - Powered by Discuz!

标题: 回溯搜索算法的程序 [打印本页]

作者: 51hei丽人 时间: 2016-6-20 23:12
标题: 回溯搜索算法的程序
回溯搜索这种算法那是相当的有用，而且对于初学者来说还很简单。学习它的前提是你必须先理解一下递归是怎么回事。。如果不知道你可以上百度搜一搜或是在空间里找到关于我写的递归的那篇文章。。如果已经理解了递归那么理解回溯搜索就是一件很简单的事了。

回溯是怎么回事呢？说简单了就是“一条路搜到黑”，当无法再继续搜下去时我就返回上一步。有点像左手法则，总是最终的结果就是会从左到右的（或从右到左）遍历整个树（即遍历所有情况）。

那么，既然是说明算法那么总得举几个例子来看看吧。这里有一道“经典”的题目：



      输入一个长度=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个加号，但有时候我们插入了更多，有时候我们一个也没有插入。对这些情况的搜索浪费了相当多的时间。你可以通过加一个计数器来计算这个程序一共遍历了多少个节点。而实际上有许多借点可以丢弃。如何来优化它？方法就是就是剪枝。我们下一次再讨论。

欢迎光临 (http://www.51hei.com/bbs/)