求解组合拍卖问题的一种贪婪算法

为有效解决组合拍卖问题,从下模集函数最大值问题的基本结论出发,将部分穷举法与贪婪算法相结合,给出了一种求解组合拍卖问题的新算法一改进的贪婪算法,并从理论上证明了所给算法具有更好的性能保证.     

双背包约束下下模函数最大值的贪婪算法

给出求解双背包约束下非减下模集函数最大值的近似算法,证明了该算法的性能保证是1-e^2-1。该算法结合了部分穷举法与贪婪算法,是对贪婪算法的一种改进。算法的时间复杂性为O（n^4）。     

求解多背包约束下下模集函数最大值的近似算法及其性能保证

将部分穷举法与贪婪算法相结合,给出求解多背包约束下非减下模集函数最大值的近似算法．证明了该算法的性能保证是1-e^-1,算法的时间复杂性为O（3n^4）．     

一种求解下模集函数最大值问题的近似算法

下模集函数最大值问题属于NP-难问题,难以得到有效的求解方法。针对这一情况,运用概率分布方法,给出了求解该问题的一种近似算法,并证明算法的性能保证为1／3。组合优化问题实例证明了该算法的有效性。该研究可为求解下模集函数最大值问题提供新的思路。     

预算型最大覆盖问题的近似算法

研究了给定预算常数的最大覆盖问题,给出了求解此问题的改进贪婪算法,得到了性能保证为1-e-1的近似算法.     

求解下模集函数最大值问题的局部搜索算法

给出了求解具有简单约束的下模集函数最大值问题的一种局部搜索算法,并讨论了所给算法的性能保证.该算法的基本思想是:算法每次迭代总是在当前近似解集的邻域内,求出使目标函数取得最大的集合,将其作为新的近似解集.分析表明,所给算法是一种多项式时间近似算法.     

用遗传算法求解组合拍卖竞胜标

从电子商务中的组合拍卖机理出发,以第一价格密封拍卖方式为背景,通过分析组合拍卖标的集和竞胜标确定的复杂性,给出了组合拍卖竞胜标确定问题的一般模型,并指出了该问题为离散组合优化问题·然后通过引入智能算法的思想,在遗传算法中采用单亲遗传算子和嵌入优先适合启发式规则,设计了求解该模型的优先适合启发式单亲遗传算法·计算实例表明,利用该算法求解竞胜标确定问题的最优解,算法实现简单,计算效果良好,且不需要复杂的交叉和变异等操作·     

用改进遗传算法求解组合拍卖竞胜标

从电子商务中的组合拍卖机理出发,以第一价格密封拍卖方式为背景,通过分析组合拍卖标的集和竞胜标确定的复杂性,给出了组合拍卖竞胜标确定问题的一般模型,并指出了该问题为离散组合优化问题·同时针对拍卖实践中组合标出现的事实,对求解该模型的单亲遗传算法的初始种群进行优化设计,使得可行解的搜索空间大大缩小·基于这种思想,提出了一种适合求解该模型的改进遗传算法·计算实例表明,利用该算法求解竞胜标确定问题的最优解,算法具有实现简单、寻优速度快、计算效果良好等特点·     

退火贪婪混合遗传算法

提出了一种将贪婪算法和退火算法相结合的新型混合遗传算法,提高了算法的收敛速度,同时避免了遗传算法中存在早熟收敛的问题.     

容量受限工厂选址问题模型及贪婪蚁群算法求解

研究了在容量受限条件下的工厂选址问题.针对现有模型对覆盖问题、经济效益问题和发展状况问题考虑不足,提出了一种新的数学模型.由于容量受限的工厂选址是一个复杂的决策过程,较难得到满意解和最优解,提出一种新的改进蚁群算法对其进行求解.改进蚁群算法在传统蚁群算法的基础上结合了贪婪算法.仿真结果一方面说明了新的数学模型的有效性,另一方面证明了改进蚁群算法改善了传统蚁群算法易于陷入局部最优解的缺点,提高了寻优质量.     

最大化非减次模集函数问题的近似算法及其性能保证

次模集函数的最值问题在组合优化问题中有广泛应用,次模集函数的增减性对该问题的分析具有一定的简化作用．给出了求解非减次模集函数最大值问题的一种近似算法,并讨论了所给算法的性能保证．     

一种无线单频谱安全拍卖算法

由于电子拍卖自身的高效性和公正性,因此基于无线频谱分配的拍卖机制应运而生,且满足了人们日益增长的无线通信服务需求。而安全的频谱拍卖算法是保证无线频谱拍卖机制安全运行的重要保障。通过分析无线频谱分配的算法特点和其所确保的安全需求,提出了一种无线单频谱安全拍卖算法。该算法结合无线频谱分配的拍卖特点与密码学机制来确保拍卖过程中信息的安全,并正确选出拍卖赢家,以及计算出赢家所需要支付的频谱拍卖价格。分析证明了算法具有较高的安全性。     

图的正面影响控制集中贪婪算法的设计与分析

对于没有固定基础设施的无线传感器网络,设计一个优良合理的拓扑控制协议是关键.根据图的控制集在无线传感器网络组建虚拟骨干网的应用,研究了图上控制集问题的一个变形—正面影响控制集问题.针对图中是否存在孤立顶点,分两种情形讨论,设计了相应的贪婪算法,并分析了算法的性能比.     

网格中基于拍卖模型与遗传算法的作业分配

引入微观经济学与遗传工程知识,兼顾时限与成本,设计了一种网格中的作业分配方法.首先基于拍卖模型确定资源购买者和资源提供者之间的资源交易价格,然后使用遗传算法寻找作业分配最优方案.仿真结果表明,该方法是可行和有效的,不仅效用较高,而且作业对资源的分配较均衡,优于PRIMAL方法.     

贪心约简算法在HSV中的应用

本文研究了粗糙集理论中的属性约简问题。一般的约简算法和改进的约简算法都不能够得到一个令人满意的属性约简结果。为了找到具有较少属性的约简,文中提出了使用贪心约简算法,通过对接受过超选择性迷走神经切断术(HSV)治疗的具有11个属性的20个十二指肠溃疡病人构成的信息系统作近似分析,获取了一个与原决策表分类质量相同的仅含有5个属性的较小属性集。实验证明:用此方法能有效地去除冗余信息,对其症状进行约简提炼,从而获取简单而又能体现症状与病征的规则。     

树-串句法统计翻译模型的正向贪心解码算法

为了有效利用句法信息指导翻译过程,提出了基于贪心搜索的树-串句法统计翻译模型的正向解码算法.该算法以对数线性模型为整体框架,采用翻译模型概率、语言模型概率和空译文罚分作为特征函数.在解码过程中首先生成初始译文,然后通过遍历句法分析树反复迭代来改进译文.重点研究了解码过程中译文片断的打分方法.实验在IWSLT2004数据集上进行并采用BLEU方法评价翻译结果.实验结果表明正向贪心解码算法在翻译质量和速度上均好于现有的反向解码算法,这说明正向贪心解码算法能够更为有效地利用句法结构信息,更适合于树-串统计翻译模型.     

次模函数近似算法求最小弱顶点覆盖

求给定无向图的最小弱顶点覆盖是一个NP困难问题,只能通过研究此问题的近似算法来求解。本文从基本圈出发,定义了一个次模函数,利用次模函数理论来得到一个最小弱顶点覆盖问题的近似解,且近似度为1+ln(d-1),其中d为图的顶点最大度。     

顶点覆盖问题的贪心算法的设计与分析

设计了解顶点覆盖问题的贪心算法 ,并证明其相对比率 η≤H(d) ,d为图中最大的顶点度数 ,H(d) =∑1/ j(j =1,2 ,…… ,d) .当d ≤ 3时 ,解的精确度有明显改善 .