回溯算法一:算法介绍与经典问题分析

互联网 2021/4/8 12:13:38

目录一、算法介绍二、3-着色问题1、问题描述2、分析过程三、8-皇后问题1、问题描述2、分析过程四、Hamilton回路问题1、问题描述2、分析过程五、子集和问题1、问题描述2、分析过程 一、算法介绍 1、普遍地适用于解决需要检测有限但是大量的可能的解的组合问题。 2、基本框…

目录
  • 一、算法介绍
  • 二、3-着色问题
    • 1、问题描述
    • 2、分析过程
  • 三、8-皇后问题
    • 1、问题描述
    • 2、分析过程
  • 四、Hamilton回路问题
    • 1、问题描述
    • 2、分析过程
  • 五、子集和问题
    • 1、问题描述
    • 2、分析过程

一、算法介绍

1、普遍地适用于解决需要检测有限但是大量的可能的解的组合问题。

2、基本框架:深度优先搜索,从顶点逐层遍历;针对当前节点,遍历取值范围,若为合法部分解,则递归进入下一层,否则更换本层的其他顶点;若本层顶点遍历完后,均无合法部分解,则回溯到上一层。

二、3-着色问题

1、问题描述

给定一个无向图G=<V,E>,需要对其中的每一个顶点着1、2、3三种颜色之一,使得任意两个相邻顶点不是同种颜色。

输入:图G=<V,E>,三种颜色

输出:若存在合法的着色方案,输出所有解向量c=<c1,c2,...,cn>, 1<=ci<=3,表示第i个顶点的着色。

2、分析过程

1、针对n个顶点的图,以深度优先的策略进行搜索,对当前节点着色,判断是否合法,若合法则进行下一层,若不合法,则变换当前节点的着色。

2、若遍历颜色后,均不合法,则回溯到当前节点的父节点,变换着色。(回溯过程)

3、若从根到叶子的着色方案合法,输出合法解。

三、8-皇后问题

1、问题描述

经典8-皇后问题:在一个8*8的棋盘上放置8个皇后,使得任意两个皇后之间不能相互攻击。若两个皇后同处于1行、1列或者1个斜线上,则可以相互攻击。

n-皇后问题:对任意的n>1,有n个皇后,放置在n*n的棋盘上,使其任意两个不能相互攻击。

输入:棋盘规模n

输出:棋盘合法布局,x=<x1,x2,...,xn>

2、分析过程

1、由于不能同处于一行或者一列,则棋盘上每行每列均只能放置一个皇后。

2、可以用向量x=<x1,x2,...,xn>表示棋盘上第i行的皇后放置的列的位置,一个x即为一个解。由于不能同列,则x实际上是x1,x2,...,xn的一个排列。

3、利用深度优先搜索,树根表示为放置任何皇后。第一层表示第一行的皇后放置的列的位置,第二层表示第二行的皇后放置的列的位置,依次类推。

4、从根节点开始遍历,逐层监测对应列放置的位置,若监测到该行的合法位置则继续下一行,否则回溯到上一层。

四、Hamilton回路问题

1、问题描述

在一个无向图G=<V,E>中,寻求中顶点s出发,经过G中每一个顶点一次,最后回到顶点d的回路。

输入:具有n个顶点的无向图G=<V,E>,起始顶点s。

输出:合法Hamilton回路,向量x=<x1,x2,...,xn>

2、分析过程

1、以起始顶点s为根节点,按深度优先原则搜索。

2、逐次遍历当前顶点的相邻顶点,判断是否可以扩展成下一个分量。

3、若可以扩展,则递归进入下一层;若与当前顶点相邻的顶点均不能扩展,则回溯到上一层。

五、子集和问题

1、问题描述

1、在一个整数集合A={a1,a2,...,an}中,寻找一个子集合A`中元素的和等于给定元素C。

输入:整数集合A={a1,a2,...,an},整数值C

输出:向量x=<x1,x2,...,xn>,xi=0或者1,表明a1是否属于子集合。

2、分析过程

1、从根节点开始,按深度优先搜索;

2、对当前节点,分别用0、1检测是否构成合法的部分解;

3、若是,则进入下一层;若0和1均不能构成合法部分解,则回溯到上一层。

随时随地学软件编程-关注百度小程序和微信小程序
关于找一找教程网

本站文章仅代表作者观点,不代表本站立场,所有文章非营利性免费分享。
本站提供了软件编程、网站开发技术、服务器运维、人工智能等等IT技术文章,希望广大程序员努力学习,让我们用科技改变世界。
[回溯算法一:算法介绍与经典问题分析]http://www.zyiz.net/tech/detail-153794.html

上一篇:Java基础00-分支语句6

下一篇:javascript中排序算法大全

赞(0)

共有 条评论 网友评论

验证码: 看不清楚?
    关注微信小程序
    程序员编程王-随时随地学编程

    扫描二维码或查找【程序员编程王】

    可以随时随地学编程啦!

    技术文章导航 更多>
    扫一扫关注最新编程教程