一个不受常量序限制的归纳逻辑程序设计算法

文章分析了FOIL（first－orderinductivelearner）递归谓词学习算法理论上的不足以及由此导致的应用范围的局限,并通过两个例子给予详细说明．为了克服这一缺陷,文章引入了反映递归规则集R与实例空间E本质关系的实例图H（R．E）和实例序的概念,奠定了算法的理论基础．在此基础上,给出了基于实例图的FOILPlus算法．算法通过对悬例、悬弧的操作把握住实例序,自然而然地防止了病态递归规则的产生,从而保证了FOILPlus可以不受常量序限制地完成学习任务;同时,算法的时空复杂度较之FOIL算法没有增加．FOILPlus算法已经编程实现,并用它尝试了两个FOIL学习失败的递归任务,都获得了成功．     

一种基于ILP和ASP的学习B语言描述的动作模型方法

动作模型学习可以使Agent主动适应动态环境中的变化,从而提高Agent的自治性,同时也可为动态域建模提供一个初步模型,为后期的模型完善和修改提供了基础.通过结合归纳逻辑程序设计(Inductive Logic Program-ming,ILP)和回答集程序设计(Answer Set Programming,ASP),设计了一个学习B语言描述的动作模型算法,该算法可以在混合规模的动态域中进行学习,并采用经典规划实例验证了该学习算法的有效性.     

基于多核学习的双稀疏关系学习算法

在关系学习中样本无法在R n空间中表示.与其他机器学习问题有很大不同,因为无法利用R n空间的几何结构使得其解决异常困难.将多核学习方法用于关系学习中. 首先,可以证明当用逻辑规则生成的核矩阵进行多核学习时,其他核都可以等价转化为线性核.在此基础上,通过用修正FOIL算法迭代生成规则,构造相应的线性核然后进行多核优化,由此实现了由规则诱导出的特征空间上的线性分类器.算法具有"双稀疏"特性,即:可以同时得到支持向量和支持规则.此外,可以证明在规则诱导出的特征空间上的多核学习可以转化为平方l1 SVM,这是首次提出的新型SVM算法.在6个生物化学和化学信息数据集上与其他算法进行了对比实验.结果表明不仅预测准确率有明显提高,而且得到的规则集数目更小,解释更为直接.     

支持向量机序贯最小优化算法推导的改进

已有文献中的支持向量机SMO算法推导过程计算复杂,该文给出一个简洁推导。整个推导过程没有复杂的计算,除了误差函数外,不需引入其它中间变量。     

序关系优化的多超平面排序学习模型

在经典排序学习模型RankSVM的基础上,提出一种序关系优化的多超平面排序模型。该模型首先根据训练数据所属等级之间的序关系进行多个超平面的构建,然后将多个超平面得到的排序列表进行聚合获得最终的排序结果。在LETOR OHSUMED数据集上对所提出的模型进行实验测试,使用信息检索领域的多个经典指标对模型的性能进行评测,并与RankSVM等方法进行比较。实验结果显示该模型不仅获得更优的排序性能,而且能显著缩短训练时间。     

基于分支定界-改进AO~*算法的序贯测试策略优化

针对经典AO*算法在求解序贯测试问题中复杂度太大的难题,提出测试选择与策略优化联合的方法;首先基于解析冗余关系(ARRs)把测试选择问题映射为一个特殊的0-1整数规划(IP)模型并用分支定界法求解之,得到最优测试;然后通过两步回溯改进的AO*算法确定最优测试顺序;在一个组合电路的应用表明算法优化了测试点数,减少了扩展节点数,降低了经典算法的复杂度。     

An Approximation Algorithm for Circular Arc Colouring

We consider the problem of colouring a family of n arcs of a circle. This NP-complete problem, which occurs in routing and network design problems, is modelled as a 0-1 integer multicommodity flow problem. We present an algorithm that routes the commodities in the network by augmenting the network with some extra edges which correspond to extra colours. The algorithm, which relies on probabilistic techniques such as randomized rounding and path selection, is a randomized approximation algorithm which has an asymptotic performance ratio of 1+1/e (approximately 1.37) except when the minimum number of colours required is very small (O(\ln n) ). This is an improvement over the best previously known result [7], which is a deterministic approximation algorithm with a performance ratio of 3/2. The substantial improvement is valuable, for instance in wavelength allocation strategies in communication networks where bandwidth is a precious resource. Received October 25, 1998; revised August 26, 1999, and April 17, 2000.     

最新ILP微处理器的设计特点及分析

文章综述了指令级并行（ILP）微处理器的特点,着重介绍了第七代X86、Itanium、E2K等ILP微处理器的体系结构和所采用的新技术,分析了它们各自的特点和问题,并对ILP微处理器的发展方向进行了探讨。     

An Algorithm for Enumerating All Spanning Trees of a Directed Graph

We present an O(NV + V ³ ) time algorithm for enumerating all spanning trees of a directed graph. This improves the previous best known bound of O(NE + V+E) [1] when V ² =o(N) , which will be true for most graphs. Here, N refers to the number of spanning trees of a graph having V vertices and E edges. The algorithm is based on the technique of obtaining one spanning tree from another by a series of edge swaps. This result complements the result in the companion paper [3] which enumerates all spanning trees in an undirected graph in O(N+V+E) time. Received September 11, 1997; revised March 6, 1998.     

平面圆簇围域边界程序画法

描述了一种在电子地图上实时标绘一簇平面圆形所围区域边界的算法。该算法采用先将圆簇以半径和圆心距分类,减少计算量;再运用解析几何的方法求出圆周上的交点集合并排序;然后依据几何关系找出判断解决问题。文中所述问题有许多应用场合。     

确定平面直线图完全单调链集的算法

本文提出求平面直线图完全单调链集的一种算法。基本思想是,先求平面直线图Ｇ的顶点集的凸壳及其直径,然后求各顶点在直径上垂直投影点,并按投影点的ｘ（或ｙ）坐 标排序Ｇ的顶点,最后按一定规则找出完全单调链集。     

一种新的与线网顺序无关的随机优化总体布线算法

针对目前总体布线中仍然存在的3个关键问题;布线结果受布线顺序的影响、总体布线图中拥挤区域的不可预见性、线网连接式样受到算法的限制等,该文提出了一种新的不受线网顺序影响的总体布线算法,并实现了相应的总体布线器RINO－Router。该算法采用随机优化方法来保 证先后被拆线重布的线网有相同的通过拥挤区域的机会,并能得到GRG边的拥挤度估计值;采用高效的Steiner树改造算法构造避开拥挤区域的布线树,采用典型电路实例进行了测试,并将布线结果与基于多商品流算法的总体布线器Matula-Router进行了对比。结果表明,RINO－Router能够在短得多的运行时间内求得质量与Matula-Router相近的总体布线解。     

Visualizing SAT Instances and Runs of the DPLL Algorithm

SAT-solvers have turned into essential tools in many areas of applied logic like, for example, hardware verification or satisfiability checking modulo theories. However, although recent implementations are able to solve problems with hundreds of thousands of variables and millions of clauses, much smaller instances remain unsolved. What makes a particular instance hard or easy is at most partially understood – and is often attributed to the instance’s internal structure. By converting SAT instances into graphs and applying established graph layout techniques, this internal structure can be visualized and thus serve as the basis of subsequent analysis. Moreover, by providing tools that animate the structure during the run of a SAT algorithm, dynamic changes of the problem instance become observable. Thus, we expect both to gain new insights into the hardness of the SAT problem and to help in teaching SAT algorithms.     

一种实现区域覆盖的图形拾取算法

为了准确拾取区域覆盖情况下的图形，逐步分析并给出了决定图形拾取与否的三个条件：拾取点是否落在图形的可拾取区域内、拾取点到图形的最短距离是否为最小、拾取点所在的图形的拾取区域面积是否最小。通过对这三个条件的依次判断，提出一种将最短距离与面积结合的方式来实现区域覆盖情况下的图形拾取算法，高效而快捷地实现了图形的拾取。     

An Efficient Parallel Algorithm for the Layered Planar Monotone Circuit Value Problem

A planar monotone circuit (PMC) is a Boolean circuit that can be embedded in the plane and that contains only AND and OR gates. A layered PMC is a PMC in which all input nodes are in the external face, and the gates can be assigned to layers in such a way that every wire goes between gates in successive layers. Goldschlager, Cook and Dymond, and others have developed NC ² algorithms to evaluate a layered PMC when the output node is in the same face as the input nodes. These algorithms require a large number of processors (Ω(n ⁶ ), where n is the size of the input circuit). In this paper we give an efficient parallel algorithm that evaluates a layered PMC of size n in time using only a linear number of processors on an EREW PRAM. Our parallel algorithm is the best possible to within a polylog factor, and is a substantial improvement over the earlier algorithms for the problem. Received April 18, 1994; revised April 7, 1995.