一种矩形的动态不干涉算法

针对处于相对运动状态下的两矩形图之间在任一瞬间的不干涉判断问题,也即矩形的动态不干涉判断问题,根据不适合多边形（No-Fit-Polygon)法和矩形的几何特性,给出了相对运动的矩形与矩形图形之间动态不干涉（不重叠）的判别条件及其证明,同时给出其不适合多边形（转化为对称八边形）顶点的简捷计算公式和相应的不干涉算法。该算法具有优良的计算特性,特别适用于既有相对平移又有转动的这种相对运动的两矩形图形之间的动态不干涉判断,并具有一定的应用价值。     

一个新的椭圆-椭圆的静动态不合适边界算法

在求解Packing问题、机器人路径规划、虚拟装配、三维圆形管道作任意斜切割、医疗内外科手术中等经常用到两椭圆干涉算法。该文根据椭圆的画法提出了一个新的椭圆-椭圆的静动态不合适边界算法。和陈羽等(2003)的算法相比,该算法无需反复求三角函数和反正切三角函数值。另外,该算法具有计算工作量相对较少,容易实现等特点。     

椭圆-椭圆不适合边界的解析方程及其干涉判断

在医疗内外科手术,虚拟装配等计算机可视化领域中,经常需检测椭圆-椭圆的干涉性。为了更好地进行干涉判断,根据椭圆-椭圆外切的代数条件——广义特征多项式具有正的重根,以及进一步证明出的该正重根的唯一性结论,利用仿射变换和逆变换方法,推导出了椭圆-椭圆的不适合边界(NFB)解析方程。根据该解析方程不仅可以直接对任意两个椭圆之间的干涉性做出精确判断,并且可由此绘出NFB的轨迹图,同时使用可视化方法给出了快速粗略的判断。在医学影像诊断上这两种方法可结合应用。     

带静不平衡约束的矩形装填问题的启发式算法

卫星舱布局问题不仅是一个复杂的耦合系统设计问题,也是一个特殊的优化问题,具有NP难度性。解决这类问题最大的挑战在于需要优化的目标函数具有大量的被高能势垒分隔开的局部极小值点。Wang-Landau（WL）抽样算法是一种改进的蒙特卡罗方法,已经被成功地运用蛋白质结构预测等优化问题。本文以卫星舱布局优化问题为背景,首次将WL抽样算法引入矩形装填问题的求解。针对矩形装填物的特点,提出了启发式格局更新策略,以引导抽样算法在解空间中进行有效行走。为了加速搜索全局最优解,每次蒙特卡罗扫描生成新的布局时,便执行梯度法进行局部搜索。通过将局部搜索机制、启发式格局更新策略与WL抽样算法相结合,提出了一种用于解决带静不平衡约束的任意矩形装填问题的启发式布局算法。在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项并采用质心平移的方法,使布局系统的静不平衡量达到约束要求。另外,为了改进算法的搜索效率,提出了改进的有限圆族法用于装填物之间的干涉性判断和干涉量计算。通过对文献中两组共10个有代表性的算例进行实算,计算结果表明,所提出的装填算法是一种求解带静不平衡性能约束的任意矩形装填问题的有效算法。     

带静不平衡约束的正交矩形布局问题的启发式模拟退火算法*

以卫星舱布局为背景,研究一类带静不平衡约束的正交矩形布局问题.借鉴拟物策略,定义矩形与矩形、矩形与圆形容器之间的嵌入度计算公式,将该问题转变为无约束的优化问题.通过将启发式格局更新策略、基于梯度法的局部搜索机制与具有全局优化功能的模拟退火算法相结合,提出一种求解带静不平衡约束的正交矩形布局问题的启发式模拟退火算法.算法中的启发式格局更新策略产生新格局和跳坑,梯度法搜索新格局附近能量更低的格局.另外,在布局优化过程中,通过在挤压弹性势能的基础上增加静不平衡量惩罚项,并采用质心平移的方法,使布局系统的静不平衡量达到约束要求.实验表明,文中算法是一种解决带静不平衡约束的正交矩形布局问题的有效算法.     

基于模拟退火剩余矩形算法的矩形件排样

针对矩形件优化排样问题,讨论了用模拟退火算法结合剩余矩形法求解问题。首先阐述了矩形件排样问题的数学模型,然后给出了模拟退火剩余矩形算法求解问题的步骤和方法,最后用实例进行了算法验证。实例分析表明,采用模拟退火剩余矩形算法求解矩形件排样问题是适合的。     

矩形件无约束二维板材剪切的4块排样算法

针对矩形件无约束二维板材剪切排样问题,提出一种新的4块排样方式及其生成算法.该排样方式将板材划分成4个块,对每个块,按照递归方式进行排样.选择一行同种矩形件放置在块的左下角,沿着这行矩形件的上边界和右边界将该块剩余部分划分成两个更小的子块以待进一步递归考察.首先,构造动态规划算法一次性生成所有可能尺寸的块中矩形件的递归...     

边界镜像对称延拓双正交小波变换矩阵的构造

计算小波变换的Mallat算法需要进行逐级分解和重构,对于有限长信号的小波变换来说,为了保证其完全重构,有必要对其进行边界延拓。基于边界周期延拓的小波变换算法极易实现,也常见于文献,而边界对称延拓较周期延拓则更适合用于信号和图像的处理,但基于边界对称延拓的小波变换矩阵实现方法却很少出现在文献中。为了用矩阵-向量乘积实现信号的小波变换,给出了一种在信号镜像对称延拓方式下,任意深度小波变换矩阵的构造方法,并证明了该延拓方式下实现Mallat算法的完全重构条件。作为实例,绘出了B ior3.3小波的分解和重构矩阵的基向量及波形图。将构造的变换矩阵用于基于小波的图像处理中,不仅可以避免逐级迭代,大大简化运算量,而且边界效应也明显减少。     

FDS中非矩形边界隧道的自动建模

FDS(Fire Dynamics Simulator)作为一种高效的火灾模拟软件,在对非长方体隧道进行火灾模拟时有很大局限性。文章提出了一种用矩形方块来拟合圆弧墙或斜线墙的算法;通过编制可视化软件来自动生成FDS输入数据,解决了在FDS中对非矩形边界隧道的建模问题;最后给出了一个在FDS中对非矩形边界隧道火灾的数值模拟实例,验证了算法的可行性。     

基于Mallat算法的图像边界问题的研究

首先介绍了一维信号边界对称延拓方式及图像双正交小波分解重构算法,然后在一维信号边界延拓方式的基础上,研究了当高、低通滤波器长度为偶数,且关于1／2对称时,图像能够精确重构的边界延拓问题,并给出了图像的小波变换及边界对称延拓的步骤。最后,通过仿真实例验证了该对称边界延拓方式能够保证图像在小渡变抉中精确重构。     

一种新的凸多边形不干涉算法

求解Packing问题、计算机辅助设计、机器人路径规划、虚拟装配等经常用到凸多边形的不干涉算法。该文根据不适合多边形的概念,通过给定的平移规则控制平移多边形中心的移动方向和位移量而计算出两凸多边形的不适合多边形,进而提出了一种新的凸多边形不干涉算法。最后用实例说明了它在布局求解中的应用。文中方法不存在斜率图算法的缺陷,其计算复杂度为O（n+m）。     

Generating strictly non-self-overlapping structured quadrilateral grids

In this paper, we present a BPM (Bézier patch mapping) algorithm which generates a strictly non-self-overlapping structured quadrilateral grid in a given four-sided planar region. Given four pieces of polynomial curves which enclose a simple region in the plane, the algorithm first constructs a Bézier patch which interpolates the four curves (as its four boundary curves), while the inner control points of its control grid remain unknown. In this paper, we show that, for the bijective condition to be satisfied, it is sufficient that the interior points satisfy a set of quadratic inequality equations. Exploiting this key result, we formulate the mapping algorithm as an optimization problem where the constraints are the bijective condition of the Bézier patch mapping (BPM), and the objective is to find out the best from all of the non-self-overlapping grids. Thus, commercial optimization solvers can be used to find the bijective mapping. If a solution to the optimization problems exists, then so does a solution to the mapping problem, and vice-versa. The BPM method is simple and intuitive, and some examples presented in this paper demonstrate its effectiveness.     

一个基于进程保护的可信终端模型

针对外包数据库系统中的隐私匹配问题,提出了基于分布针对计算机终端是网络系统中安全风险的根源问题之一,提出了一种新的基于进程保护的可信终端模型。该模型通过进程静态、动态保护和进程间无千扰来判定系统的可信性。进程静态保护的主要功能是确保进程代码和辅助文件的完整性,进程动态保护的主要功能是防止进程运行的相关数据被篡改,进程间无干扰的功能是基于无千扰理论判断进程交互的合法性。理论分析结果表明,该模型的可信性与基于可信根的无干扰可信模型等价。但该模型不仅有效克服了基于可信根的无千扰可信模型中的可信传递函数。Check( )的不合理性,而且将系统的状态、动作具体化,使得该模型更直观、具体,更容易理解,与实际的终端系统更相符。     

Linear quadratic control with stability degree constraint

The problem of static state feedback Linear Quadratic (LQ) optimal control subject to a prescribed degree of stability for the closed-loop system is considered in this paper. A necessary optimality condition is given via the Lagrange multiplier method. A globally convergent algorithm is provided to solve the optimization problem. It is shown that the algorithm recovers the standard LQ feedback gain provided the desired stability degree is small enough to be within the range by the standard LQ design. As for other cases the optimum occurs on the boundary of the α-region. A numerical example shows that the proposed algorithm provides a better design compared to the existing methods.     

Formulating and solving parametric design problems involving non-interference constraints

Improvements in computer-aided design (CAD) tools can significantly increase designer productivity, since the ability to explore a variety of possible designs quickly and effectively is essential for a designer. Using an optimization tool, systematic exploration of design spaces can be achieved readily. The general goal of the work presented here is to aid design by combining the strengths of optimization techniques with those of CAD systems. The specific objective of this paper is to introduce goal directed geometry (GDG) as a computational framework for parametric design, aiding the formulation of engineering problems with geometric considerations and their solution with a multi-objective optimization package. Using GDG, What if questions can be posed and answered in a systematic fashion. Specific issues to be addressed include the development of a general parametric design problem formulation, development of static and dynamic geometric non-interference constraints for use in this formulation, and investigation of the efficacy of the adaptive linear programming (ALP) multiobjective optimization algorithm in solving such problems. Two examples are presented, one each to illustrate the use of the static and dynamic non-interference constraints. Results demonstrate that the GDG formulation can be applied readily to a wide variety of parametric design problems. Additionally, the ALP algorithm successfully navigates around geometric constraints, although care must be taken when linearizing highly non-linear design spaces.     

基于无干扰理论的在线用户行为可信性分析方法

针对在线应用中用户行为可信性难监测、难评判的现状和当前用户行为可信性分析理论薄弱问题，提出一种基于无干扰理论的在线用户行为可信性分析方法。首先，从执行单步行为的行为实体身份、状态、环境三方面定义单步行为静态可信性，给出静态可信验证策略；然后，从行为执行过程和结果两个角度定义行为动态可信性，给出行为动态可信验证策略；最后，基于单步行为构建用户行为流程，提出基于可信扩展思想的用户行为流程可信性判定定理，并应用无干扰理论进行定理证明。证明过程及结果验证了所提方法的正确性和有效性。     

基于蝙蝠算法的PFSP调度干扰管理研究

对置换流水车间调度问题分别加入单工件、双工件、四工件干扰因素,采用较新颖的蝙蝠算法对其进行优化,并同较成熟的粒子群算法进行比较,结果表明新型启发式智能蝙蝠智能算法性能不仅仅适用于生产调度干扰管理问题的求解且优于基本粒子群算法,同时对其加权系数进行测试分析,结果表明了加权系数对生产调度干扰管理影响的权重。     

Routing in Polygons Without Rectilinearly Visible Corners

In this paper we present an algorithm for the routing problem in a routing region which is bordered by a simple polygonal line, such that there are no rectilinearly visible corners. The routing problem consists in finding pairwise edge-disjoint paths in the grid for the nets connecting some given pairs of boundary vertices. Whenever a solution exists our algorithm finds it in time O(U log²U), where U is the size of the boundary. This is a generalization of the algorithm for rectangle routing by Mehlhorn and Preparata (1986, J. Assoc. Comput. Mach.33, 60-85), which up to now has been the only method with sublinear running time in respect of the routing area.     

Implementation, interpretation, and analysis of a suboptimal boundary finding algorithm

This paper presents a suboptimal boundary estimation algorithm for noisy images which is based upon an optimal maximum likelihood problem formulation. Both the maximum likelihood formulation and the resulting algorithm are described in detail, and computational results are given. In addition, the potential power of the likelihood formulation is demonstrated through the presentation of three simple but insightful analyses of algorithm performance. These analyses are based on a technique we have developed for comparing the accuracies of different boundary finding algorithms. This technique also helps in understanding the interplay of object shape and data models in the relative performances of boundary finders. Some of the algorithm design considerations resulting from the use of our analysis technique are new and, at first, surprising. Our technique appears to be the only one developed for comparing the accuracies of different boundary finding algorithms.