与近似比固定算法的高性能算法

news/2024/7/7 15:35:57

    我不得不这样做研究,写论文。我喜欢用这个词来形容提到的高性能算法,感觉有点王婆卖瓜。当然,研究了算法的性能还是不错的,能是否是一个高性能的。自己不肯定的说。最近翻阅读Vazirani的《Approximate Algorithms》一本书。仔细重读他的前言。算法的一个定义。即高性能算法的解与最优解的误差仅仅有2%或5%。

2%的误差要求可能有点高,但5%应该还是不错的。假设以此为衡量,先前所做的算法少部分能达到这个要求。由于所做的算法大都在10%以内。但博士论文里的工作还是达到了5%的要求,主要是採用了改良的技术。

多说一句。为了提高2%,花费了无数的日日夜夜的调试与总结,没办法,启示式的方法都带有这个特征,非常多好的性质都是通过实验观察总结得到的。

    另外,先前研究看不上所谓的带有固定近似比的算法,由于大多数近似比都在2或3/2左右,甚至有的是O(logN),因而人为不值深入研究。看了Vaziranni的解释。自己深感惭愧和无知,事实上固定近似比的算法是值得研究的,详细的原因,能够看看Varizani怎样理解的。

    “对于寻找高性能算法的实践者来说,在最优解的因子2或者更坏的因子O(logn)以内的算法能有多好?更进一步,由此看来,近似保证的改进(比方从因子2到3/2)能实用到何种程度?

    我们讨论一下这两个问题并指出这些论断中的一些谬误。近似保证只反映算法关于大部分病态实例的性能。

也许把近似保证看成促使我们更深入地研究问题的组合结构并发现利用这个结构的更强有力工具的一种度量更合适。已经注意到当得到有更好保证的算法的时候,构造紧样例的困难性明显增大。实际上,对于一些今年来的算法,得到紧样例已经独立成为一篇论文。实验已证实这些算法和其他复杂算法对于典型事例能达到想要的2%到5%量级的误差界限。尽管它们最坏情形误差界限要高得多。另外,应将已被理论证明的算法看成核心算法思想,这个思想须要非常好地融入特定应用中所产生的事例。

    大师的见解入木三分。正所谓偏见比无知离真理更远,为自己曾经的偏见深感羞愧。事实上。固定近似比算法能让我们更好地认识和了解问题的结构和特点,这才是固定近似比算法的重要性。从自己的研究经历来看,基于固定近似比算法开发的一些算法实际效果也不错,最明显的就是并行机调度里面的WSPT算法。

    在做研究,您不能运行一路前行。有时我们需要停下来看看他们以前走过的路。

版权声明:本文博主原创文章。博客,未经同意不得转载。


http://www.niftyadmin.cn/n/2459960.html

相关文章

读《程序员生存定律》心得体会

原文链接:http://www.jianshu.com/p/8df220e6d67c 图片来自网络前言 在CSDN上偶然间看到这本李智勇前辈《程序员生存定律》,用了4天时间认真读完了。书中详细介绍了关于程序员的各种事情,并引经据典表达自己的看法。 无论是认真思考未来出路的…

Java: protobuf

*.proto 文件 syntax“proto3”; package nettytest; option java_outer_classname “SubscribeReqProto”; message SubscribeReq{ int32 subReqID 1; string userName 2; string productName 3; repeated string address 4; } C:\0000>protoc --java_out. Subscr…

go学习(一)——编译环境安装

CentOS下安装go语言编译环境 安装包下载地址为:https://golang.org/dl/。注:安装包下载地址为:https://golang.org/dl/ 如果打不开可以使用这个地址:https://golang.google.cn/dl/ 或者打开这个地址:https://studygola…

指针1

int main(){int a 4;int *p&a;int b *p;*p6;printf("%p %p %d %d %d",&a,p,b,*p,a);return 0; }int *p&a;就代表取a的地址 *p可以将它解地址,找出这个地址对应的元素 int main(){int arr[]{1,2,3,4,5};int *parr;printf("%p %p…

go学习(二)——基本数据类型和基本语法

在 Go 编程语言中,数据类型用于声明函数和变量。 数据类型的出现是为了把数据分成所需内存大小不同的数据,编程的时候需要用大数据的时候才需要申请大内存,就可以充分利用内存。 1.常见数据类型 Go 语言按类别有以下几种数据类型&#xff1…

JAVA:Protobuf3 对值为0 的int32将不进行序列化

JAVA:Protobuf3 对值为0 的int32将不进行序列化

指针作为函数

int main(){char *p,crr[]{h,e,l,l,o},*q;pcrr;qcrr5;while(p<q){printf("%c",*p);p;}return 0; }p q为两个指针p指向crr第一个元素的地址&#xff0c;q则指向最后一个位置&#xff0c;p<q即为p针在q的前面&#xff0c;那他就不断网后移动&#xff0c;每次移动…