同类机半在线排序问题及其近似算法

研究两台同类机系统两个半在线排序问题 .第一个为总加工时间已知 ,第二个为最大工件加工时间已知 .对这两个问题 ,文章给出了各自的近似算法 ,证明了它们的最坏情况界分别为 3和3/2 .文章还研究了上述问题的下界并与我们的算法的最坏情况界进行了比较.     

占线顶点覆盖问题的结构性下界

在实际 顶点覆盖选址过程中,经常会遇到如下的情形:在需要服务的边的个数未知的前提下,决策者需要决定在哪里建立初始的设施(或设施集),同时还要求,当新的设施建立后,前面已经建立的设施不能被删除.以往一般建立的模型和算法都是针对静态选址而言的,这里需要的是满足上述约束的动态选址模型.考虑了占线顶点覆盖问题,给出了一个不需要任何复杂性假设条件下的结构性的下界结果,并通过对一个限制性条件下的占线顶点覆盖问题给出算法并证明竞争性能比结果说明了所作的下界分析是紧的,同时证明了所给出的算法在非多项式时间内是最优的.     

求解项目调度中资源水平问题的近似算法

针对RLP与RCPSP的相似之处和自身特点，以求解PCRSP的遗传算法为基础，设计了一种求解RLP的基于分支定界策略的近似算法，搜索树的每一节点对应一个RCPSP，通过求解各节点RCPSP来求得RLP的最优调度计划，算法从具有基本资源需求水平的根节点开始，采用宽度优化顺序逐渐提高各种资源的可用量，既有利于资源的均衡利用，又可以通过定界策略有效地控制搜索树的节点数量，结合实例问题说明了基于分支定界策略的近似算法的求解过程，最后通过实例问题对该算法与遗传算法进行求解效果和时间效率的对经，分析了对比结果。     

带核集分划问题的一个改进近似算法

设有整数集S={ $r_1,r_2; p_1, p_2,\cdots, p_n$ }, 这里$r_i\geq 0, p_j>0$ (I=1, 2; j=1, 2, …, n), 寻找一个S的分划P=($S_1, S_2$)使得: 1) $r_i$属于不同子集, 2) $S_1$与$S_2$中元素总和较大者尽可能地小. 这是一个NP-完备问题. 其已有的线性时间算法近似比为8/7, 文章在此基础上给了一个线性时间改进算法, 它的近似比为10/9.     

差异作业批调度的流水车间问题及近似算法

考虑了尺寸有差异的作业在两台设备上的流水加工问题,两台设备均为批处理机,有确定的最大容量.采用了制造跨度和总完工时间两类目标函数,建立了基于整数规划的优化模型,分析了两类问题的计算复杂性,给出了设备和作业数量既定情况下的可行解规模.设计了一种基于LPT规则和批调度规则的近似算法,时间性能为O(nlogn),证明了该算法在优化制造跨度时的最坏性能比不大于2,优化总完工时间的最坏性能比不大于3.     

最小顶点覆盖问题的DNA分子算法

最小顶点覆盖问题是找给定图G中覆盖每条边的最小顶点子集,这个问题即是一个著名的NP 完全问题。给出了基于分子生物技术的图的顶点覆盖问题的DNA算法。算法的关键是数学问题到DNA链的映射,对图中的顶点进行恰当的编码,以便于使用常规的生物操作及生物酶完成解的产生及最终解的分离。依据分子生物学的实验方法,提出的算法是有效和可行的。最后指出了该算法的优点、存在问题及下一步的研究方向。     

传感器网络中基于Voronoi网格的快速覆盖判定算法

覆盖问题是传感器网络研究中的一个基础课题,判定感兴趣的区域是否被一组给定的传感器节点完全覆盖,在监控等传感器网络的许多应用领域中具有重要意义。提出了一种传感器网络中基于Voronoi网格的快速覆盖判定算法VT-RCDA(Voronoi Tessellation based Rapid Coverage Decision Algorithm)。算法首先将感兴趣的区域进行正方形网格剖分,然后采用Voronoi网格模型将复杂的区域覆盖问题转化为简单的顶点覆盖问题。理论分析与仿真实验表明,与已有算法相比,新算法具有较好的覆盖判定正确率,较低的计算复杂度,且针对具有n个节点的传感器网络,能在O(nlogn)的时间开销内快速判断出任意给定感兴趣区域能否被这n个传感器节点覆盖。     

逆一般中心选址问题的算法研究

主要讨论了逆一般中心选址问题的算法研究。对于实例是树且U为整数的情况,逆一般中心选址问题转化为逆中心选址问题。对于实例是一般简单图的情况,本文给出了一个逆一般中心选址问题转化为权重为1的S te iner树问题的拟多项式算法。并对于权w=1的S te iner树问题,本文也给出了一个近似界为43的近似算法。     

二分图匹配模型下的武器目标分配问题

武器目标分配问题是研究双方交战时,按照一定分配原则将武器分配给多个能造成威胁的对方目标,从而达到最佳打击效果的问题,也是军事运筹学领域经典的组合优化问题。提出了二分图匹配模型下的武器目标分配问题,并建立了相关的数学模型,最后运用结合了贪心策略的Kuhn-Munkres算法对模型进行求解。通过使用随机生成的20个规模不同的实例来测试所提模型与算法的有效性。计算实验结果表明,提出的模型与算法求解精度高、求解速度快,可以满足武器目标分配问题快速做出最优决策的要求。     

基于单亲遗传模拟退火算法的顶点p-中心问题

针对顶点p-中心问题这一经典的离散选址NP困难问题提出了一种单亲遗传和模拟退火的混合算法.该算法:1)采用单亲遗传算法简化遗传操作过程;2)加入模拟退火策略,增强局部优化能力;3)提出自适应选择法,根据个体的优劣及算法迭代情况来选择个体;4)设计了自适应基因重组操作;5)采取最优保存策略,避免最优解的丢失.数值实验结果表明了该算法对于解决规模较大的顶点p-中心问题的有效性.     

基于三角形形态变化的网格模型简化算法

着重分析和研究了在模型简化过程中因对视觉效果考虑不足而导致的视觉特征急剧改变问题,因简化算法的误差积累而容易错误地选择折叠边的问题,提出了一种基于三角形形态变化的网格简化算法,该算法在计算边的折叠代价时将边的长度以及边折叠后生成的三角形内角与等边三角形内角的差异作为加权因子,在计算顶点的二次误差测度时考虑顶点周围每个三角形的面积因素,对每个顶点的二次误差测度求均值,有效地解决了上述问题。经实验验证和对比分析,证明了本算法的有效性。     

一种新型的感知逼真的渐进网格简化算法

网格简化是计算机图形学中一个传统的研究课题,它对网格的存储和传输处理以及实时绘制都有着重要的意义。在视觉感知理论的指导下,提出一种新型的渐进网格简化算法,在简化过程中尽量保持视觉敏感的区域。依据半边折叠的能量函数来有效控制几何误差。实验表明,此算法不但可以生成一系列感知逼真的细节等级模型,而且具有很好的时间复杂性。     

一种网格简化算法及其在三维重建上的应用

针对机器人和自主车辆仿真系统开发的需要,提出了一种利用激光雷达采集的点云数据进行场景重建的算法.该算法根据激光雷达的点云数据生成多边形网格,能够对场景进行有效分割,并在此基础上对多边形网格进行有效简化,从而满足实时仿真系统的需要.在最后给出了仿真实验的结果,实验证明该算法简明有效.     

Algorithm Design and Approximation Analysis on Distributed Robust Game

This paper designs a distributed algorithm to seek generalized Nash equilibria of a robust game with uncertain coupled constraints. Due to the uncertainty of parameters in set constraints, the authors aim to find a generalized Nash equilibrium in the worst case. However, it is challenging to obtain the exact equilibria directly because the parameters are from general convex sets, which may not have analytic expressions or are endowed with high-dimensional nonlinearities. To solve this problem, t...     

基于加权三角面法向变化的模型简化算法

提出一种新的基于边折叠的模型简化算法，该算法在计算边的折叠代价时综合衡量边的长度以及相关三角面在折叠前后面积加权的法向量方向发生的变化。算法能够避免使三角面的法向量发生突变，从而避免模型视觉特征的急剧改变。实验表明本算法能够产生质量较高的简化模型。     

基于构造物特征点的矢量数据化简算法

在进行公路矢量数据化简时,采用已有算法,一些构造物可能会在转换低比例尺时被不正确地化简掉,影响应用的正确性.提出了一种基于构造物特征点的二级矢量数据化简算法,根据空间位置提取高速公路中的构造物点,进行一级化简,构成构造物特征点,以每个特征点作为分割点,将整个曲线划分为若干子曲线,在每个子曲线中采用Douglas-Peucker算法进行二级化简,最后进行子曲线合并,并设计了一种多比例尺矢量数据组织的构建方法.实验表明该数据化简算法能够有效化简数据,并且保存完整的构造物特征点,选取的多级比例尺能够满足应用的需求.     

一种最佳的Mesh中的空闲子网搜索算法

在并行机系统中为了获得系统的高性能,对任务进行处理的有效分配是至关重要的,这需要用最小的时间开销识别所有的空闲处理机。针对网格多处理机的子网分配,提出了一种新的子网搜索算法,该算法实现简单,时间复杂度为O(N     

一种新颖的网格综合优化算法

用三角网格逼近三维扫描所得散乱点集,实现曲面重构,是一种得到广泛应用的技术。为了提高网格对物体表面的逼近精度,需要对网格进行优化。提出一种新颖的网格综合优化算法,将基于SOM的网格优化模型和节点分裂算法有机结合,使网格中顶点的分布更符合散乱点数据的空间分布,使网格更好地逼近数据点集,还通过分裂大度数顶点来改善网格的拓扑关系,使其更好地反映原始数据点集的拓扑特征,也使得网格更加平滑。试验结果表明,该算法取得的网格优化效果良好。     

基于区块自适应网格的全球地形快速绘制算法

在基于球面剖分的全球地形数据组织模型基础上,实现了一种视点相关的全球地形数据快速调度与可视化的算法。提出了一种基于区块纹理分辨率的自适应目标层次模型提取方法,能够快速准确地得到视点相关的正确细节模型,且算法的时间空间复杂度与全球地形模型的数据量无关。进而通过利用区块结构的一致性进行高效的外存数据调度,尽可能地减少了系统I/O带来的性能瓶颈,在实现数据重利用的同时很好地管理了内存消耗。实验表明,基于该算法可以实现全球地形的高效绘制,并且对硬件配置要求很低,具有很好的实用性。