决策粗糙集属性约简算法与属性核研究

属性约简是粗糙集理论的重要研究内容之一。在Pawlak粗糙集模型中,正区域大小随着属性增多而变大,呈现单调性。然而,在决策粗糙集模型中,概率正区域与属性集之间不具有单调性,从而产生各种属性约简定义。为此,深入研究了决策粗糙集属性约简问题,阐述了几种约简定义之间的关系,证明了保持局部最大概率正区域的约简具有较大的代价,指出了保持所有对象的正决策不变的约简呈现稳定性和存在属性核。     

决策系统属性约简优化算法研究

属性约简是粗糙集理论研究的关键问题,针对求取决策系统所有约简的NP问题,基于差别矩阵提出一种决策系统属性约简优化算法.通过改进差别矩阵得到差别集,在获得核与约简候选信息基础上,以属性频度作为启发式信息,快速有效地求取决策系统的所有约简.分析表明了该算法的可行性与有效性.     

一种改进的规则获取方法

属性约简和属性值约简是基于粗糙集理论获取决策规则的基础,在分析经典约简算法的基础上,根据粗糙集理论中属性的依赖度和重要度等性质,提出一种改进的约简方法,以获取简洁的决策规则。并运用实例对方法的有效性进行分析和验证。     

基于遗传算法的粗糙集属性约简算法

属性约简是粗糙集理论中的一个核心问题，为了有效获取属性最小相对约简，本文提出了一种基于遗传算法的粗糙集属性约简算法．该算法将核引入遗传算法的初始群体来提高算法的性能，依照决策属性对条件属性的依赖度，在加强局部搜索能力的同时保持了该算法全局寻优的特性，能够获得最佳的搜索效果．实验结果证明了该算法能够快速有效的进行属性约简。     

基于粗糙集的决策表属性约简方法的研究

求核和属性约简是粗糙集理论研究的一个核心问题。文中主要针对现有的一些决策表属性约简算法存在的不足,尤其是基于信息熵的属性约简算法在较大数据集上效率不高的问题提出改进。主要通过结合粗糙集的相关理论来改进原有的属性约简算法在求核中的约束条件,进而在原有算法的基础上提出了一种改进算法。在求约简属性集时,利用新提出的约简算法,使计算复杂度降低,同时保持了高效的决策准确率。实验结果表明改进后的决策表属性约简方法能够更加快速有效地找到约简集。     

基于差别矩阵的双射软决策系统的约筒

在GongK等人给出双射软集和双射软决策系统概念的基础上,提出基于差别矩阵的求双射软决策系统约简的方法。利用差别矩阵的一些性质,把粗糙集理论中的约简方法应用到双射软决策系统中,既简化了求约简的过程,又推广了粗糙集理论中的约简方法。     

保正域的决策粗糙集属性约简

针对决策粗糙集模型,分析了它的正域随条件属性删除时的变化特点,即当条件属性集变小时,决策粗糙集的正域不但会变大,而且可能保持不变或变小。讨论了现有几种与正域相关的决策粗糙集属性约简定义的优缺点,在此基础上提出一种新的保正域不变的决策粗糙集属性约简。计算实例发现,现有基于差别矩阵的决策粗糙集属性约简方法不能求到它的所有保正域约简。上述研究结果说明,决策粗糙集模型与经典粗糙集模型的属性约简问题完全不同,因此不能简单地将经典粗糙集的方法平行推广到决策粗糙集模型上。该文的结论为将来系统研究决策粗糙集模型中的属性约简问题提供了很好的小结和理论基础。     

基于位运算的属性核约简

属性约简是粗糙集理论中的一个重要内容，其核心任务是得到属性集的核，它是属性约简的基础，文中提出了基于位运算的新的核约简算法。与传统算法相比，其速度更快，效率更高，且易于计算机实现，为扩展粗糙集的应用提供了理论基础。     

基于回溯搜索算法的决策粗糙集属性约简

属性约简是粗糙集理论的核心问题,为了获得更多更稳定的最小属性约简,根据决策粗糙集模型将最小属性约简问题转化为决策风险最小化问题,并给出了新的适应度函数计算方法;在此基础上利用回溯搜索算法较强的全局搜索性能,提出了基于回溯搜索算法的决策粗糙集属性约简算法;对UCI数据集的实验结果以及与其他约简算法的比较表明,该算法能够得到更多的最小属性约简,而且能够在多次运行中保持约简结果个数的稳定性。     

基于分形维数的非常规决策表的属性约简

属性约简是粗糙集的一个核心研究课题,但经典属性约简及其延伸算法是基于有决策属性的决策表的属性约简算法,它们对无决策属性的非常规决策表的属性约简无能为力。以粗糙集理论为基础,对无决策属性的非常规决策表从分形维数方面进行研究,提出了一种适用于无决策属性的决策表的启发式属性约简算法。该算法在一定程度上能够解决非常规决策表的属性约简问题,进一步扩展了粗糙集理论的应用范围。实例表明该算法是有效可行的。     

基于图灵模型的P=？ NP问题分析

P=？NP问题是计算复杂性中的核心问题。2000年,美国克雷实验室将其收录为“千禧年大奖”七个问题之首。本文基于图灵模型,对P=？NP问题的研究现状、P=NP／P≠NP 证明方法、NPC问题求解方法及研究进展进行阐述。     

关于同步部分规约的有限自动机的优化问题的近似难度

自动机是可同步的是指它具有满足以下性质的同步字:不论自动机当前所处的状态,以同步字为输入执行后它一定会到达某个特定状态。同步自动机问题的核心是计算最短同步字。聚焦于这一核心问题,文中就一类称为部分规约的确定的有限自动机的最短同步字问题,研究了近似计算这类自动机的最短同步字的复杂性,即近似计算它的难度,该工作有助于其近似算法的分析与设计。通过建立由两个优化问题(MAX SAT问题以及MAX FA-INT问题)到最短同步字长度计算这一问题(即Shortest-Syn)的归约,利用与概率可检验证明(Probabilistically Checkable Proofs,PCP)定理和概率可检验辩论(Probabilistically Checkable Debate,PCD)定理有关的若干结果证明了文中的主要结论:对于部分规约的确定的有限自动机,在某个近似因子内Shortest-Syn的近似难度是NP-难的和PSPACE-难的,除非NP和PSPACE分别坍塌到P。     

Complexity of the Exact Domatic Number Problem and of the Exact Conveyor Flow Shop Problem

We prove that the exact versions of the domatic number problem are complete for the levels of the boolean hierarchy over NP. The domatic number problem, which arises in the area of computer networks, is the problem of partitioning a given graph into a maximum number of disjoint dominating sets. This number is called the domatic number of the graph. We prove that the problem of determining whether or not the domatic number of a given graph is exactly one of k given values is complete for BH_2k(NP), the 2kth level of the boolean hierarchy over NP. In particular, for k = 1, it is DP-complete to determine whether or not the domatic number of a given graph equals exactly a given integer. Note that DP = BH₂(NP). We obtain similar results for the exact versions of generalized dominating set problems and of the conveyor flow shop problem. Our reductions apply Wagner's conditions sufficient to prove hardness for the levels of the boolean hierarchy over NP.     

求解三角形Packing问题的拟物策略

NP难度问题的求解一直是计算机科学技术的一个瓶颈任务。自20世纪70年代以来的研究结果表明,求解NP难度问题不存在既完整严格又不太慢的求解算法。三角形Packing问题是NP难的。给出了泊位的定义,并给出了求解三角形Packing问题的拟物策略。以拟物策略为基础发展出拟物算法。实验结果表明,拟物算法具有较高的完整性。     

Two‐node‐connected star problem

In this study, a two‐node‐connected star problem (2NCSP) is introduced. We are given a simple graph and internal and external costs for each link of the graph. The goal is to find the minimum‐cost spanning subgraph, where the core is two‐node‐connected and the remaining external nodes are connected to the core. First, we show that the 2NCSP belongs to the class of NP‐hard computational problems. Therefore, a greedy randomized adaptive search procedure (GRASP) heuristic is developed, enriched with a variable neighborhood descent (VND). The neighborhood structures include exact integer linear programming models to find the best paths and two‐node‐connected replacements, as well as a shaking operation in order to prevent being trapped in a local minima. The ring star problem (RSP) represents a relevant model in network optimization, where the core is a ring instead of an arbitrary two‐node‐connected graph. We contrast our GRASP/VND methodology with a previous reference work on the RSP in order to highlight the effectiveness of our heuristic. The heuristic is competitive, and the best results produced for several instances so far are under study. In this study, a discussion of the results and trends for future work are provided.     

Inapproximability of the kidney exchange problem

To overcome the shortage of kidneys available for transplantation, several countries have started various programmes of kidney exchanges between incompatible patient-donor pairs. This situation can be modeled as a cooperative game in which the players are the patient-donor pairs and their preferences are derived in the first step from the suitability of the donated kidney and in the second step from the length of the obtained cycle of exchanges. Although the core of such a cooperative game is always nonempty and one core solution can be found by the famous Top Trading Cycles algorithm, many questions concerning the structure of the core are NP-hard. In this paper we show that the problem of finding a core permutation that maximizes the number of patients who obtain a suitable kidney is not approximable within n1−ε for any ε>0 unless P=NP.     

基于欧氏距离的矩形Packing问题的确定性启发式求解算法

使用拟人的策略,提出了基于欧氏距离的占角最大穴度优先的放置方法,为矩形Packing问题的快速求解提供了一种高效的启发式算法.算法的高效性通过应用于标准电路MCNC和GSRC得到了验证.     

P vs. NP问题研究状态及其对密码学的意义

介绍P vs.NP问题的研究状态以及P vs.NP问题的研究对于密码学的意义。主要内容包括关于证明P≠NP的主要研究方法和相关工作,关于证明P=NP的主要研究方法和相关工作,关于求解NP完全问题的相关方法,以及P vs.NP问题研究与密码学的关系。由于现代密码学建立在未知密钥情况下不存在有效的算法将明文消息从密文中提取出来的假定之上,因此安全加密算法存在的一个必要条件是P≠NP。如果P=NP,根据Cook的观点,现代密码体制将崩溃。依据P=NP的假定,给出一个可能的密码分析模型。     

经典Ramsey数DNA计算模型(Ⅰ):位序列计算模型

Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一．对于经典Ramsey数,至今只有9个Ramsey数得到解决．按照传统的算法,其搜索空间太大,当前的电子计算机无法胜任．研究表明,DNA计算在求解困难的NP一完全问题上优于电子计算机．目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型．作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解．全文共分两篇,该文属首篇,建立了一种可适用于DNA计算模式的所谓的求解Ramsey数的位序列计算模型,其中的位序列是以图的相邻矩阵下三角阵中行从左到右、列从上到下的排列次序．文中重点对该模型的机理与使用方法进行了分析研究．