算法设计策略----回溯法和分枝限界法

显示约束解空间:规定每个分量xi取值的约束条件称为显式约束。对给定的一个问题,显示约束规定了所有可能的元组,他们组成问题的候选解集,被称为该问题实例的解空间。

隐式约束判定函数:隐式约束给出了判定一个候选解是否为可行解的条件。一般需要从问题描述的隐式约束出发,设计一个判定函数,程序根据判定函数判断一个解是否为可行解。

最优解目标函数:目标函数,也称代价函数,用来衡量每个可行解的优劣。使目标函数取得最大(小)值的可行解为问题的最优解。

剪枝函数:为了提高搜索效率,在搜索过程中使用约束函数,可以避免无谓地搜索那些已知不含答案状态的子树。如果是最优化问题,还可以使用限界函数剪去那些不可能含有最优解的子树。约束函数和限界函数目的相同,都是为了剪去不必要搜索的子树,减少问题求解所需实际生成的状态结点数,他们统称为剪枝函数。

使用剪枝函数的深度优先生成状态空间树中的节点的求解方法称为回溯法;广度优先生成结点,并使用剪枝函数的方法称为分枝限界法

一个问题能够用回溯法求解的条件:

  1. 它的解具有n-y元组的形式;
  2. 问题提供显式约束来确定状态空间树,并提供隐式约束来判定可行解;
  3. 能设计有效的约束函数缩小检索空间。

回溯法算法框架:

Void RBacktrack(int k){
    for(每个x[k],使得x[k]∈T[x[0],...,x[k-1]&&B(x[0],...x[k]){
        if(x[o],x[1],...,x[k]是一个可行解)
            输出(x[o],x[1],...,x[k]);
        RBacktrack(k+1);
    }
}

回溯法相关算法:

分枝限界法相关算法:

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏MixLab科技+设计实验室

用谷歌新开源的deeplearnJS预测互补颜色

本文翻译自deeplearnJS的示例教程,并结合了我在学习过程中的理解。 deeplearnJS简介: deeplearn.js是用于机器学习的开源WebGL...

3288
来自专栏小鹏的专栏

01 TensorFlow入门(2)

Working with Matrices:         了解TensorFlow如何使用矩阵对于通过计算图理解数据流非常重要。 Getting read...

2846
来自专栏PaddlePaddle

【序列到序列学习】使用Scheduled Sampling改善翻译质量

生成古诗词 序列到序列学习实现两个甚至是多个不定长模型之间的映射,有着广泛的应用,包括:机器翻译、智能对话与问答、广告创意语料生成、自动编码(如金融画像编码)...

1.1K5
来自专栏Hadoop数据仓库

HAWQ + MADlib 玩转数据挖掘之(十一)——分类方法之决策树

一、分类方法简介 1. 分类的概念         数据挖掘中分类的目的是学会一个分类函数或分类模型(也常常被称作分类器),该模型能把数据库中的数据项映射到给定...

33410
来自专栏DHUtoBUAA

编程求取直线一般式表达式,两直线交点

背景介绍   最近在水面无人艇(USV)模拟仿真中,用到了一些点和线的关系求解,本文主要讲述一下两点确认直线,点到直线距离,两条直线的交点等问题的解决方法,并给...

5017
来自专栏Gaussic

使用TensorFlow训练循环神经网络语言模型

读了将近一个下午的TensorFlow Recurrent Neural Network教程,翻看其在PTB上的实现,感觉晦涩难懂,因此参考了部分代码,自己写了...

2663
来自专栏人工智能LeadAI

实现与优化深度神经网络

全连接神经网络 辅助阅读:TensorFlow中文社区教程 - 英文官方教程(http://www.tensorfly.cn/tfdoc/tutorials/m...

35811
来自专栏Python数据科学

一款非常棒的特征选择工具:feature-selector

本篇主要介绍一个基础的特征选择工具feature-selector,feature-selector是由Feature Labs的一名数据科学家williamk...

2794
来自专栏智能算法

决策树算法之----C4.5

1. C4.5算法简介 C4.5是一系列用在机器学习和数据挖掘的分类问题中的算法。它的目标是监督学习:给定一个数据集,其中的每一个元组都能用一组属性...

46712
来自专栏从流域到海域

How to Use the TimeDistributed Layer for Long Short-Term Memory Networks in Python 译文

How to Use the TimeDistributed Layer for Long Short-Term Memory Networks in Pyth...

56012

扫码关注云+社区

领取腾讯云代金券