【摘 要】
：
该文讨论的是一类限制在欧式平面上的NP-Hard问题,这类问题可以称为"平面距离和优化问题".该文以实际问题为例介绍这种具有通用意义的近似方案设计技术.该文先阐述随机平面分
论文部分内容阅读
该文讨论的是一类限制在欧式平面上的NP-Hard问题,这类问题可以称为"平面距离和优化问题".该文以实际问题为例介绍这种具有通用意义的近似方案设计技术.该文先阐述随机平面分割的方法与相应结论,之后分别以K-Median与TSP为例重点介绍应用动态规划技术求特殊解的方法,其中该文对文献[1]中TSP问题动态规划算法进行改进:提出一种新的构造方法,使应用于该算法的"补丁定理"结论由常数6改进到常数4,并给出明确证明,从而使该算法的运行时间得以指数倍的缩短.最后该文编程实现TSP问题的动态规划算法,并在实验数据的基础上分析应用该技术存在的问题.同时文中给出针对TSP问题进行剪枝操作的原理与方法.近年来Arora利用该技术获得了TSP、Steiner树、K-Median三个著名NP-hard问题在欧式空间中的多项式近似方案,使得人们对该类问题的认识有了长足进步.
其他文献
CRM和数据挖掘是目前计算机技术领域两个非常热门的话题。CRM是企业信息化的重要内容，它在电子商务中所起到的日益重要的作用，使其受到企业越来越多的重视。数据挖掘是知识发现
本文针对电信储值卡支付业务中对数据安全性要求高，数据处理的实时性要求高的问题，进行了分析，最后采用了交易中间件技术作为解决这一问题的方案。 随着计算机软硬件技术迅速
随着计算机技术的发展，企业在信息化的过程中，难以保持一个统一的技术平台，因此，企业信息资源常常由不同的操作系统、不同的编程语言、不同的技术模型、不同的数据库系统组成。将
维吾尔语名词词汇语义网是以名词词汇所构成的同义词概念集合为描述对象，以名词词汇间的潜在语义关联为连接方式，通过其中的组织与联系，以词义与语义关系为经纬建立的一种词汇语
矩阵分解算法因其模型简单效果显著在很多机器学习任务中备受欢迎，尤其在社区发现、个性化推荐以及文本分析等任务中更是有着极其广泛的应用，然而，矩阵分解算法在处理大规模训练
该文作者曾亲自参与南开太阳公司IC卡智能水表信息管理系统和北京301医院病人订餐系统的设计与实现.针对在这两个系统开发过程中所发现的开发人员对软件工程的认识、开发方法
该文利用数理统计、拓扑、符号动力学等数学原理及现代金融理论、小波理论相结合的新方法一计算机实验数学的方法,研究基于金融领域的非线性复杂系统的混沌分形演化,形成了以
随着信息技术的发展，数据仓库在许多领域发挥了越来越重要的作用。面对当今世界中逐渐增多的数据和信息，人们希望以更低的成本、更快的速度做出及时、准确的决策。业务智能化系
传统市场调查方法和当前的网络市场调查方法都存在着种种不足,为了克服现代市场调查方法的缺陷,该文将现代密码学和市场调查相结合,设计了两种基于Mobile Agent的匿名网络市