算法实践与创新论文


    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-着色判定问题(面图画面边交叉图)图区域变成结点两区域相邻相应结点条边连接起
    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)户传

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

    下载文档到电脑,查找使用更方便

    文档的实际排版效果,会与网站的显示效果略有不同!!

    需要 10 香币 [ 分享文档获得香币 ]

    下载文档

    相关文档

    粒子群算法(优化算法)毕业设计论文

     毕 业 论 文 题 目 粒子群算法及其参数设置 专 业 信息与计算科学 班 级 ...

    5年前   
    1450    0

    基于视觉的车道线识别算法研究毕业论文

    毕业设计基于视觉的车道线识别算法研究Research on Algorithms of Vision-basedLane Recognition 2009 届 电气与电子工程 分...

    4年前   
    984    0

    毕业论文:TIPTOP双档算法设计与分析

    为了进一步完善现有的TIPTOP系统,针对工程部需求对企业设备进行有效登记管理,本人通过编写TIPTOP双档程序cfar222初步完成了对设备仪器的数据采集。在cfar281双档项目实施后,工程...

    5年前   
    1469    0

    首次适应算法最佳适应算法

    姓名:学号:实验名称:进程调度模拟实验 实验目的:了解动态分区存储管理方式中的数据结构和分配算法,加深对动态分区存储管理方式及其实现技术的理解。实验内容:#include<iostream.h...

    3年前   
    1603    0

    创新与制做小论文

    创新与制做小论文                  高一 911班 李亮 同学们,你是否也愿意动手呢?一起来吧!              一、液压千斤顶 看老师演示液压千斤顶的时候,...

    12年前   
    12777    0

    教育创新在路上论文

    教育创新在路上 在教育改革进程中,教育利益相关者增多,不同利益群体都在强烈地表达自身的利益诉求,价值取向也呈现出明显的多元化趋势,有的价值取向甚至是相悖的。教育决策的形成过程和教育改革举措...

    1年前   
    280    0

    基于内点法的电力系统最优潮流算法研究毕业论文

     本科毕业设计 题 目 基于内点法的电力系统最优潮流算法研究 XX大 学 毕 业 设 计(论文) 题目...

    5年前   
    2029    0

    最速下降法原理及其算法实现课程论文

     本科毕业论文(设计)模板 课程论文论文题目:最速下降法原理及其算法实现 课程名称: 现代信号处理新方法 学 院: ...

    3年前   
    774    0

    毕业实践论文

                                实习报告 2011年3月,我在**华忠维修服务有限公司进行维修实习。在来这一个多月的时间里,我对汽车维修服务站的、零部件供应、售后服...

    9年前   
    7604    0

    暑期实践论文

    “阳光总在风雨后,请相信有彩虹……” 在这个炎热的暑假,我们暂别象牙塔中舒适的生活,带着青年人特有的蓬勃朝气,走入社会,了解社会,深入社会。暑期社会实践活动一直是我校大学生投身社会、体验生...

    5年前   
    1078    0

    暑期实践论文

    暑期实践论文  作为新时代的大学生,社会实践是每一个人必须拥有的一段经历,它使我们在实践中了解社会、在实践中巩固知识;它是对每一位学生专业知识的一种检验,它让我们学到了很多在课堂上根本就学不到...

    9年前   
    501    0

    农村初中创新写作教学的探索与实践论文—井含祥

    农村初中创新写作教学的探索与实践论文—井含祥给学生习作注入“河水”——农村初中创新写作教学的探索与实践青海省湟中县丹麻初级中学井含祥发展与创新是时代赋予素质教育的中心任务和核心内容。作文教学是...

    8年前   
    488    0

    概率统计、算法

    1. 统计1. 如图是样本容量为200的频率分布直方图.根据此样本的频率分布直方图估计,样本数据落在[6,10)内的频数为_____ 642. 甲、乙两名同学在五次考试中数学成绩统计用茎叶图表...

    10年前   
    795    0

    教师教学创新与实践

        多点改变,多点偏爱,多点收获       --**城关中学  张** (B6  促进学生参与的教学情境创设的研究与实践)   关键词:创新   实践   新课程标准的...

    8年前   
    6416    0

    2017年创新论文格式最新

    创新论文格式最新  致谢  致谢对象限于对课题研究、学位论文完成等方面有较重要帮助的人员。  基本格式  标题  (1)一般分三级标题。具体要求如下:  一级标题:黑体,三号或16pt,段前、...

    6年前   
    405    0

    暑假社会实践论文

    暑假社会实践论文  社会,在实践中增长知识,锻炼自己的能力,更重要的是检验一下自己所学东西能否被社会所用,找出自己的不足之处,以便更好的取长补短,完成自己的学业。  “纸上得来终觉浅,绝知此事...

    11年前   
    627    0

    社会实践报告论文

    社会实践报告论文  今年暑假我来到东莞开达玩具厂进行社会实践,在实践期间我学习了许多,也感受颇深。  年少的我们都喜欢幻想,在高中的时候就幻想大学的是什么样子呢。那时也一样,还没放假就想像着打...

    9年前   
    466    0

    翻译实践报告论文

    大二的下学, 我的职责是俄语翻译,翻译一些资料。实习的目的是增加社会实践经验,迅速将翻译理论知识应用到实践当中,并加强使用计算机和翻译工具的能力。翻译实践的过程中,我总结了4种必备的翻译工具:...

    2个月前   
    82    0

    会计社会实践论文

    会计社会实践论文  转眼间暑假又过了,在这个暑假里开展了丰富多彩的暑期活动,本人在东莞东成发化工有限公司进行了社会实践学习,以下是本人此次学习的一些心得和体会。  这是我第一次到公司里做实习,...

    8年前   
    499    0

    化工社会实践论文

    化工社会实践论文  今年的暑假与往年不同,今年暑假虽然没有往年那样自由,舒适,往年在假期几乎全部时间都是上上网,看看电视,过着无忧无虑的生活。热了有空调,困了就躺下休息,而今年则恰好相反,大部...

    10年前   
    594    0

    文档贡献者

    文***享

    贡献于2020-09-08

    下载需要 10 香币 [香币充值 ]
    亲,您也可以通过 分享原创文档 来获得香币奖励!
    下载文档

    该用户的其他文档