共查询到20条相似文献,搜索用时 187 毫秒
1.
On Unknown Small Subsets and Implicit Measures: New Techniques for Parameterized Algorithms 下载免费PDF全文
Parameterized computation is a recently proposed alternative approach to dealing with NP-hard problems.Developing efficient parameterized algorithms has become a very active research area in the current research in theoretical computer science. In this paper, we investigate a number of new algorithmic techniques that were proposed and initiated by ourselves in our research in parameterized computation. The techniques have proved to be very useful and promising,and have led to improved parameterized algorithms for many well-known NP-hard problems. 相似文献
2.
Evolutionary computation has experienced a tremendous growth in the last decade in both theoretical analyses and industrial applications. Its scope has evolved beyond its original meaning of "biological evolution" toward a wide variety of nature inspired computational algorithms and techniques, including evolutionary, neural, ecological, social and economical computation, etc, in a unified framework. Many research topics in evolutionary computation nowadays are not necessarily "evolutionary". This paper provides an overview of some recent advances in evolutionary computation that have been made in CERCIA at the University of Birmingham, UK. It covers a wide range of topics in optimization, learning and design using evolutionary approaches and techniques, and theoretical results in the computational time complexity of evolutionary algorithms. Some issues related to future development of evolutionary computation are also discussed. 相似文献
3.
张晓龙 《计算机科学技术学报》2002,17(5):0-0
Knowledge acquisition with machine learning techniques is a fundamental requirement for knowledge discovery from databases and data mining systems.Two techniques in particular-inductive learning and theory revision-have been used toward this end.A method that combines both approaches to effectively acquire theories (regularity) from a set of training examples is presented.Inductive learning is used to acquire new regularity from the training examples;and theory revision is used to improve an initial theory.In addition,a theory preference criterion that is a combination of the MDL-based heuristic and the Laplace estimate has been successfully employed in the selection of the promising theory.The resulting algorithm developed by integrating inductive learning and theory revision and using the criterion has the ability to deal with complex problems,obtaining useful theories in terms of its predictive accuracy. 相似文献
4.
ZHU Ding-ju 《通讯和计算机》2009,6(4):42-46
Traditional spatial-temporal mode is based on serial computing. Currently the scale of spatial-temporal problems requiring attention has exceeded the capacity of series computation, I propose parallel spatial-temporal mode to divide big spatial-temporal problems, which a single computing node does not have the ability to process, into many small spatial-temporal problems that can be distributed onto many parallel computing nodes and be parallel processed. These nodes are small enough for each parallel computing node to finish the simulation in a practical time frame. Such processing demonstrates that parallel spatial-temporal mode provides a way to solve the very large or real-time spatial-temporal problems in spatial-temporal GIS applications that cannot be processed by traditional (serial) spatial-temporal mode. 相似文献
5.
YANG Lu 《计算机科学技术学报》1999,14(5):434-446
Automated theorem proving on inequalities is always considered as a difficult topic in the area of automated reasoning.The relevant algorithms depend fundamentally on real algebra and real geometry,and the computational complexity increases very quickly with the dimension,that is,the number of parameters.Some well-known algorithms are complete theoretically but inefficient in practice,which cannot verify non-trivial propositions in batches.A dimension-decreasing algorithm presented here can treat radicals efficiently and make the dimensions the lowest. Based upon this algorithm,a generic program called “BOTTEMA”was implemented on a personal computer.More than 1000 algebraic and geometric inequalities including hundreds of open problems have been verified in this way.This makes it possible to check a finite many inequalities instead of solving a global-optimization problem. 相似文献
6.
Reinforcement learning (RL) in real-world problems requires function approximations that depend on selecting the appropriate feature representations. Representational expansion techniques can make linear approximators represent value functions more effectively; however, most of these techniques function well only for low dimensional problems. In this paper, we present the greedy feature replacement (GFR), a novel online expansion technique, for value-based RL algorithms that use binary features. Given a simple initial representation, the feature representation is expanded incrementally. New feature dependencies are added automatically to the current representation and conjunctive features are used to replace current features greedily. The virtual temporal difference (TD) error is recorded for each conjunctive feature to judge whether the replacement can improve the approximation. Correctness guarantees and computational complexity analysis are provided for GFR. Experimental results in two domains show that GFR achieves much faster learning and has the capability to handle large-scale problems. 相似文献
7.
Angsheng Li 《International Journal of Software and Informatics》2011,5(4):547-548
This is a special issue with special interest in computability and computational
complexity with extensions to information and network analysis. It consists of seven
invited submissions each of which is carefully reviewed.
The paper entitled: The future of computer science by John E. Hopcroft, Sucheta
Soundarajan, and Liaoruo Wang, surveys some important topics and paradigm shift
in computer science with the new focus on large-scale data and network analysis.
The paper entitled: Holographic reduction: A domain changed application and
its partial converse theorems by Mingji Xia arises the new problem of the converse of
Valiant''s holographic reductions, and partially answers this question, which makes a
significant contribution to the theory of holographic computation.
The paper entitled: On strings with trivial Kolmogorov complexity by George
Barmpalias studies the degree theoretic complexity of sets of strings with low algorithmic complexity, building a few fundamental results in the area of algorithmic
randomness.
The paper entitled: Color-Coding and its applications: A survey by Jianxin
Wang, Qilong Feng, Jianer Chen, describes a comprehensive survey on this important
topic of parameterized computation.
The paper entitled: Rent-or-Buy network design problem and the Sample-Augment
algorithm: A survey by Peng Zhang, gives a survey on approximation algorithms of
the recently active topic of the rent or buy network design.
The paper entitled: Kalimulin pairs of ** w-enumeration degrees by Ivan N.
Soskov and Mariya I. Soskov studies the new phenomena of omega-enumeration degrees which is a natural extension of the classical enumeration degrees.
The paper entitled: A toolkit for generating sentences from context-free grammars by Zhiwu Xu, Lixiao Zheng, and Haiming Chen, presents a toolkit for parsing
context-free grammars and generating valid sentences.
I would like to thank all authors for their contribution to this excellent issue,
which reflects both our traditional research on computability and computational complexity and the extensions of the theory to information and networks.
I am grateful to Prof. Ruqian Lu for inviting me to organize this special issue,
and thank both Professor Ruqian Lu and the members of the Editorial Board of
the International Journal of Software and Informatics for cooperation throughout the
preparation of this special issue. 相似文献
8.
The Traveling Salesman Problem(TSP) is one of the most difficult problems that many scholars all over the world are studying.This paper points out the disparity between the definition and the classical solution of TSP and its practical applications,and the presents a new definition of TSP and its effective algorithm conforming to practical applications,thus making TSP practically more valuable. 相似文献
9.
A class of new fuzzy inference systems New-FISs is presented. Compared with the standard fuzzy system, New-FIS is still a tmiversal approximator and has no fuzzy rule base and linearly parameter growth. Thus, it effectively overcomes the second “curse of dimensionahty” : there is an exponential growth in the number of parameters of a fuzzy system as the numberof input variables, resulting in surprisingly reduced computational complexity and being especially suitable for applications, where the complexity is of the first importance with respect to the approximation accuracy. 相似文献
10.
基于约束理论的Flow-shop分解协调算法 总被引:2,自引:0,他引:2
There are many flow shop problems of throughput (denoted by FSPT) with constraints of due date in real production planning and scheduling. In this paper, a decomposition and coordination algorithm is proposed based on the analysis of FSPT and under the support of TOC (theory of constraint). A flow shop is at first decomposed into two subsystems named PULL and PUSH by means of bottleneck. Then the subsystem is decomposed into single machine scheduling problems, so the original NP-HARD problem can be transferred into a serial of single machine optimization problems finally. This method reduces the computational complexity, and has been used in a real project successfully. 相似文献
11.
Set Cover和Hitting Set问题是两个重要的W[2]完全问题。Set Cover问题在大规模集成电路设备的测试和人员调度等领域有着广泛的应用,Hitting Set问题在生物计算等领域有着重要的应用。在引入参数计算和复杂性理论后,Set Cover和Hitting Set问题再次成为研究的热点。首先介绍Set Cover和Hitting Set的各种分类问题及其定义,并对各种分类问题的计算复杂性和相关算法的研究进展加以分析总结,给出(k,h)-Set Cover和(k,d)-Set Cover问题的复杂性证明。最后总结全文并提出进一步研究的方向。 相似文献
12.
Steiner树问题是经典的NP难解问题,在计算机网络布局、电路设计以及生物网络等领域都有很多应用。随着参数计算理论的发展,已经证明了无向图和有向图中的Steiner树问题都是固定参数可解的(FPT)。介绍了无向图和有向图中Steiner树问题的近似算法和参数算法,分析了一些特殊Steiner树问题的研究现状,还讨论了顶点加权Steiner树问题的研究进展。最后,提出了该问题的进一步研究方向。 相似文献
13.
反馈集问题是经典的NP难问题,在电路测试、操作系统解死锁、分析工艺流程、生物计算等领域都有重要应用,按照反馈集中元素类型可分为反馈顶点集(FVS)问题和反馈边集(FAS)问题。人们利用线性规划和局部搜索等技术设计了一系列关于FVS和FAS问题的近似算法,并基于分枝一剪枝策略和加权分治技术提出了FVS问题的精确算法。随着参数计算理论的发展,近年来参数化反馈集问题引起了人们的重视,并取得了很大突破。目前已经证明了无向图和有向图中FVS问题和FAS问题都是固定参数可解的(FPT)。利用树分解、分支搜索、迭代压缩等技术,对无向图FVS问题提出了一系列FPT算法。针对某些特殊的应用,人们开展了对具有特殊性质的图上FVS问题的研究,提出了一些多项式时间可解的精确算法。现首先介绍了在无向图中关于FVS问题的近似算法与精确算法,然后具体分析了FVS问题的参数化算法。进一步阐述了关于有向图和特殊图上FVS问题的研究现状,介绍了FAS问题的研究成果。基于对反馈集问题研究现状的分析,提出了今后FVS问题研究中值得关注的几个方面。 相似文献
14.
15.
16.
17.
超平面覆盖问题是计算几何领域中一类典型的NP难问题,在实际生活中有着广泛的应用.针对NP难问题的难解性,人们提出了一些传统的方法用来求解这些NP难问题.但由于这些方法具有各自的局限性,不能满足实际应用中的各种需求,人们从新的理论角度为固定参数可解的NP难问题设计参数算法.通过深入分析直线覆盖问题(超平面覆盖问题的一个特例)的结构特征,并利用深度有界搜索树的方法,提出了一个时间复杂度为O(k3(0.736k)k+nlogk)的确定性参数算法,极大地改进了当前最好的结果O((k/2.2)2k+nlogk).通过对上述算法在高维空间中的进一步扩展,提出了关于超平面覆盖问题时间复杂度为O(dkd+1(dk)!/((d!)kk!)+nd+1)确定性参数算法,对当前的最好结果O(kd(k+1)+nd+1)有较大改进. 相似文献
18.
N-body问题涉及了科学和工程中的许多领域,它的主要特点就是O(N~2)的计算量,采用并行计算方法是解决N-body问题巨大计算量的终极选择。针对该类问题的具体特点以及不同的并行计算机体系结构,目前有多种算法有效地减少了计算量,加快了求解速度。本文介绍了N-body问题的几种常见算法和它们的并行化方法。 相似文献
19.
集合包含与几何包含的多方保密计算 总被引:6,自引:0,他引:6
多方保密计算是近几年国际密码学界研究的一个热点问题.研究了保密的集合包含与几何包含问题,提出集合包含问题的多方保密计算方案,在此基础上结合Montecarlo方法与cantor编码方法,提出了任意几何图形包含问题的近似多方保密计算方案.并利用模拟范例证明了方案的安全性.同已有的方案相比,提出的方案适用范围广、通信复杂性低;在解决已有方案可解决的同样问题时,某些情况下计算复杂性也比较低. 相似文献