背包问题的一种自适应算法

背包问题是经典的NP-hard组合优化问题之一，由于其难解性，该问题在信息密码学和数论研究中具有极重要的应用．基于求解背包问题著名的二表算法和动态二表算法，利用归并原理和4个非平衡的子表，提出一种求解该问题的自适应算法，算法可根据计算资源和问题实例规模的大小，允许使用O(2^n/2-ε)的存储空间(1≤ε≤n／4)，在O(ε(2^n/2))的时间内求解背包问题．对算法性能的理论分析和数值实验结果表明，自适应算法可显著扩大背包实例的求解规模，从时间和空间上改进背包问题现有算法的性能．     

背包问题无存储冲突的并行三表算法

背包问题属于经典的NP难问题，在信息密码学和数论等研究中具有极重要的应用，将求解背包问题著名的二表算法的设计思想应用于三表搜索中，利用分治策略和无存储冲突的最优归并算法，提出一种基于EREW-SIMD共享存储模型的并行三表算法，算法使用O（2^n/4）个处理机单元和O（2^3n/8）的共享存储空间，在O（2^3n/8）时间内求解n维背包问题．将提出的算法与已有文献结论进行的对比分析表明：文中算法明显改进了现有文献的研究结果，是一种可在小于O（2^n/2）的硬件资源上，以小于O（2n/2）的计算时问求解背包问题的无存储冲突并行算法。     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2n/8)的处理机在O(27n/16)的时间和O(213n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(25n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

一种求解背包问题的自适应算法

针对二表算法和动态二表算法求解背包问题,提出一个并行自适应算法,能用 个处理机、 的时间、 的空间求解背包问题 ,根据处理机的数目以及存储器的容量来选择参数,充分利用已有的硬件资源,以求得最快的求解速度。实验结果证明了该算法的有效性。     

基于分治的背包问题DNA计算机算法

如何减少DNA计算机在求解大型难解问题中以问题输入纯指数增长的DNA链数,已成为DNA计算机研究的重要内容.将分治策略应用于背包问题的DNA分子计算中,提出一种求解背包问题的新的DNA计算机算法.算法由n位并行减法器、n位数据搜索器和其他4个子算法组成.算法的DNA链数可达到亚指数的O(2q/2),其中q为背包问题的维数.与最近文献结论进行的对比分析表明:算法将求解背包问题所需的DNA链数从O(2q)减少至O(2q/2),最大链长度减少为原来的1/2,因此,理论上新算法在试管级水平上能将可破解的背包公钥的维数从60提高到120.     

求解背包问题的演化算法

背包问题(Knapsack Problem, KP)是一类著名的组合优化问题,也是一类NP难问题,它包括0-1背包问题、有界背包问题、多维背包问题、多背包问题、多选择背包问题、二次背包问题、动态背包问题和折扣背包问题等多种形式,在众多领域有着广泛的应用.演化算法(EAs)是一类有效的快速近似求解KP的算法.本文对近十余年来利用EAs求解KP的研究情况进行一个较为详细的总结,它一方面讨论了利用EAs求解各种KP问题时个体的编码方法与处理不可行解的有效方法,另一方面为今后进一步利用最新提出的EAs求解KP问题提供一个可借鉴的思路.     

背包类问题的并行O(25n/6)时间-空间-处理机折衷

将串行动态二表算法应用于并行三表算法的设计中,提出一种求解背包、精确的可满足性和集覆盖等背包类NP完全问题的并行三表六子表算法.基于EREW-PRAM模型,该算法可使用O(2^n/8)的处理机在O(2^7n/16)的时间和O(2^13n/48)的空间求解n维背包类问题,其时间-空间-处理机折衷为O(2^5n/6).与现有文献的性能对比分析表明,该算法极大地提高了并行求解背包类问题的时间-空间-处理机折衷性能.由于该算法能够破解更高维数的背包类公钥和数字水印系统,其结论在密钥分析领域具有一定的理论和实际意义.     

蚁群算法求解多维0／1背包问题

0／1背包问题是一类典型的组合优化问题，并且是NP-完全的问题，研究它具有很重要的意义。本文针对多维0／1背包问题的特点，设计了二进制编码的有向图，使得蚁群算法可以应用到背包问题上。仿真结果表明，该蚁群算法在求解多维0／1背包问题上的是相当出色的。     

背包问题的量子计算算法

背包问题属于NP完全问题,经典算法对规模为n的背包问题求解的时间复杂度为O（n²）。给出了基于固定相位的背包问题量子计算算法,证明了该算法在多解的情况下,能够以不低于98%的成功率在O（√N/M）步完成对规模为n的背包问题求解（M是解的数目）,而基于原始Grover算法的背包问题量子计算算法计算复杂度为O（√N/M）,成功率是50%～100%。     

求解广义背包问题的贪心DS_BPSO算法

首先针对演化算法求解背包问题定义了贪心变换的概念,并给出了该变换的一种有效实现算法;然后将此算法与文献[5]中提出的具有双重结构编码的二进制粒子群优化算法(DS_BPSO)相结合,提出了一种解决广义背包问题GKP(General Knapsack Problem)的快速算法:基于贪心变换的DS_BPSO算法(GDS_BPSO).利用该算法求解文献[3,6]中的著名背包实例,给出了该背包实例的目前最好结果.此外,对于随机生成的大规模背包实例,通过与文献[3]中的HGA算法对比计算表明:GDS_BPSO算法是求解广义背包问题的一种高效方法.     

基于0/1背包问题的算法探究

0／1背包问题是计算机科学中的一个经典问题。动态规划法，递归法，回溯法是求解该问题的三种典型方法，使用这三种方法求解0／1背包问题，并对各算法进行了理论分析。用不同规模的0／1背包问题对三种算法进行测试，比较它们的运行时间，发现测试结果与其理论分析结果相符．最后指出就求解不同规模的0／1背包问题而言各算法的优劣。     

求解旅行商问题的近似多项式算法

旅行商(TSP)问题是一个典型的组合优化问题,易于描述却难于求解.对于大规模TSP问题,目前仍没有非常有效的方法.针对弹性网络算法在求解旅行商问题中时间性能方面的不足,提出了一种快速的求解算法.在弹性网络算法基础上,提出了求解旅行商问题的扩张方法和收缩方法,它们时间复杂性低于O(N3),经过比较扩张方法的效果比较理想.在扩张方法的基础上,提出随机扩张方法和完全扩张方法,完全扩张方法的时间复杂性低于O(N4),仍然是一个多项式算法.实例表明,完全扩张方法是一个快速且有效的算法.     

多维背包问题的一个蚁群优化算法

蚁群优化(ACO)是一种通用的启发式方法,已被用来求解很多离散优化问题.近年来,已提出几个ACO算法求解多维背包问题(MKP).这些算法虽然能获得较好的解但也耗用太多的CPU时间.为了降低用ACO求解MKP的复杂性,文章基于一种已提出但未实现过的MKP的信息素表示定义了新的选择概率的规则和相应的基于背包项的一种序的启发式信息,从而提出了一种计算复杂性较低、求解性能较好的改进型蚁群算法.实验结果表明,无论串行执行还是虚拟并行执行,在计算相同任务时,新算法耗用时间少且解的价值更高.不仅如此,在实验中,文中的新算法获得了ORLIB中测试算例5.250-22的两个"新"解.     

演化算法求解近似最大匹配问题的时间复杂性分析

虽然演化算法已经广泛地被用于求解不同的组合优化问题，但是对于其时间复杂性目前仍然了解得比较少。最近，在这方面有了一些初步的研究，然而迄今的结果大多局限于讨论一些简单的演化算法(如(1 1)类型的演化策略)和人造的模型问题(如二进制类型的示例问题)，很少涉及到使用种群、杂交操作演化算法和传统的组合优化问题。因此，理论上需要分析演化算法，求解一些典型的组合优化问题的时间复杂性。     

基于质粒分子数子集O（1．414^n）DNA计算机算法

文章提出了一种求解背包问题的新的基于质粒DNA计算机算法.本算法的DNA链数可达到亚指数的O(1.414n),其中n为背包问题的维数.将提出的算法与已有文献结论进行的时比分析表明:本算法将穷举算法中所需的DNA链数从O(2n)减少至O(1.414n),因此利用本DNA计算机算法在试管级水平上能将可破解的背包公钥的维数从60提高到120,显示出了一定的优越性.     

二重结构编码遗传算法及其在贷款组合优化决策中的应用

对于综合考虑贷款收益和风险的贷款组合配给决策模型 ,算法上是一类背包问题 ,但它有其特殊性 .采用二重结构编码的遗传算法 ,结合贪心算法和局部搜索算法 ,可以提高这类问题求解的效率 ,并在运算时间和解的精度上取得较好的平衡 .     

高效求解三维装箱问题的剩余空间最优化算法

为实现三维装箱问题的高效求解，提出了一个三维的剩余空间最优化算法（Three-Dimensional Residual-Space-Optimized Algorithm，3D-RSO）。在满足3个著名约束的条件下，该算法将三维问题转化为带有高度约束的二维问题，通过对箱子放置后的剩余空间状态分析，提出了基于概率较优的空间分割方法和箱子布置规则。相比于传统算法，3D-RSO在求解过程中不需要任何的预处理和搜索操作，是一种最坏计算复杂度为[O(2n2)]的直接求解算法。针对强异构体的实验表明，该算法能够在极短的时间内对算例进行高效求解，适合应用在大规模或者需要被快速求解的三维装箱问题中。     

基于离散微粒群算法求解背包问题研究

微粒群算法(PSO)是一种新的演化算法,主要用于求解数值优化问题.基于离散微粒群算法(DPSO)分别与处理约束问题的罚函数法和贪心变换方法相结合,提出了求解背包问题的两个算法:基于罚函数策略的离散微粒群算法(PFDPSO)和基于贪心变换策略的离散微粒群算法(GDPSO).通过将这两个算法与文献[7]中的混合微粒群算法(Hybrid_PSO)进行数值计算比较发现:对于求解大规模的背包问题,GDPSO非常优秀,其求解能力优于Hybrid_PSO和PFDPSO,是求解背包问题的一种非常有效的方法.     

一种基于预处理技术的约束满足问题求解算法

相容性技术作为约束满足问题的一种有效求解技术,不论是在求解前的预处理过程中,还是在搜索过程中,都扮演着极为重要的角色.文中对预处理阶段的相容性技术进行改进和信息抽取,提出两种应用于搜索过程中的新算法Pre-AC和Pre-AC*,并嵌入到BT框架中,形成新的搜索算法BT MPAC和BT MPAC*,给出了其正确性证明,通过复杂性分析得到Pre-AC和Pre-AC*的时间复杂度分别是O(nd)和O(ed2),明显低于目前最流行的弧相容技术的时间复杂度O(ed3).实验测试结果表明:对于不同类别的用例,新算法的执行效率是弧相容维护算法的2~50倍.     

一种求解背包问题的混合遗传微粒群算法

背包问题是计算科学理论中一个著名的NP-hard问题,也是典型的组合优化问题,在物流系统的库存分配和货物装载等方面都有非常重要的应用.采用借鉴遗传算法的编码、交叉和变异的遗传微粒群算法对背包问题进行求解.为了增强遗传微粒群算法的搜索性能,将基于自学习规则的启发式算法与遗传微粒群算法相结合得到混合遗传算法用于求解背包问题.对多个标准测试实例的仿真计算表明,该算法能有效求解KP问题.