回溯法算法框架

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

算法基本思想:

  确定解空间后

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

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

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

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

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

回溯法解题步骤:

  1 定义问题的解空间

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

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

递归回溯:

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中找出满足某种性质的子集时,相应的解空间树称为子集树。

伪码为:

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个元素满足某种性质的排列时,相应的解空间树称为排列数。

伪码为:

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]);
        }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

详解斯坦纳点及斯坦纳树及模版归纳总结

①什么是斯坦纳点?   假设原来已经给定了个点,库朗等指出需要引进的点数至多为,此种点称为斯坦纳点。过每一斯坦纳点,至多有三条边通过。若为三条边,则它们两两交成...

93560
来自专栏灯塔大数据

每周学点大数据 | No.30前序计数

No.30期 前序计数 Mr. 王:我们再来说说父子关系判定的应用。前序计数是一种非常常用的对树进行处理的方法。前序计数实现的就是对各个节点按照其前序遍...

34870
来自专栏小樱的经验随笔

Codeforces Round #412 (rated, Div. 2, base on VK Cup 2017 Round 3)(A.B.C,3道暴力题,C可二分求解)

A. Is it rated? time limit per test:2 seconds memory limit per test:256 megabyte...

38570
来自专栏owent

C++ 新特性学习(六) — 新的字符串编码和伪随机数

使用u””为能至少储存UTF-16的16位元编码,对应’\u’表示16位元的字符。

9510
来自专栏自学笔记

Data Structure_图图论带权图

交通运输,社交网络,互联网,工作的安排,闹区活动等等都可以用到图论处理。图可以分成两大类,一类是无向图,就是没有方向的,就好像两个人都互相认识一样,有向图就是单...

8510
来自专栏用户2442861的专栏

MATLAB 中有哪些命令,让人相见恨晚?

提问都说了是命令,大家回答那么多函数干什么... 我来给一个超级大杀器 在命令行敲入 dbstop if error

52010
来自专栏mathor

LeetCode42. 接雨水

 有人说用贪心,我觉得这是一个单调栈的板子题,构建一个单调递减栈(栈底到栈顶是递减的),要想能够收集雨水,栈中至少要两个数字,才能形成一个坑,先pop一个数...

66420
来自专栏应兆康的专栏

100个Numpy练习【4】

Numpy是Python做数据分析必须掌握的基础库之一,非常适合刚学习完Numpy基础的同学,完成以下习题可以帮助你更好的掌握这个基础库。

813120
来自专栏数据结构与算法

1893. [国家集训队2011]等差子序列(bitset)

★★   输入文件:nt2011_sequence.in   输出文件:nt2011_sequence.out 简单对比 时间限制:0.3 s   内存限制:5...

356100
来自专栏Spark学习技巧

CountVectorizer

CountVectorizer 关于文本特征提取,前面一篇文章TF-IDF介绍了HashingTF,本文将再介绍一种Spark MLlib的API CountV...

70770

扫码关注云+社区

领取腾讯云代金券