android开发实战 Linxu磁盘 editor 微服务 分布式 scipy multithreading plugins vbscript xsd vue网站 vue图表 nginx教程视频 easyui视频 mysql在线测试 abaqus是什么软件 oracle连接字符串 matlab区分大小写吗 matlab不等于怎么表示 图片生成链接 php获取当天的0点时间戳 svn安装后右键不显示 python运算符优先级 搭建java环境 linux命令行大全 java游戏开发教程 tar文件怎么打开 万能低格工具 win10计算器下载 滑动门代码 京东钱包客户端 js验证码 拼多多商家下载 大数据之路 fastcgi jpg格式转换器 4k对齐是什么意思 lol无限视野 ps怎么修证件照 iphone组装机
当前位置: 首页 > 学习教程  > 编程语言

算法设计与分析之近似算法

2020/12/5 10:34:12 文章标签:

文章目录前言一、近似算法的基本思想二、近似算法的性能三、近似算法示例总结前言 大家好,越努力,越幸运,我是程序猿小猿。本篇文章小猿将跟您分享算法设计与分析中的近似算法,希望对您有所帮助。 一、近似算法的基本思想 1、放弃…

文章目录

  • 前言
  • 一、近似算法的基本思想
  • 二、近似算法的性能
  • 三、近似算法示例
  • 总结


前言

        大家好,越努力,越幸运,我是程序猿小猿。本篇文章小猿将跟您分享算法设计与分析中的近似算法,希望对您有所帮助。

在这里插入图片描述

一、近似算法的基本思想

1、放弃求解最优解,用近似最优解代替最优解,以此换取:
        (1)、算法设计上的简化
        (2)、时间复杂性的降低
2、近似算法是可行的
        (1)、问题的输入数据是近似的;
        (2)、问题的解允许有–定程度的误差;
        (3)、近似算法可在很短的时间内得到问题的近似解。

二、近似算法的性能

1、衡量近似算法性能的标准:
        (1)、时间复杂性必须是多项式阶的。这是近似算法的基本目标。
        (2)、解的近似程度。这是近似算法的重要目标。

2、若一个最优化问题的最优值为c*,求解该问题的一个近似算法求得的近似最优值为c,则将该近似算法的近似比定义为

在这里插入图片描述

3、在通常情况下,该性能比是问题输入规模n的一个函数ρ(n),即
在这里插入图片描述
4、近似算法的相对误差λ定义为:

在这里插入图片描述
        λ表示一个近似最优解与最优解相差的程度。

        若问题的输入规模为n,存在一个函数ε(n), 使得:

在这里插入图片描述
        ε(n)称为近似算法的相对误差界。且有:

在这里插入图片描述
通过近似比和相对误差这两个标准评价一个近似算法的优劣!

三、近似算法示例

1、顶点覆盖问题
2、TSP问题
3、装箱问题

总结

知识点总结
1、近似算法放弃求最优解,用近似解代替最优解,以换取算法设计上的简化和时间复杂性的降低。
2、近似算法通常采用两个标准来衡量性能:
        (1)、算法的时间复杂性
        (2)、解的近似程度
                近似比η
                相对误差λ
                相对误差界ε(n)

结语
        对近似算法的介绍就到这里啦,希望这篇文章能给予你一些帮助,感谢各位人才的:点赞、收藏和评论,我们下次见。

在这里插入图片描述


本文链接: http://www.dtmao.cc/news_show_450269.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?