算法实践与创新论文

XX学

算法实践创新文



题目 回溯法分析应

学生姓名：
学号：












摘
计算机科学说算法概念关重算法系列解决问题清晰指令说够定规范输入限时间获求输出更加解算法篇文中先研究算法回溯法
回溯法种常重基设计方法基做法范围搜索适解组合数相问题圆排列描述定n等圆 C1C2„Cn现n圆排进矩形框中求圆矩形框底边相切圆排列问题求n圆排列中找出长度圆排列图着色问题数学定义定图G（V E）中V顶点集合E边集合图着色问题V分K颜色组组形成独立集中没相邻顶点优化版希获K值符号三角形问题求定n计算少符号三角形含+数相
篇文中运回溯法解决着图着色问题符号三角形问题图排列问题三问题进行深入探讨





关键词 回溯法 图着色问题 符号三角形问题 图排列问题


I

目录
第1章 引言 1
第2章 回溯法背景 2
第3章 图着色问题 4
31 问题描述 4
32 四色猜想 4
33 算法设计 5
34 源代码 6
35 运行结果图 10
第4章 符号三角形问题 11
41 问题描述 11
42 算法设计 11
43 源代码 12
44 运行结果图 16
第5章 圆排列问题 17
51 问题描述 17
52 问题分析 17
53 源代码 18
54 运行结果图 22
结 23
参考文献 24

II

第1章 引言
现实世界中相类问题试求问题全部解求问题优解基方法通枚举法搜索问题解空间许问题解空间问题规模n增长呈指数规律增长问题理解实际行搜索空间减少需采良搜索技术回溯法种较搜索技术
回溯法称试探法种效试探回溯搜索技术运回溯法求解问题基某种确定法通量反复试探回溯基做法搜索避免必搜素穷举式搜索回溯法问题解空间树中深度优先策略根结点出发搜索解空间树算法搜索解空间树意点时先判断该节点否包含问题解果肯定包含跳该结点根子树搜索逐层祖先结点回溯否进入该子树继续深度优先策略搜索简单说采回溯法求解问题整程贯穿搜索试探—决定回溯前进三种基运算
通运回溯法解决问题譬熟知八皇问题01背包问题教学阶段中运实际运中产生作学程中会遇样问题寻找定问题解集者找出满足某约束条件优解时候采回溯法解决类问题通运回溯法解决问题譬熟知八皇问题01背包问题教学阶段中运实际运中产生作回溯法优点容易理解行性较强[1] 原福永算法设计分析机械工业出版社1998P213214








第2章 回溯法背景
回溯法种穷举类型算法说种算法倒说种试法回溯法没什高深算法思想然名字起高规格实算法性连二分查找里说算法性实指技巧性问题特性解越深入越创造出巧妙算法时间复杂度级提高算法效率体现算法效率适性间矛盾二分查找效率高适性较低类似著名KMP算法穷举法效率低适问题回溯法种试探性算法点穷举法终究穷举法回溯法组织进行穷举试探程中断通题设求减少搜索空间种减少解减少搜索空间进行规模剪枝实际搜索空间远远问题解空间回溯法实际运行效率较高回溯法应背景说说算法情况 会果算法回溯法高效忘回溯法基穷举回溯法适解排列组合类问题说目标解候选空间中选择出数量级考虑设候选空间n果选择重复生成搜索树完全n叉树搜索空间n^n（01背包问题生成解空间高度n完全二叉树中n物体数）果选择重复生成解空间n(TSP问题生成解空间n中n城市数)说通分析发现问题解空间n^n者n时回溯法回溯法解决问题首先确定问题状态空间树难步选择少选值第步8选值树第层8节点第二步5选值第层节点5分支第二层8×540节点类推……第n层m1×m2×……×mn节点中mi第i步选值数[2] 王晓东计算机算法设计分析电子工业出版社2012P5354

确定状态空间树步搜索时候体现出回溯法优势前面说嘛回溯法特点规律组织进行搜索面回溯法进行搜索：开始搜索前先说做事情解量solution分量应步选择结果显然解量长度应该n（采c语言标准标范围0n1）现状态空间树（逻辑实现）解量（物理装数）现开始搜
索先设定标rr解量标标识状态树第r行先做第步令r0选solution[0]树第0行选择值放入solution[0]显然刚开始应该选择第前面提8里面第然半成品解量否行说刚选择值否满足求加入值满足求应该选择第二类推直选择行值放入solution[0]然r++进行第二步选择solution[1]样应该树第二行中选择第构成解否行（时解量中包含两元素）样步骤直进行直出现样情况[3] 毛静华刘丽红基回溯法案例推理方法研究情报杂志2015P4041

（1）rn1说问题行解时候题设求果求找行解时算法停止
（2）某层候选值选完知道没层候选值定数面提例子中第二层5候选值果五候选值试探完没行解该办呢？里体现思想回溯法名字回溯令r退回新选择面解面例子先选择8中第作解部分然发现面5前面组成行解说明前面选择行面搭配应该返回选择8中第二然5进行选择第二想匹配
（3）种情况程中回溯程r程r0说明整树搜索完问题没行解
回溯法般两种代码实现方案递方法非递方法相递设计方法较简单前面提r作递变量果满足搜索条件递调r+1应函数果满足递调r1应函数基础步r＜0rn1分应解行解说非递方法循环方法设计细节较掌握特点问题适性强（代码通少修改应问题）加效率高递算法（循环优势）里着重讲回溯非递代码实现

第3章 图着色问题
31 问题描述
定连通图Gm>0种颜色准者m中颜色G结点重色情况否途中相邻两结点具颜色

32 四色猜想
四色问题m图着色问题特例根四色原理证明面球面图区域四种颜色着色两段公边界相邻区域没相颜色
问题转换成面图４－着色判定问题(面图画面边交叉图)图区域变成结点两区域相邻相应结点条边连接起
4
3
5
2
1
1
2
3
4
5

年然已证明5种颜色足幅图着色直找定求4种颜色图直1976年问题爱普尔黑肯考西利电子计算机帮助解决证明4种颜色足图着色[4] 冯俊算法程序设计基础教程清华学出版社2010P252256





图






图31
33 算法设计
考虑图讨m种颜色情况定图着色方法通回溯方法断节点着色前面n1节点合法着色开始第n节点进行着色时候枚举m颜色通第n节点相邻节点颜色判断颜色否合法果找种颜色第n节点够着色说明m种颜色方案行
m种颜色图G(VE)着色中V顶点数nn元组x(x1x2…xn)描述图种着色中xi∈{1 2 … m}(1≤i≤n)表示赋予顶点i颜色例5元组(1 2 2 3 1)表示具5顶点图（a）种着色顶点A着颜色1顶点B着颜色2顶点C着颜色2等等
果n元组X中相邻顶点会着相颜色称n元组行解否效解容易出顶点着颜色m种选择n顶点mn种着色方案问题解空间棵高度n完全m叉树里树高度定义根节点叶子节点路径长度分支结点m子结点底层mn叶子结点














图32
34 源代码
#include
#include
using namespace std

const int N 5
const int M 3
ifstream fin(5d8txt)

class Color
{
friend int mColoring(int int int **)
private
bool Ok(int k)
void Backtrack(int t)
int n
m
**a
*x
long sum
}

int mColoring(int nint mint **a)

int main()
{
int **a new int *[N+1]
for(int i1i {
a[i] new int[N+1]
}
cout<<图G邻接矩阵< for(int i1 i {
for(int j1 j {
fin>>a[i][j]
cout< }
cout< }
cout<<图G着色方案：< cout< for(int i1i {
delete[] a[i]
}
delete []a
}

void ColorBacktrack(int t)
{
if (t>n)
{
sum++
for (int i1 i cout << x[i] <<
cout << endl
}
else
{
for (int i1i x[t]i
if (Ok(t)) Backtrack(t+1)
}
}
}

bool ColorOk(int k)
{
for (int j1j {
if ((a[k][j]1)&&(x[j]x[k]))
{
return false
}
}
return true
}

int mColoring(int nint mint **a)
{
Color X


Xn n
Xm m
Xa a
Xsum 0
int *p new int[n+1]
for(int i0 i {
p[i] 0
}
Xx p
XBacktrack(1)
delete []p
return Xsum
}



图m着色问题解空间树中结点数结点坏情况ok检查前扩展结点子相应颜色性需耗时O(mn)回溯法总时间耗费：













35 运行结果图









图33

第4章 符号三角形问题
41 问题描述
图14+14组成符号三角形2号面+2异号面

+ + + + +
+ +
+ + +
+ +
+

+
图41
般情况符号三角形第行n符号符号三角形问题求定n计算少符号三角形含+数[5] 冯学军石冰算法设计分析安庆师范学院学报2012年第18卷P2332



42 算法设计
符号三角形问题n元组[1n]表示符号三角形第行n字符X[i]1表示第行第i符号+X[i]0表示第行第i符号1 算法中递方法backtrack（1）实现整解空间回溯搜索Backtrack（i）搜索整解空间中第i层子树类Triangles数成员记录解空间中间点信息减
少传backtrack参数Sum记录前已找+数数相符号三角形数
算法backtrack中i>n时算法搜索叶节点新+数数相符号三角形前已找符号三角形数sum增1
I
解判断n*(n+1)2奇数

43 源代码
#include
using namespace std

class Triangle
{
friend int Compute(int)
private
void Backtrack(int i)
int n
half
count
**p
long sum
}

int Compute(int n)

int main()
{
for(int n1n<10n++)
{
cout< cout<<符号三角形< }
return 0
}

void TriangleBacktrack(int t)
{
if ((count>half)||(t*(t1)2count>half))
{
return
}

if (t>n)
{
sum++
}
else
{
for (int i0i<2i++)
{
p[1][t]i
count+i

for(int j2j {
p[j][tj+1]p[j1][tj+1]^p[j1][tj+2]
count+p[j][tj+1]
}
Backtrack(t+1)
for (int j2j {
countp[j][tj+1]
}
counti
}
}
}

int Compute(int n)
{
Triangle X
Xnn
Xcount0
Xsum0

Xhalfn*(n+1)2
if(Xhalf21)return 0
XhalfXhalf2

int**pnew int*[n+1]

for(int i0i {
p[i]new int[n+1]
}

for(int i0i {
for(int j0j {
p[i][j]0
}
}

Xpp
XBacktrack(1)
for(int i0i {
delete []p[i]
}
delete []p
p0
return Xsum
}






计算行性约束需O(n)时间坏情况 O(2^n)结点需计算行性约束解符号三角形问题回溯算法需计算时间 O(n2^n)


44 运行结果图



图42


第5章 圆排列问题
51 问题描述
定n等圆c1c2…cn现n圆排进矩形框中求圆矩形框底边相切圆排列问题求n圆排列中找出长度圆排列例n33圆半径分112时3圆长度圆排列图示长度 2+4[7] 杨金勇等 圆排列包装问题优解解析华侨学学报2013年2期P5862








图41



2+√4
52 问题分析
圆排列问题解空间棵排列树回溯法搜索排列树算法框架设开始时a[r1r2……rn]n元半径相应排列树a[1n]排列构成

解圆排列问题回溯算法中CirclePerm(na)返回找圆排列长度初始时数组a输入n圆半径计算结束返回相应优解圆排列


center计算圆前圆排列中横坐标x^2 sqrt((r1+r2)^2(r1r2)^2)推导出x 2*sqrt(r1*r2)
Compoute计算前圆排列长度变量min记录前圆排列长度数组r表示前圆排列数组x记录前圆排列中圆圆心横坐标

递算法Backtrack中i>n时算法搜索叶节点新圆排列方案时算法调Compute计算前圆排列长度适时更新前优值

i

53 源代码
#include
#include
using namespace std

float CirclePerm(int nfloat *a)

template
inline void Swap(Type &a Type &b)

int main()
{
float *a new float[4]
a[1] 1a[2] 1a[3] 2
cout<<圆排列中圆半径分：< for(int i1 i<4 i++)
{
cout< }
cout< cout<<圆排列长度：
cout< return 0
}

class Circle
{
friend float CirclePerm(intfloat *)
private
float Center(int t)
void Compute()
void Backtrack(int t)

float min
*x
*r
int n
}

float CircleCenter(int t)
{
float temp0
for (int j1j {

float valuexx[j]+20*sqrt(r[t]*r[j])
if (valuex>temp)
{
tempvaluex
}
}
return temp
}

void CircleCompute(void)
{
float low0high0
for (int i1i {
if (x[i]r[i] {
lowx[i]r[i]
}

if (x[i]+r[i]>high)
{
highx[i]+r[i]
}
}
if (highlow {
minhighlow
}
}

void CircleBacktrack(int t)
{
if (t>n)
{
Compute()
}
else
{
for (int j t j < n j++)
{
Swap(r[t] r[j])
float centerxCenter(t)
if (centerx+r[t]+r[1] {
x[t]centerx
Backtrack(t+1)
}
Swap(r[t] r[j])
}
}
}

float CirclePerm(int nfloat *a)
{
Circle X
Xn n
Xr a
Xmin 100000
float *x new float[n+1]
Xx x
XBacktrack(1)
delete []x
return Xmin
}

template
inline void Swap(Type &a Type &b)
{
Type tempa
ab
btemp}
54 运行结果图




图51




结
三实例编程中总算法思想利回溯法求解问题第选图着色问题NP问题涉图邻接顶点访问图便利图储存结构选择邻接矩阵形式遍历图式时第顶点开始次顶点数组中完成顶点遍历保证全部顶点访问着色着色动态程遍历程中完成着色次访问结点先赋值第种颜色果接点颜色重复顶点着色否顶点颜色转化种直够完成赋值
程序编写身难思路清晰赋值较间回循环较困难通三实例练中回溯算法更进步理解回溯法解框架更清楚方面认识足通三编程收获需更加深入学算法说明回溯法种通性高算法模型回溯法面棵空间搜索树课树已完成实际问题数学表达建模棵树特性相致算法具高度致性角度旦掌握回溯法起较简单回溯法值学算法
问题解空间通常搜索问题解程中动态产生回溯重特性
实回溯法根思想条路前走进进进退回换条路试遇某类问题时问题分解出明确动态规划递解法时考虑回溯法解决类问题回溯法优点程序结构明确读性强易理解通问题分析提高运行效率出明显递推公式迭代求解问题回溯法花费时间较长
回溯法求解问题首先问题进行适转化出状态空间树棵树条完整路径代表种解通深度优先搜索棵树枚举种解情况出结果回溯法中通构造约束函数提升程序效率深度优先搜索程中断解（定完整事实构造约束函数意义）约束函数进行删解样必继续解剩余部分列出节省部分时间
参考文献
文档香网(httpswwwxiangdangnet)户传

《香当网》用户分享的内容，不代表《香当网》观点或立场，请自行判断内容的真实性和可靠性！
该内容是文档的文本内容，更好的格式请下载文档