论文部分内容阅读
0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对0-1背包问题及其解法进行了分析,然后提出0-1背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。
0-1背包问题的两种扩展形式及其解法
【摘 要】
：
0-1背包问题是经典的NP-HARD组合优化问题之一,由于其难解性,该问题在信息密码学和数论研究中具有极其重要的应用。首先对0-1背包问题及其解法进行了分析,然后提出0-1背包问题的两种扩展形式,并给出了基于动态规划和贪心算法的两种有效算法来解决这两类问题。实验结果验证了所提出方法的有效性。
【机 构】
：
辽宁师范大学计算机与信息技术学院,中国科学院研究生院信息安全国家重点实验室
【出 处】
：
计算机应用研究
【发表日期】
：
2006年01期
其他文献
为尽量保留有价值的证据,并实现较大的数据缩减,设计了一种主动证据选取存储方法。根据IDS日志对安全事件进行分类,针对不同类型的安全事件选取并存储不同的网络数据作为证据存储,实现证据量与代价的折中。
提出了一种新的基于虚电路的可靠组播技术。首先分析了可靠组播的几个要素,然后介绍了基于虚电路的可靠组播机制,如资源预留、间隙整形、优先级策略等,最后设计了基于虚电路的组播模型。该模型结合多路径备份方法和特殊的重传机制,可以实现在某条链路出现故障的情况下迅速地恢复正常通信,大大地提高了组播的可靠性。
随着现代社会的不断发展与进步,我国信息化建设程度也越来越高,因此当下比较重要的一点就是保障信息通信网络的高效运行.而通信电源作为通信系统的'心脏',在保障通信
针对均值滤波对突变点敏感及传统自适应维纳滤波所取邻域的局限性,给出了一种新的电能质量检测去噪算法。该算法首先通过均值滤波去除噪声从而减小噪声在维纳滤波参数估计的影响;再对纳滤波结果进行阈值处理,从而提取突变点信息。实验结果表明,该算法不仅能去除大量的噪声而且能很好地保留突变点信息。
以某钢铁企业烧结过程,即烧结终点(Burning Though Point,BTP)优化控制系统为对象,针对当前控制软件存在开放性差、结构固定、可重用程度低的问题,提出一种多层分布式软件体系结构。在分析系统结构、接口和交互模式的基础上,给出系统开发的实施方案,从而建立了一个基于Windows DNS的开放的、有强交互能力和扩展能力的分布式BTP优化控制系统。
从控制的角度出发,提出了一种模型无关的无定标视觉伺服控制方法。在该方法中不需要机器人及摄像机模型,图像雅克比矩阵的计算采用最小二乘估计,机器人系统采用变结构的控制理论设计控制器;而后用李亚普诺夫方法对其进行了稳定性分析,结果证明系统能够渐近稳定。仿真实验证明了算法的有效性。
对机械产品协同设计的特点进行了分析,指出了目前这方面存在的问题,在此基础上介绍了基于网络面向并行工程的齿轮协同设计系统。讨论了系统的体系结构、框架模型、运行模式和系统实现,就系统涉及到的主要内容和主要关键技术进行了分析。
针对复杂电子装置及系统的故障诊断和自动测试,传统的测试仪器和自动测试系统已不能满足实际要求,下一代测试系统和综合仪器便应运而生。在设计下一代测试系统和综合仪器的基础上,给出了下一代测试系统的关联多参量的描述方法,以及对自动测试至关重要的同步测试方法。
传统的基于微机的车牌识别系统的方案,使得评价识别效果的识别速率和识别成功率两个重要指标相互冲突。为了解决这个问题,很多文章提出了改进算法来调和识别算法的计算量和识别的成功率,但却没有考虑识别系统的成本问题。提出了一个基于DSP+CPLD的硬件识别平台,可以大大提高各种识别算法的适应性和降低系统成本。
为了提高数据库恢复过程服务的有效性,给出基于数据项的分类标记方法的错误隔离模型,同时给出基于事务依赖关系数据修复算法。该模型和算法能够有效地减少修复错误所需的时间。