检索结果-内蒙古大学图书馆

软件学报 2016年第11期27卷 2712-2724页

作者：王晓峰许道云北方民族大学计算机科学系宁夏银川750021 贵州大学计算机科学系贵州贵阳550025

置信传播算法求解RB(k,n,a,r_c,p)模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础... 详细信息

置信传播算法求解RB(k,n,a,r_c,p)模型实例时非常有效,几乎能够有效求解接近可满足性相变点的难解实例.然而,因子图带有回路的实例,置信传播算法不总有效,常表现为不收敛.对于这种现象,至今缺少系统的理论解释.置信传播算法是最为基础的信息传播算法,对置信传播算法的收敛性分析是其他信息传播算法收敛性分析的重要基础.在RB(k,n,a,rc,p)模型中,取k=2,a>1/k,r_c>0均为常数,且满足ke^(-a/r_c)≥1.证明了如果p∈(0,n^(-2a)),则置信传播算法在RB(k,n,a,r_c,p)模型产生的随机实例集上高概率收敛.最后,在RB(k,n,a,r_c,p)模型上选取了几组不同的数据进行数值模拟,实验结果表明该结论有效.当问题规模n增大时,在RB(k,n,a,r_c,p)模型的可满足区域,实验收敛区间趋于一个固定范围,而理论收敛区间逐渐变窄.原因在于,RB(k,n,a,r_c,p)模型是一个具有增长定义域的随机CSP实例产生模型,不协调赋值的数目与参数p及问题规模n有关.

关键词：置信传播算法收敛性约束可满足性问题 RB模型

来源：评论

学校读者我要写书评

暂无评论

基于置信传播算法的低密度校验码量化译码设计

引用

计算机学报 2003年第8期26卷 934-939页

作者：贺玉成慕建君王新梅西安电子科技大学综合业务网国家重点实验室西安710071

介绍了二元输入连续输出无记忆AWGN信道下低密度校验 (LDPC)码的置信传播译码算法及其密度进化特性 .根据密度进化规律 ,分析了不同消息空间中的量化译码问题 .得出结论如下 :对于概率和概率差消息 ,只有高阶均匀量化才能获得满意的译... 详细信息

介绍了二元输入连续输出无记忆AWGN信道下低密度校验 (LDPC)码的置信传播译码算法及其密度进化特性 .根据密度进化规律 ,分析了不同消息空间中的量化译码问题 .得出结论如下 :对于概率和概率差消息 ,只有高阶均匀量化才能获得满意的译码性能 ;似然比消息的适当对数量化可等价于对数似然比消息的均匀量化 ;对数似然比消息易于实现相对信道输入± 1的无偏对称量化 ,并有效利用消息的统计特性 .由非均匀量化在大消息区域分配的量化电平可以有效地促进算法收敛 .仿真结果表明。

关键词：人工智能置信传播算法低密度校验码量化译码设计概率推理算法

来源：评论

学校读者我要写书评

暂无评论

置信传播算法在社交网络影响力问题的应用研究

置信传播算法在社交网络影响力问题的应用研究

引用

作者：冯琬晶北方民族大学

学位级别：硕士

社交网络的出现推动了信息传递方式的变革,基于社交网络产生一种低成本高收益的营销模式——“病毒营销”。病毒营销根据口碑传播的原理,使信息在网络中快速扩散。病毒营销的基本思想是选取少部分受众群体去影响网络中其他用户,达到被... 详细信息

社交网络的出现推动了信息传递方式的变革,基于社交网络产生一种低成本高收益的营销模式——“病毒营销”。病毒营销根据口碑传播的原理,使信息在网络中快速扩散。病毒营销的基本思想是选取少部分受众群体去影响网络中其他用户,达到被影响用户范围最大化的目的。关键在于选择哪些用户作为传播源,这个问题实质上是社交网络影响力最大化问题。该问题在人工智能等领域具有很高的应用价值,然而求解较为困难。置信传播算法是一种基于因子图的近似算法,当算法收敛后,因子图中每条边上的信息都会趋于稳定,利用这些信息可以高概率固定某些变元的取值,从而使问题简化。社交网络影响力最大化问题本质是寻找影响力最大的节点,因此本文探索利用置信传播算法求解社交网络影响力最大化问题,具体地讲,有如下创新点:(1)社交网络中部分用户之间联系趋于紧密,在社交网络中会形成各种社区结构,利用社交网络的社区性质对社交网络影响力最大化问题求解。把社交网络划分为多个社区,依据网络中用户与社区之间的关系将社交网络映射为因子图。(2)提出一种混合算法求解社交网络影响力最大化问题。将节点的影响力因素加入置信传播方程,用改进后的置信传播算法在因子图模型上进行信息传递,从而求出影响力最大的候选种子集合,最后使用贪心算法求解出影响力最大的种子集合。

关键词：影响力最大化置信传播算法因子图

来源：评论

学校读者我要写书评

暂无评论

置信传播算法在最小费用流问题上的研究

置信传播算法在最小费用流问题上的研究

引用

作者：王雅静太原理工大学

学位级别：硕士

本文主要探究置信传播算法在带平方项的最小费用流问题上的求解.具体来讲,有如下研究内容:(1)当指派问题中工作数量大于工人数量时,在进行分配时可能导致分配不均甚至出现个别人过多或过少现象,针对此问题,我们利用最小费用流问题与指... 详细信息

本文主要探究置信传播算法在带平方项的最小费用流问题上的求解.具体来讲,有如下研究内容:(1)当指派问题中工作数量大于工人数量时,在进行分配时可能导致分配不均甚至出现个别人过多或过少现象,针对此问题,我们利用最小费用流问题与指派问题之间的关系,考虑分配公平条件,将此类指派问题转化为带平方项的最小费用流问题并将其映射为因子优化问题进行求解,并提出求解此类带平方项的最小费用流问题的置信传播算法.(2)证明置信传播算法在此类带平方项的最小费用流问题上的收敛性.在问题有唯一最优解的前提下,首先将问题的图模型转化为因子图模型,接着引入计算树概念,根据计算树图模型上问题与原问题的联系,利用反证法在计算树图模型上通过改变流量构造新的可行解使之矛盾,得证在有限次迭代后问题收敛到最优解,并从完全二部图推广到一般图,这与大多数研究只考虑线性规划存在区别.此外,进一步总结出问题收敛的充分条件.(3)分析置信传播算法在带平方项的最小费用流问题上的运行时间.针对整数型该问题,通过分段线性凸函数界定二次项函数的方法,利用线性函数已有的运算时间性质逼近带平方项的最小费用流问题上的运行时间,为置信传播算法在非线性问题提供一种新的思路.

关键词：置信传播算法不平衡指派问题最小费用流问题因子图

来源：评论

学校读者我要写书评

暂无评论

一种求解0-1背包问题的置信传播算法

引用

郑州大学学报（理学版） 2021年第1期53卷 29-34页

作者：张丹丹王晓峰冯琬晶左逢源北方民族大学计算机科学与工程学院宁夏银川750021 宁夏智能信息与大数据处理重点实验室宁夏银川750021

针对启发式算法在求解0-1背包问题时易陷入局部最优以及寻优精度低等不足,提出一种求解0-1背包问题的置信传播算法。根据0-1背包问题的线性规划,构造该问题的因子图模型,并基于该模型的特点设计对应的标识函数,进而设计一种求解0-1背包... 详细信息

针对启发式算法在求解0-1背包问题时易陷入局部最优以及寻优精度低等不足,提出一种求解0-1背包问题的置信传播算法。根据0-1背包问题的线性规划,构造该问题的因子图模型,并基于该模型的特点设计对应的标识函数,进而设计一种求解0-1背包问题的置信传播算法。当算法收敛时,计算每个物体节点的置信度,以确定该物体的装包概率,从而高概率地给出0-1背包问题的解。与其他启发式算法进行了比较,结果表明,该算法具有较好的全局搜索能力。

关键词： 0-1背包问题线性规划因子图置信传播算法

来源：评论

学校读者我要写书评

暂无评论

极化码置信传播算法早期终止准则的研究

引用

信号处理 2016年第3期32卷 253-259页

作者：邢超赵生妹郑宝玉南京邮电大学信号处理与传输研究院江苏南京210003 河南工业大学信息科学与工程学院河南郑州450001

适用于极化码置信传播(Belief-Propagation,BP)算法的早期终止准则研究具有实际意义。本文提出将循环冗余校验(Cyclic Redundancy Check,CRC)作为极化码BP算法的早期终止准则(简称为BP-CRC),当BP算法迭代次数大于门限后,如果信源估计值... 详细信息

适用于极化码置信传播(Belief-Propagation,BP)算法的早期终止准则研究具有实际意义。本文提出将循环冗余校验(Cyclic Redundancy Check,CRC)作为极化码BP算法的早期终止准则(简称为BP-CRC),当BP算法迭代次数大于门限后,如果信源估计值符合CRC校验,提前终止迭代;否则,就按固定迭代次数执行完BP算法。(1024,512)极化码通过二进制输入高斯白噪声信道后,提出的BP-CRC与基于生成矩阵G的早期终止准则(简称为BP-Gmatrix)做对比。仿真结果表明:在译码性能上,BP-CRC与原始BP算法基本一致;在平均迭代次数减少的效果上,和BP-Gmatrix一致;随着信噪比的增大,两者平均迭代次数减少的次数更明显。CRC比生成矩阵G检测的计算复杂度更低。平均迭代次数的减低,可以有效降低BP译码器的时延和能耗。因此,CRC是有效的低能耗和低复杂度的极化码BP算法早期终止准则。

关键词：极化码置信传播算法早期终止准则循环冗余校验

来源：评论

学校读者我要写书评

暂无评论

LDPC译码中的消息传递算法和置信传播算法等效性的证明

引用

应用科学学报 2005年第2期23卷 218-220页

作者：杜鹏毕光国东南大学移动通信国家重点实验室江苏南京210096

给出了LDPC译码中三种算法:硬判决算法、消息传递算法以及置信传播算法的详细步骤,证明了消息传递算法和置信传播算法的等效性,得出了消息传递算法是置信传播算法对数域的实现方法.

关键词：置信传播算法消息传递 LDPC 等效性证明译码硬判决对数域

来源：评论

学校读者我要写书评

暂无评论

一种用于立体图像匹配的改进置信传播算法

引用

中国图象图形学报 2009年第11期14卷 2383-2386页

作者：严恺周军上海交通大学图像通信与信息处理研究所上海200240 上海市数字媒体处理与传输重点实验室上海200240

给出了一种用于立体图像匹配的改进置信传播算法。基于视差场的连续性假设。传统视差估计置信传播算法将稠密视差场抽象为一种马尔可夫场,置信传播在消息双向传递的马尔可夫网络上进行。考虑到在物体遮挡区域视差场并不连续,首先采用基... 详细信息

给出了一种用于立体图像匹配的改进置信传播算法。基于视差场的连续性假设。传统视差估计置信传播算法将稠密视差场抽象为一种马尔可夫场,置信传播在消息双向传递的马尔可夫网络上进行。考虑到在物体遮挡区域视差场并不连续,首先采用基于初始视差估计的交叉不稳定检测技术检测出遮挡区域,将稠密视差场更加精确地抽象为一种马尔可夫场和贝叶斯场的混合场,置信传播在马尔可夫和贝叶斯的混合网络上进行,使得遮挡区域像素视差信息不传递给非遮挡区域,提高了视差估计精度并降低了算法复杂度。采用Middlebury网站提供的标准测试图像对本文算法进行了客观评估,实验结果表明,本文算法同时具有较好的视差估计精度和运算效率。

关键词：立体图像匹配置信传播算法马尔可夫场交叉不稳定检测技术

来源：评论

学校读者我要写书评

暂无评论

一种求解最小支配集问题的置信传播算法

引用

计算机仿真 2022年第12期39卷 387-391,397页

作者：刘子琳王晓峰芦磊程亚南北方民族大学计算机科学与工程学院宁夏银川750021 北方民族大学图像图形智能处理国家民委重点实验室宁夏银川750021

最小支配集问题(MDS)是图论中的一个重要问题,在网络资源配置中有广泛的应用。上述问题是一个NP难问题,传统的启发式算法求解最小支配集问题时速度慢,且易于陷入局部最优解。将上述问题原有的无向图转化为对应的因子图,基于因子图构建... 详细信息

最小支配集问题(MDS)是图论中的一个重要问题,在网络资源配置中有广泛的应用。上述问题是一个NP难问题,传统的启发式算法求解最小支配集问题时速度慢,且易于陷入局部最优解。将上述问题原有的无向图转化为对应的因子图,基于因子图构建最小支配集问题的线性规划方程,将方程代入图模型(GM)中,设计了一种求解最小支配集问题的置信传播算法。当算法收敛时,获得每个节点取值的边缘概率,利用边缘概率高概率地决定最小支配集节点。在随机生成的无向图上进行数值实验,结果表明,算法有效。

关键词：最小支配集集合覆盖置信传播算法因子图线性规划

来源：评论

学校读者我要写书评

暂无评论

求解多文字可满足SAT问题的置信传播算法

引用

计算机应用研究 2021年第9期38卷 2710-2715页

作者：芦磊王晓峰牛鹏飞刘子琳北方民族大学计算机科学与工程学院银川750021 北方民族大学图像图形智能处理国家民委重点实验室银川750021

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真。多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真。显然,此问题仍然是一个NP难问题。为了... 详细信息

可满足(SAT)问题是指:是否存在一组布尔变元赋值,使得合取范式公式中每个子句至少有一个文字为真。多文字可满足SAT问题是指:是否存在一组布尔变元赋值,使得CNF公式中每个子句至少有两个文字为真。显然,此问题仍然是一个NP难问题。为了研究解决多文字可满足SAT问题的算法,引入随机实例产生模型,设计求解多文字可满足SAT问题的置信传播算法。最后,用实例模型产生了大量数据进行实验验证,结果表明:该算法求解多文字可满足SAT问题的性能优于其他启发式算法。

关键词：多文字可满足置信传播算法 WalkSAT算法可满足问题

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：