支配问题的研究进展

复杂性理论中,支配问题是一类重要的问题,被广泛应用于资源分配、电话交换网络和无线传感器网络等领域。支配问题主要包括点支配集(VDS)问题和边支配集(EDS)问题两大类。人们利用动态规划、加权分治等技术对VDS和EDS问题的精确算法进行设计与分析,并通过将EDS问题转化为边覆盖集问题提出了EDS问题的近似算法。近年来对参数化支配问题做了大量研究。目前已经证明了平面图中VDS问题和一般图中EDS问题都是固定参数可解的(FPT)。利用树分解和分支搜索等技术,人们分别对平面图VDS问题和一般图EDS问题提出了一系列FPT算法。文中对VDS和EDS问题进行了分类,给出了每类问题的具体定义及其相关算法介绍,此外还对矩阵支配集问题进行了简单介绍,并提出了支配问题研究中值得关注的几个方面。     

基于Mybatis框架的批量数据插入的性能问题的探讨

本文首先提出了一个基于Mybatis框架下针对ORACLE的批量数据插入的性能问题,然后针对该问题进行了调查,给出了问题的解决方法,并针对提出的方法进行了性能测试和比较。本文给开发者解决基于java的批量数据插入的性能问题提供了一个思路。     

反馈集问题的研究进展

反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。     

基于规划的空间布局

本文基于正规集首先建立了一个空间布局问题的形式化定义,然后分析了这一问题的计算复杂度,并证明了基于网格上空间布局问题的可计算性.重点介绍了基于分布式规划的住宅平面布局问题的求解模型,同时给出了一个实例,最后分析了规划方法和分布式规划的一些优点.     

求解可满足问题的改进的蚁群算法

可满足问题（SAT）是一个NP-hard问题,将SAT问题转换为无约束的离散优化（最小值）问题。并根据M Dorigo提出的蚁群算法,给出了一种求解SAT问题的新方法：改进的最大最小蚁群系统（MMAS-SAT）。在改进的算法中,给出了SAT问题的构造图,指出了启发式信息值的求法,对衰变系数进行了动态调整。测试问题的数值实验表明,采用MMAS-SAT的结果优于Gwsat、Walksat、Novelty等局部搜索算法,因此该算法是求解SAT问题的一种可行高效的算法。     

基于遗传算法的排课问题研究

排课问题是一个有约束、多目标的组合优化问题,同时也是一个NP-hard问题。因此,该文选用将遗传算法引入排课问题中,首先对排课问题进行了描述,在此基础上提出了一种基于遗传算法的排课算法,并对其进行了仿真实验,最后较快的找到了问题的最优解或次优解。     

Packing问题的计算复杂性

本文讨论了离散模型与连续问题的关系以及图灵机的计算能力,在此基础上扩充了问题及NP完全问题的定义,根据解空间的拓扑结构特点将NP完全的Packing问题分为三类,并对多边形Packing问题进行了有益的探讨。这对设计Packing问题的求解算法具有借鉴意义。     

求解SAT问题的算法的研究进展

SAT问题是研究最广泛的NPC问题之一。由于SAT问题本身的特性,除非P=NP,否则不存在最坏情况下多项式阶时间复杂度的SAT求解算法。因此设计出高效快速的SAT求解算法至今仍是研究热点。首先简要介绍了SAT问题;其次从完备算法、不完备算法和组合算法3个角度总结了新近的研究进展,深入分析了已有算法解决SAT问题的基本流程,并从适用问题类别、算法特点、求解效率等方面对各类先进的求解器进行了对比分析;最后讨论了求解SAT问题的算法面临的挑战,并对下一步研究工作进行了展望。     

线性系统的同时镇定问题

线性系统的同时镇定问题,是系统与控制理论中的基本问题,有着广泛的理论意义和应用价值.本文介绍了线性系统同时镇定问题的研究现状和最新进展.首先回顾了同时镇定问题的研究内容、基本方法及相关结果.其次,从理论求解和控制器设计的角度对线性系统同时镇定研究中著名的"香槟问题","比利时巧克力问题"和"威士忌问题"进行了分析探讨,并基于不等式型定理机器证明理论,给出了线性系统同时镇定问题的相关工作.最后指出了对于同时镇定多个线性系统方面的若干研究方向.     

矩形的三角形划分问题研究

给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。     

奇异系统的输出稳定化通过一般状态反馈的可解性

讨论了奇异系统的输出稳定化问题，得到了在初始值为容许且不保证闭环正则的情形下，通过一般状态反馈求解此问题的充要条件及计算步骤     

Equivalence of nonlinear systems to triangular form: the singular case

The problem of state equivalence of a given nonlinear system to a triangular form is considered here. The solution of this problem has been known for the regular case, i.e. when there exists a certain nested sequence of regular and involutive distributions. It is also known that in this case the corresponding system is linearizable using a smooth coordinate change and static state feedback. This paper deals with the singular case, i.e. when the nested sequence of involutive distributions of the system contains singular distributions. Special attention is paid to the so-called bijective triangular form. Geometric, coordinates-free criteria for the solution of the above problem as well as constructive, verifiable procedures are given. These results are used to obtain a result in the nonsmooth stabilization problem.     

Optimal singular control for nonlinear semistabilisation

The singular optimal control problem for asymptotic stabilisation has been extensively studied in the literature. In this paper, the optimal singular control problem is extended to address a weaker version of closed-loop stability, namely, semistability, which is of paramount importance for consensus control of network dynamical systems. Three approaches are presented to address the nonlinear semistable singular control problem. Namely, a singular perturbation method is presented to construct a state-feedback singular controller that guarantees closed-loop semistability for nonlinear systems. In this approach, we show that for a non-negative cost-to-go function the minimum cost of a nonlinear semistabilising singular controller is lower than the minimum cost of a singular controller that guarantees asymptotic stability of the closed-loop system. In the second approach, we solve the nonlinear semistable singular control problem by using the cost-to-go function to cancel the singularities in the corresponding Hamilton–Jacobi–Bellman equation. For this case, we show that the minimum value of the singular performance measure is zero. Finally, we provide a framework based on the concepts of state-feedback linearisation and feedback equivalence to solve the singular control problem for semistabilisation of nonlinear dynamical systems. For this approach, we also show that the minimum value of the singular performance measure is zero. Three numerical examples are presented to demonstrate the efficacy of the proposed singular semistabilisation frameworks.     

Continuous-time singular linear–quadratic control: Necessary and sufficient conditions for the existence of regular solutions

The purpose of this paper is to provide a full understanding of the role that the constrained generalized continuous algebraic Riccati equation plays in singular linear–quadratic (LQ) optimal control. Indeed, in spite of the vast literature on LQ problems, only recently a sufficient condition for the existence of a non-impulsive optimal control has for the first time connected this equation with the singular LQ optimal control problem. In this paper, we establish four equivalent conditions providing a complete picture that connects the singular LQ problem with the constrained generalized continuous algebraic Riccati equation and with the geometric properties of the underlying system.     

Semi-global robust output regulation for a class of singular nonlinear systems via nonlinear internal model

Most of existing results on robust output regulation problem of singular nonlinear systems are limited to local solutions. In this paper, the semi-global robust output regulation problem for a class of singular nonlinear systems is investigated by using a nonlinear internal model. Attaching a nonlinear internal model to the singular nonlinear system yields an augmented singular nonlinear system whose semi-global robust stabilisation solution leads to the solution of the semi-global robust output regulation problem of the original singular nonlinear system. The solvability conditions of the semi-global output regulation problem are established by addressing the solvability of the robust stabilisation problem of augmented singular nonlinear system. Finally, a numerical simulation example is used to illustrate the design of the semi-global regulator for the singular nonlinear systems.     

Solution of output regulation of singular nonlinear systems bynormal output feedback

The output regulation problem of singular nonlinear systems via the normal output feedback control has been a challenging problem. Existing approaches for solving this problem employed techniques similar to those used for linear singular systems. Results from these approaches either rely on a normalizability assumption or are limited to systems with special structures. This paper gives a complete solution for this problem by employing a novel approach that is also interesting for linear systems     

首系数奇异的二阶系统解耦

针对首系数奇异的二阶系统的解耦问题,提出了一种奇异二阶系统的同谱构造解耦方法。引入了对逆二阶系统,将难以描述的二阶系统无穷大特征值转化为其对逆二阶系统的零特征值来加以描述,分析了奇异二阶系统可对角化应该满足的条件及其相应的证明,并且给出了一种具体的奇异二阶系统的同谱构造解耦方法,从而实现了奇异二阶系统解耦,即将奇异二阶系统的3个参数矩阵同时对角化。数值试验中将一个三自由度的奇异质量弹簧二阶系统解耦成3个无关的单自由度二阶子系统,而且解耦前后系统不仅保持了相同的有限特征值及其重复度结构,还保持了相同的无限特征值及其重复度结构。工程应用前景十分广泛。     

广义系统干扰解耦的正则状态观测器

本文在文[1]的基础上进一步讨论了含有未知输入(或外部干扰)的广义系统Ex=Ax+Bu+Mf,y=Dx的正则状态观测器问题。结果表明:只要这样的观测器存在,则也可将其设计化为一个低于rankE阶的正则系统的相应问题。     

Nilpotentization of the kinematics of the n-trailer system at singular points and motion planning through the singular locus

We propose in this paper a constructive procedure that transforms locally, even at singular configurations, the kinematics of a car towing trailers into Kumpera-Ruiz normal form. This construction converts the non-holonomic motion planning problem into an algebraic problem (the resolution of a system of polynomial equations), which we illustrate by steering the two-trailer system in a neighbourhood of singular configurations. We show also that the n-trailer system is a universal local model for all Goursat structures and that all Goursat structures are locally nilpotentizable.