保持外形特征的网格简化算法

目前许多网格简化算法在大幅度减少算法简化时间的同时,忽略了模型简化后的仿真质量。为此提出一种基于外形特征保持的网格简化算法：依据顶点坍塌值由小到大的次序将顶点排入网格简化优先队列中;每次选择队首顶点向其折叠点合并,并且更新队列中受影响的顶点信息,再对队列重新排序。此算法数据结构存储简单,大规模简化后的模型仍然较好保持了原模型的视觉特征。     

一种应用于DVB-RCS卫星通信系统的存储优化带宽请求算法

DVB-RCS 卫星通信系统中,已有的带宽请求算法多注重于队列延迟以及带宽利用率等性能的提高而未考虑卫星终端的存储优化针对此问题,提出了一种应用于 DVB-RCS 卫星通信系统的存储优化带宽请求算法,该算法通过预测到达数据流的容量来实现对发送队列中数据总量的控制,同时兼顾对传输时延以及传输效率的平衡。仿真表明,该算法能够合理控制系统的存储容量,并且在优化带帘利用率、控制时延抖动等方面与已有算法相比具有同样的高性能.     

基于局部比值法的强弦图带权控制集问题的线性时间算法

一个无向图G＝(V,E)的顶点子集DV是控制集,当且仅当任意一个顶点v∈V－D至少与一个顶点u∈D相邻。图G中的顶点数最少的控制集称为最小控制集,带权控制集问题是求解给定的顶点带权的无向图G的权最小的控制集。结合强弦图的性质,给出基于局部比值法的线性时间算法来求解强弦图带非负权的控制集问题,同时给出了算法复杂度的证明。     

区分服务网络队列调度策略的研究与仿真

针对目前几种DiffServ(Differentiated Service)网络队列调度算法进行研究,提出一种动态队列调度策略来提高队列转发效率。通过动态调整队列权值实现队列的动态管理,从而改进网络资源的利用效率,改善DiffServ网络QoS。利用NS2模拟动态队列调度算法,实验表明动态队列调度算法有效地提高了区分服务网络的队列转发效率。     

一种分布式实时系统任务调度算法的设计

结合分布式系统和实时系统的特点,分析了分布式系统任务调度算法和实时系统任务调度算法,为了能够较好地实现系统的并行性能、实时任务的调度性能以及网络的负载平衡,提出一种将分布式系统任务调度算法和实时系统任务调度算法想结合的算法,采用层次式调度算法以及动态权值的轮转调度算法和速率单调调度算法相结合,在队列权值固定的实验基础上,采用随机改变队列权值的算法,实验证明该随机改变队列权值的算法能够更好地调度任务.     

基于内容与链接分析的主题爬虫研究与设计

现存主题爬虫算法在抓取主题网页方面,其准确性不是很高。本文提出一种基于文本内容评价与网页链接评价的主题网页抓取方法。首先计算当前网页与主题的相关度,然后将相关度值与给定阈值进行比较决定当前网页是丢弃还是存储,同时相关度值的大小也决定了待爬链接队列中URL的优先权,此模型考虑了主题网页的准确率与覆盖率之间的平衡。新设计的主题爬虫算法在抓取主题网页方面,其准确性有一定程度的提高。     

一种Internet上的优先权加权平均数据传输方法

文章基于优先权处理和队列式加权平均流量分配提出一种在Internet上有效地传送带优先权数据的方法,该方法包括两个路由器优先权加权平均算法(PWFQ):单队列记数排序算法(SQSS)和多队列布谷鸟轮换算法(MQRR)。路由器使用PWFQ公平有效地为超流(superflow)分配和调整带宽,并实现了网络阻塞时传输质量的平缓缩减,同时为子流(flow)提供优先权服务,高优先权的子流将被优先服务,从而保证传输的QoS。MQRR还融入RED算法以在阻塞时得到更好的链路利用率、吞吐率和数据流缩减.这种方法融合了Guaranteed服务和Differential服务的优点,算法的计算复杂度不高,实现较易。实验表明这个方法是有效实用的。     

保特征的网格光顺算法

提出了一种保特征的网格光顺算法，能够在快速地去除噪声的同时，保持网格模型的结构特征。该算法对网格中每个三角形的法矢进行光顺，同时求得顶点的法矢。根据当前点到邻接点的距离以及当前点的法矢与邻接点的法矢的夹角对顶点移动的方向进行调整，使顶点分布更加均匀。利用高斯函数求得光顺权值。实验结果证明，该算法能够有效地保持网格模型的结构特征，同时具有迭代次数少、体积收缩小、执行效率高的特点。     

基于加权有向图的权频繁模式挖掘算法

为解决加权图遍历模式的挖掘问题,提出了一种从加权有向图中挖掘加权频繁模式算法.在该算法中,利用图全局拓扑结构和顶点权值信息评估遍历模式的权支持度,从而将剪枝问题转化成模式可扩展性问题,再利用可扩展模式产生候选模式集.本算法把图,顶点权值融合进来,提高了挖掘结果的准确度.实验结果表明,该算法可以有效地进行基于加权向图的权频繁模式挖掘.     

采用快速排队算法的WSN任务调度策略研究

针对TinyOS使用的FCFS以及各种改进的基于静态优先权的调度策略的缺陷,提出了一种适用于无线传感器网络的基于动态优先权的FQ-IP任务调度策略。该策略通过定时地增加任务队列中任务的优先权大小,使得低优先权任务能够在一定的时间限制内得到系统的调度,提高了系统的整体任务吞吐量。同时,随着无线传感器技术的发展,任务队列长度的增加使得排队算法显得愈发重要,提出了一种平均查找长度较小的排队算法,通过测试表明,该算法可以在增加很小的计算开销下显著提高排队速度。     

保持视觉外观特征的网格简化

针对附有纹理属性的网格模型,提出并实现了一种保持模型基本外观和形状特征的多分辨率网格简化算法.采用半边折叠操作,综合考虑了网格模型半边的几何重要性和纹理属性重要性,将其作为各半边的折叠代价来确定模型中所有边的折叠顺序.预先对网格模型中的边界边和纹理边进行标记,并在简化过程中进行加权处理.实验结果表明,即使在急剧的模型简化后,该方法仍能很好地保持原有模型的视觉外观和形状特征.     

结合面积度量和误差校正的网格简化算法

提出了一种基于边折叠的网格模型简化的新方法。考虑到模型的局部形状特征，算法将局部面积度量因素加入简化计算过程，与二次方距离误差测度一起组成新的误差目标函数。还提出了计算二次方误差矩阵的预测-校正模型，用于降低简化累积误差。实验结果表明，该算法通用性较强，能够显著提升模型的简化质量，特别是对于曲率变化剧烈的模型表面，其简化模型能够更好地保持原有特征。     

保持属性特征的模型简化算法*

为较好保持模型的拓扑结构和属性特征,采用基于半边折叠简化思想对模型进行了带属性简化算法的研究。算法考虑了几何误差度量算子的三个因子：折叠边的欧氏距离、折叠边二面角和顶点到星型邻域平面的距离;引入模型属性特征权重值,将几何误差和属性误差加权作为总体误差进行简化,并对简化质量进行了合法性检查。实验证明,算法在保持模型几何和属性特征方面有效。     

基于二次误差测度的车身网格简化算法研究

在车身逆向设计中,点云数据预处理后形成的拓扑网格数据庞大,导入三维软件中进行处理时,对计算机显示、分析、存储、传输等造成很大负担。该文研究了车身曲面重构过程中基于二次误差测度的边折叠网格简化算法。该算法将点到相关平面距离的平方和作为误差测度,进行多次选择性边折叠,实现网格有效简化。采用VC++6.0编程实现了该算法,实验表明, 算法稳定可靠, 效率较高,简化效果好。     

基于局部区域面积度量的边折叠简化算法

目前提出的网格简化算法中,边折叠简化方法是一种主要的简化方法,在网格压缩、多细节层次模型生成、递进网格构造中得到了广泛的应用.本文在基于边折叠算法基础上引入局部区域面积度量方法,将其应用到折叠代价计算中,改变边折叠顺序以进行网格简化.实验表明,算法不仅能有效地保留原始网格的模型特征和视觉特征,速度更快而且能够合理地分配三角面片.     

Parameterized algorithm for eternal vertex cover

In this paper we initiate the study of a “dynamic” variant of the classical Vertex Cover problem, the Eternal Vertex Cover problem introduced by Klostermeyer and Mynhardt, from the perspective of parameterized algorithms. This problem consists in placing a minimum number of guards on the vertices of a graph such that these guards can protect the graph from any sequence of attacks on its edges. In response to an attack, each guard is allowed either to stay in his vertex, or to move to a neighboring vertex. However, at least one guard has to fix the attacked edge by moving along it. The other guards may move to reconfigure and prepare for the next attack. Thus at every step the vertices occupied by guards form a vertex cover. We show that the problem admits a kernel of size k⁴(k+1)+2k, which shows that the problem is fixed parameter tractable when parameterized by the number of available guards k. Finally, we also provide an algorithm with running time O(²O(k²)+nm) for Eternal Vertex Cover, where n is the number of vertices and m the number of edges of the input graph. In passing we also observe that Eternal Vertex Cover is NP-hard, yet it has a polynomial time 2-approximation algorithm.     

一种基于加减法求交和顶点类型的凹多边形水平扫描填色算法

本文给出了一种只有加减运算就能求大平线线与凹多边形边界交点的方法,并根据顶点类型定义,将凹多边形顶点分成“水平顶点”、“极占”、“拐点”三类。设计了基于三类顶点的边界存储结构;建立了凹多边形水平扫描填色算法,解决了当交为顶点时可能产生的“交点对”不配对的问题。     

基于隐函数插值的连续多分辨率模型

提出了一种基于变分隐函数插值的连续多分辨率模型生成算法,通过递归地删除网格模型中的边得到连续的简化模型.算法采用变分隐函数插值的方法对网格模型分区域插值,生成原始模型的区域插值隐函数曲面,并以对应隐函数曲面上的采样点作为边折叠的目标点.算法建立了可调加权控制函数来控制边的简化顺序.在模型简化过程中,可通过交互调节控制函数的权值执行不同的简化原则,使得重要度低的边优先删除.此外,通过建立独立集,避免了模型的局部过度简化.实验结果表明,此算法能实现较理想的简化效果.     

顶点链码表示区域的面积计算

链码因其能用较少数据来存储较多信息而得到广泛应用。顶点链码是一种用边界象素的顶点个数表示区域的编码技术。本文从顶点链码的性质出发,给出了直接由顶点链码求其所围区域面积的算法。     

虚拟手术仿真中三维模型简化方法的研究

针对虚拟手术仿真中海量三角网格模型的特点,提出一种改进的基于边折叠的模型简化算法。该算法在经典边折叠算法的基础上,从误差估算、折叠点选取、模型平滑三方面进行了改进,进一步优化三维模型的简化速度和外观效果。实验结果表明,改进后的边折叠算法对海量三角网格的肝脏以及静脉模型的简化速度显著加快,简化后的模型与原模型相比在视觉上保持了良好的一致性,证明了该算法的有效性和可靠性。