前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >回溯法算法框架

回溯法算法框架

作者头像
用户1154259
发布2018-01-17 15:47:44
1.2K0
发布2018-01-17 15:47:44
举报

回溯法:有通用解题法 之称,可以系统的搜索一个问题的所有解和任一解,是一个既带有系统性,又带有跳跃性的搜索算法。

算法基本思想:

  确定解空间后

  从开始节点出发,以深度优先的方式搜索整个解空间。

  如果当前扩展结点不能再向纵深方向移动,当前节点为死节点。此时,应该往回移动至最近的一个活节点处。,并是这个或节点成为当前节点的扩展结点。

提高算法方式(剪枝函数)

  1 用约束函数在扩展结点出剪去不满足约束的子树

  2 用限界函数剪去得不到最优解的子树。

回溯法解题步骤:

  1 定义问题的解空间

  2 确定易于搜索的解空间结构

  3 以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

递归回溯:

代码语言:javascript
复制
void Backtrack(int t)
{
    if(t>n)
        Output(x);
    else
        for(int i=f(n,t);i<=(g,t);i++)
        {
            x[t] = h(i);
            if(Constraint(t) && Bound(t))
                Backtrack(t+1);
        }
}

子集树:

当所有的问题是从n个元素的集合S中找出满足某种性质的子集时,相应的解空间树称为子集树。

伪码为:

代码语言:javascript
复制
void Backtrack(int t)
{
    if(t>n)
        Output(x);
    else
        for(int i=f(n,t);i<=(g,t);i++)
        {
            x[t] = h(i);
            if(Constraint(t) && Bound(t))
                Backtrack(t+1);
        }
}

排列树:

当所给的问题是确定n个元素满足某种性质的排列时,相应的解空间树称为排列数。

伪码为:

代码语言:javascript
复制
void Backtrack(int t)
{
    if(t>n)
        Output(x);
    else
        for(int i=f(n,t);i<=(g,t);i++)
        {
            Swap(x[t],x[i]);
            if(Constraint(t) && Bound(t))
            {
                Backtrack(t+1);
            }
            Swap(x[t],x[i]);
        }
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2012-10-22 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档