注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

TOTO

Think and Be Different

 
 
 

日志

 
 

一个问题的想法  

2007-06-27 17:26:58|  分类: 默认分类 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
发信人: Curvelet (小曲线), 信区: Algorithm
标  题: 问个题...
发信站: 水木社区 (Mon Jun 25 13:15:04 2007), 站内

数组 A 中有 N 个无符号整数(假定是 64 bit 吧),

给定无符号整数 a,
在数组 A 中找一个元素 x,
使得 a 跟 x 的海明距离小于等于常数 c。

补充点信息:可以假定 c = 8。

海明距离的定义是,
两个数的二进制表示中对应位不同的个数,
或者说 x 和 y 的海明距离是 x 跟 y 异或运算后二进制位上 1 的个数。

这个问题,版上那些牛人最后的得出的解法如下:
现在假定C=4,
可以生成和a的海明距离为4,数组中,形成它们距离他们各自元素的海明距离为4的书,
那么通过对两个集合的hash查找,如果有公共元素,那么肯定可以有这个数,否则可能没有,必须再确认一下!

我查了一下,发现格雷码有个非常有趣的性质:任意两个整数的差是这两个整数所对应的格雷码之间的海明距离,这样将数全部转化成格雷码,这样可以有很好的
方法,只要将原来数组排序,按照二分查找的方法来找,那么这个问题很容易解决!





一个问题的想法 - Ryan - TOTO



TOTO  
查看个人资料
 更多选项 6月27日, 下午5时06分
发件人:TOTO <sand...@gmail.com>

下面有个家伙写了篇很好的文章讲的就是格雷码:
http://www.vckbase.com/document/viewdoc/?id=1305
拜一下!

采用二进制编码方法所构成的个体基因型是一个二进制编码符号串。

其编码长度与问题所要求的求解精度有关。

设某一参数的取值范围是 ,我们用长度为 的二进制编码符号串来表示该参数,则它总共能够产生 种不同的编码,若使参数编码时的对应关系如下:

二进制编码不便于反映所求问题的结构特征,对于一些连续函数的优化问题等,也由于遗传运算的随机特性而使得其局部搜索能力较差。为改进这个特性,人们提
出用格雷码(gray code)来对个体进行编码。

格雷码是这样一种编码方法,其连续的两个整数所对应的编码值之间仅仅只有一个码位不同,其余码位完全相同。见下表

假设一个二进制编码为 ,其对应的格雷码为 ,由二进制编码到格雷码的转换公式为:

(1)

由格雷码到二进制码的转换公式为:

(2)

其中 表示异或运算符。

采用格雷码编码的过程是:首先将10进制数编码为二进制数,再由式(1)转化为格雷码,在解码时,先由式(2)将格雷码转换为二进制数,在由二进制数得
到十进制数。

格雷码有这样一个特点:任意两个整数的差是这两个整数所对应的格雷码之间的海明距离。这个特点是遗传算法中使用格雷码来进行个体编码的主要原因。

遗传算法的缺点:局部搜索能力不强,引起该问题的主要原因是,新一代群体的产生主要是依靠上一代群体之间的随机交叉重组完成的,所以即使已经搜索到最优
解附近,而想要达到这个最优解,却要费一番功夫,甚至需要花费较大的代价。对于用二进制编码方法表示的个体,个体表现型X的微小变化,基因型却需要进行
经过大量变化才能得到。

但是,若使用格雷码来对个体进行编码,则编码串之间的一位差异,对应的参数值也只是微小的差别。这样就相当于增前了遗传算法的局部搜索能力,便于对连续
函数进行局部空间搜索。

例如,对于区间 中两个临近的整数 和 ,若使用长度为10位的二进制编码,它们可分别表示为:

而使用同样长度的格雷码,他们可以分别表示为:

显然,对于相邻的十进制整数,使用格雷码时,两个编码串之间只有一位编码值不同;而使用二进制编码时,两个编码串之间却相差较大。

格雷码编码方法是二进制编码方法的一种变形,其编码精度与相同长度的二进制编码的精度相同。

格雷编码方法的主要优点是:

(1)       便于提高遗传算法的局部搜索能力

(2)       交叉、变异等遗传操作便于实现。

(3)       复合最小字符编码原则。

(4)       便于利用模式定理对算法进行理论分析。
*********************************************************************************

  评论这张
 
阅读(333)| 评论(1)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017