货郎问题求解算法分析

介绍了求解货郎问题的4个算法：贪心算法、MST近似算法、MM近似算法和回溯搜索算法。分别使用各个算法对一个货郎问题的具体实例进行求解，并对各个算法的性能进行了分析比较。贪心算法的运行速度较快，但在大多数情况下该算法找到的是次优解而非最优解。MST和MM近似算法用以求解满足三角不等式的货郎问题，其近似性能比（即精确度）分别为：RMST（I）＜2，RMM（I）＜3／2。回溯搜索算法可以求出货郎问题的最优解，随着城市数目的增加，其搜索效率会下降。     

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

在最近邻法、k-变换策略和贪心算法的基础上,尝试设计效率较高的产生旅行商问题较优可行解的方法。将3变换邻域分成两种结构(称为3_1和3_2变换邻域)考虑,设计以下算法:利用最近邻法产生初始当前最优解;然后依次在当前最优解的3_2、3_1、2变换邻域中寻找更优的局部最优解成为当前最优解,直到结果没有改进。利用算法对一些经典的实例进行实验,依次将每个城市作为出发地,在多项式时间O(n4)得到的最优解与给定的最优解相对误差在1%内。     

顶点的度与Hamilton圈算法

单图可按顶点的度构作Hamilton圈,本文给出Hamilton圈的一个算法.     

0_1背包问题及贪心算法应用

本文结合生活中顾客中奖后奖品的选择问题,给出背包问题的数学模型,介绍基于0_1背包问题的贪心算法,使用这种算法解决奖品选择问题,最后再用C＋＋编程实现.     

带权PLA折叠问题及其启发式算法

本文将可编程逻辑阵列（ＰＬＡ）的折叠问题推广到行列折叠点间带权的一般情况，对这个ＮＰ－完全问题给出三个启发式算法，其中两个为贪心类算法，另一个是利用独立集的启发式算法，分析了各个算法的复杂性。     

关于旅行推销员问题的一个算法

通过圈上结点下标自足方法，给出了一个关于旅行推销员问题的算法，尽管该算法实质上无法改变问题的NP－完全性的难度，但较分支定界法的执行速度快，比一些近拟算法要好。     

套利问题的贪心算法设计

通过对套利问题的具体分析，利用该问题本身具有的一些特性，并结合实际的6种货币汇率的交叉兑换数据，提出了一个用贪心算法解决该问题的可行方案，同时给出了示例数据的求解结果；讨论了套利的实际可操作性。     

用贪心算法求解删数问题

贪心算法作为解决问题的一类重要方法,因其直观、高效的特点而受到重视。如果某一类实际问题,能够具有最优予结构和贪心选择性质,那么它就可以通过一系列局部最优选择来获得整体最优解。本文首先对删数问题进行了分析,然后给出了该问题的贪心解法。最后对所提出算法的时间复杂度进行了分析。     

单向Hamilton最优通路的求解新方法及其算法设计

Hamilton(哈密尔顿 )问题包括最小 Hamilton圈 ,以及单向 Hamilton最优通路两个基本问题 ,后者属于排序问题 .同 H-圈问题一样 ,目前尚无一种有效求解方法 .使用元素判别值分配法求解单向 H-通路问题 ,仅一次调配便可获得最优的单向 H-通路 ,无须调整 .它具有显著的特点 .文中介绍单向 H-通路求解的表上作业法及计算机程序的算法设计 .     

基于贪心算法的离散单位圆盘覆盖问题研究

提出了一种基于贪心启发式的计算方法,可以在多项式时间复杂度内获得DUDC问题的近似最优解.首先生成了可替代二维平面的离散单元格,在每一单元格中心建立能够覆盖一定数量目标点的替代集,使用贪心算法确定替代集的最小组合方式,实现了对目标点的全覆盖.基于每个子集内所包含的点的具体位置,计算了其最小覆盖圆.最小覆盖圆的中心视为选址位置.基于具体案例证明了算法的有效性.讨论了该算法的影响因素,分析了时间复杂度以及近似度比率.     

改进的生成树算法求解旅行商问题

给出了一种基于最小生成树的TSP求解算法,该算法结合贪心算法和匹配算法,把传统近似算法的局部最优转化为全局最优,避免了最邻近算法中最后几步产生的较大的误差.文章最后分析了算法的复杂性,实验数据表明该算法有较高的有效性.     

基于贪心算法的改进遗传算法解决背包问题

本文分析了简单遗传算法解决背包问题时候的一些缺陷,并通过适应度函数的计算以及选择方式的改进,给出了一种基于贪心算法的混合遗传算法以解决这些缺陷。实验表明,改进的遗传算法具有一定的优越性。     

篮球场灯光照明问题的算法设计

提出了依据球场平面照度不均匀度最小的约束条件排列照明光源的方法．将光源依照度大小非递增排序，根据照度与空间距离变化规律和光源架与篮球场的具体尺寸，采用贪心算法设计技术，依据使球场平面上最小照度取最大值和最大照度值取最小的原则，依次排列照明灯．计算表明，此方法降低了球场照度的不均匀度，提高了篮球场照度的均匀性．     

多约束条件车辆路径问题的二阶段遗传退火算法

针对多约束条件的多配送中心有时间窗车辆路径问题,提出了一种二阶段遗传退火算法.在第1阶段,使用遗传算法对客户按供应量和路径长度进行模糊分区;在第2阶段,采用二维变长染色体编码及相应的遗传算子进行混合遗传算法的全局优化.在初始种群生成和交叉、变异算子中采用了随机贪心算法以避免无效解,并利用退火选择来提高种群的多样性.实验结果表明,二阶段遗传退火算法可加速收敛,提高搜索效率,在模糊分区上的搜索速度较之标准遗传算法提高了3～10倍.     

近似求解子问题的乘性Schwarz算法

提出求解线性互补问题的一个乘性Ｓｃｈｗａｒｚ算法，算法中子问题非精确求解，得到了单调收敛性及误差估计式。     

贪心算法在多机调度问题中的应用

设有n个独立的作业{1,2,…,n}和m台相同的机器,利用贪心算法的原理使所给的n个作业在最短的时间内由m台机器完成。     

使用模拟退火算法解课表问题

给出一种使用模拟退火算法（ＳＳＡ）来解课表问题的方案，详细地讨论了方案涉及的各种问题，包括目标函数和初解的确定，邻域和新解的产生方法，初始“温度”的确定和“温度”更新的方式，内循环次数及算法终止条件的确定等，章的最后给出了该方案的一个实例和若干性质分析。     

求解最优控制问题的改进辛几何算法

最优控制问题的 Pontryagin极大值原理以 Hamilton形式为基石 ,合理的数值计算应当遵循 Hamilton体系的性质 ,而以 Runge- Kutta( R- K)方法为代表的传统计算方法却不能保持这一性质 .本文尝试用基于 Hamilton体系的辛几何算法求解最优控制问题 ,提出了消除计算过程中误差生长的方法 ,最后设计了仿真算例 ,与 R- K法相比显示了明显的优越性     

闭包是完全图的求Hamilton圈的新算法

Hamilton圈问题是一个典型的NP-完全问题,文章设计和研究了闭包是完全图的求Hamilton圈的新算法,其基于Bondy-Chvátal算法,与原来算法相比,新算法存在易于程序设计、可读性强等优点,且不失其好算法的特性。