Longest (s,t)-paths in L-shaped grid graphs

The longest path problem, that is, finding a simple path with the maximum number of vertices, is a well-known NP-hard problem with many applications. However, for some classes of graphs, including solid grid graphs and grid graphs with some holes, it is open. An L-shaped grid graph is a special kind of a rectangular grid graph with a rectangular hole. In this paper, we show that a longest path between two given vertices s and t of an L-shaped grid graph can be computed in linear time.     

一种无回溯的最长前缀匹配搜索算法

研究网络处理器中的搜索算法,提出一种基于Patricia树的无回溯搜索算法,并进行仿真和评估分析。该算法被用于中科院计算所的网络处理器的搜索引擎的设计中,该搜索引擎可以运行在155.9 MHz的XC2VP30 FPGA上,占用421个LUT,当频率为100 MHz时,每秒可以执行约7 000 000次搜索操作,实现了资源消耗和性能的折中。     

采用双向搜索在多权值路网中查找较优长路径

求解最短路径是图研究中的一个经典问题。目前大多数相关研究都假设图中每条边只有一种权值。然而在实际应用中,有时候图中的边设有多种权值,求解最短路时需要综合计算多种权值,并采用用户自定义的聚合函数f将路径的多种权值映射到一个实数上,用以比较路径的长短。当f不是线性函数时,最短路的子路不一定也是最短路,于是大部分求解最短路的算法对此问题并不适用。文中提出了一种双向搜索方法,用以在多权值路网中求解最短路近似解。实验表明,本方法适用于长路径查询。与单向搜索相比,该方法有较高的运行效率。与基于Dijkstra算法的贪心算法相比,该方法有较高的准确率。     

求解k条最短路径问题的混合蛙跳算法

提出了一种求解k条最短路径问题的混合蛙跳算法.采用自然路径的形式对青蛙个体编码,设计了一种能够使模因信息在青蛙个体间传递的蛙跳方法.在各青蛙族群内部,通过较差个体向优秀个体的跳跃进行局部搜索,从而优化模因信息.在族群之间,通过混合与排序使各族群的模因信息得以交流与重组,从而获取新的寻优方向.数值实验表明,本文算法搜索k条最短路径的能力强、收敛速度快、稳定性好,可应用于求解大规模网络中的多条最优路径问题.     

最长路径问题研究进展

最长路径问题是著名的NP难问题,在生物信息学等领域中有着重要的应用.参数计算理论产生后,参数化形式的k-Path问题成了研究的热点.介绍了现有求解最长路径问题的几种算法,包括近似算法、参数化算法和特殊图的多项式时间算法;着重分析和比较了参数化算法中利用着色、分治和代数法研究k-Path问题的最新结果.最后,提出了该问题的进一步研究方向.     

最短路径问题的禁忌搜索求解方法

针对网络优化算法中的最短路径（Shortest Path,SP）问题,建立了有约束条件的SP问题模型,并探讨了使用禁忌搜索（Tabu Search,TS）算法对其求解的算法框架及关键步骤。该求解方法寻优能力强,结构简明,能方便处理问题约束,具有智能计算方法的优点。最后,通过实例进行测试和比较,证明算法收敛速度快,并能够获得满足约束条件的优解集合,能适应较差网络条件下的多条路径选择,算法是可行和有效的。     

Scheduling Sport Tournaments using Constraint Logic Programming

We tackle the problem of scheduling the matches of a round robin tournament for a sport league. We formally define the problem, state its computational complexity, and present a solution algorithm using a two-step approach. The first step is the creation of a tournament pattern and is based on known graph-theoretic results. The second one is an assignment problem and it is solved using a constraint-based depth-first branch and bound procedure that assigns actual teams to numbers in the pattern. The procedure is implemented using the finite domain library of the constraint logic programming language \eclipse. Experimental results show that, in practical cases, the optimal solution of the assignment problem (which is not necessarily optimal for the overall problem) can be found in reasonable time, despite the fact that the problem is NP-complete. In addition, a local search procedure has been developed in order to provide, when necessary, an approximate solution in shorter time.     

Control Abstractions for Local Search

Comet is an object-oriented language supporting a constraint-based architecture for local search through declarative and search components. This paper proposes three novel and lightweight control abstractions for the search component, significantly enhancing the compositionality, modularity, and reuse of Comet programs. These abstractions, which includes events and checkpoints, rely on first-class closures as the enabling technology. They are especially useful for expressing, in a modular way, heuristic and meta-heuristics, unions of heterogeneous neighborhoods, and sequential composition of neighborhoods.     

无向连通图中求约束条件下近似最长路算法

在无向连通图中寻找最长路是一个NP问题,在实际应用中往往以近似最长路来代替最长路,但现存的算法都针对图中任意两点之间的近似最长路。该文利用一条最长路中是不可以被再插入一个新顶点的这个事实,通过对图的深度优先生成树的指定起点和终点之间的路径进行不断插入的方法,以多项式的算法复杂度求得一条指定起点和终点间不可再被插入顶点的路,而这样的一条路往往非常接近指定的起点与终点之间的最长路。该算法在绣花打版软件的应用中取得了良好的效果。     

数据仓库中时态视图的维护

数据仓库的一个重要用途是利用时态视图向用户提供历史信息.因为在传统关系数据模型中增加了对时间的支持,而且时态视图的更新不仅来自于基表更新,还包括时间前进,所以,目前对非时态视图维护的研究成果不适用于时态视图,并且已有的一些时态视图维护算法也不适用于数据仓库.以历史关系模式为对象,根据增量式维护方法的原理,采用纯删除、纯插入的计算方法,用代数语言给出了5种基本历史关系代数运算的更新传播算法,由这5种历史关系代数组合定义的时态视图都可用迭代方法得到其增量维护计算式.所采用的纯删除、纯插入思想也可移用于其他历史     

基于加权路径的指令调度算法

随着线延迟的逐渐增加,指令调度技术作为一种可以有效减少处理器片上通信的技术日益重要。本文介绍一种分片式处理器结构上基于加权路径的指令调度算法,该算法利用已经放置好的指令——锚指令信息精确计算路径长度,再用指令所在路径长度作为权值对指令进行调度。实验结果表明,本算法实现的调度器IPC比已有的两种TRIPS调度算法的IPC分别提高了21%和3%。     

A personal perspective on problem solving by general purpose solvers

To solve the problems that abound in real‐world applications, we are proposing an approach of using general‐purpose solvers, as we cannot afford to develop special‐purpose algorithms for all individual problems. The existing general‐purpose solvers such as linear programming and integer programming are very useful but not sufficient. To improve the situation, we have developed solvers for other standard problems such as the constraint satisfaction problem and the resource‐constrained project scheduling problem among others. In this article, we describe why general‐purpose solvers are needed, what kinds of solvers we considered, how they were developed and where they have been applied.     

An effective framework for asynchronous incremental graph processing

Although many graph processing systems have been proposed, graphs in the real-world are often dynamic. It is important to keep the results of graph computation up-todate. Incremental computation is demonstrated to be an efficient solution to update calculated results. Recently, many incremental graph processing systems have been proposed to handle dynamic graphs in an asynchronous way and are able to achieve better performance than those processed in a synchronous way. However, these solutions still suffer from suboptimal convergence speed due to their slow propagation of important vertex state (important to convergence speed) and poor locality. In order to solve these problems, we propose a novel graph processing framework. It introduces a dynamic partition method to gather the important vertices for high locality, and then uses a priority-based scheduling algorithm to assign them with a higher priority for an effective processing order. By such means, it is able to reduce the number of updates and increase the locality, thereby reducing the convergence time. Experimental results show that our method reduces the number of updates by 30%, and reduces the total execution time by 35%, compared with state-of-the-art systems.     

基于顶点组重分配的动态增量图划分算法

图划分是分布式图计算中的一项基础工作, 其作用是将大规模图进行划分并分配到集群中的不同机器上. 图划分的质量对分布式图计算的性能有很大的影响, 其目标是降低负载平衡和最小化边割. 如今, 现实中的图数据通常呈动态增长态势, 这就需要一种能够处理动态增量图的划分方法, 在图数据动态增长的过程中确保划分的质量不受影响. 目前虽然有一些动态图划分算法被提出, 但它们不能同时专注于实时处理动态变化和获得高质量的划分结果. 提出基于顶点组重分配的动态增量图划分算法(ED-IDGP)来解决大规模动态增量图的划分问题. 在ED-IDGP算法中, 设计实时处理4种不同单元更新类型的动态处理器, 并在每次处理完单元更新后通过在分区发生动态变化的附近执行局部优化器进一步提高图划分的质量. 在ED-IDGP的局部优化器中, 利用基于改进标签传播算法的顶点组搜索策略搜索顶点组, 并利用提出的顶点组移动增益公式衡量最有益的顶点组, 将该顶点组移动到目标分区中做优化. 在真实数据集上从不同的角度和度量指标评估了ED-IDGP算法的性能和效率.     

基因学习算法及其在图论中的应用

在ＰＢＩＬ算法及自私基因算法的基础上,提出了一个适应性更广、搜索能力更强的优化搜索算法。该算法从各基因位的初始等位基因概率出发,通过一系列概率采样、选择与搜索、概率修正等操作,使搜索空间逐步收敛于最优点。该算法既吸取了遗传算法的群体搜索的特点,又吸收了局部搜索算法的局部搜索能力强的优点。最后介绍了该算法在图论中的几个应用实例。     

Clause Weighting Local Search for SAT

This paper investigates the necessary features of an effective clause weighting local search algorithm for propositional satisfiability testing. Using the recent history of clause weighting as evidence, we suggest that the best current algorithms have each discovered the same basic framework, that is, to increase weights on false clauses in local minima and then to periodically normalize these weights using a decay mechanism. Within this framework, we identify two basic classes of algorithm according to whether clause weight updates are performed additively or multiplicatively. Using a state-of-the-art multiplicative algorithm (SAPS) and our own pure additive weighting scheme (PAWS), we constructed an experimental study to isolate the effects of multiplicative in comparison to additive weighting, while controlling other key features of the two approaches, namely, the use of pure versus flat random moves, deterministic versus probabilistic weight smoothing and multiple versus single inclusion of literals in the local search neighbourhood. In addition, we examined the effects of adding a threshold feature to multiplicative weighting that makes it indifferent to similar cost moves. As a result of this investigation, we show that additive weighting can outperform multiplicative weighting on a range of difficult problems, while requiring considerably less effort in terms of parameter tuning. Our examination of the differences between SAPS and PAWS suggests that additive weighting does benefit from the random flat move and deterministic smoothing heuristics, whereas multiplicative weighting would benefit from a deterministic/probabilistic smoothing switch parameter that is set according to the problem instance. We further show that adding a threshold to multiplicative weighting produces a general deterioration in performance, contradicting our earlier conjecture that additive weighting has better performance due to having a larger selection of possible moves. This leads us to explain differences in performance as being mainly caused by the greater emphasis of additive weighting on penalizing clauses with relatively less weight.     

A Fully Dynamic Approximation Scheme for Shortest Paths in Planar Graphs

In this paper we give a fully dynamic approximation scheme for maintaining all-pairs shortest paths in planar networks. Given an error parameter such that , our algorithm maintains approximate all-pairs shortest paths in an undirected planar graph G with nonnegative edge lengths. The approximate paths are guaranteed to be accurate to within a 1+ factor. The time bounds for both query and update for our algorithm is O( ^-1 n ^2/3 log ² n log D) , where n is the number of nodes in G and D is the sum of its edge lengths. The time bound for the queries is worst case, while that for the additions is amortized. Our approximation algorithm is based upon a novel technique for approximately representing all-pairs shortest paths among a selected subset of the nodes by a sparse substitute graph. Received January 1995; revised February 1997.     

一种高效的de bruijn有向图路由算法

通过对de bruijn有向图最长路径路由算法和最短路径路由算法的分析,提出了一种新的路由算法,它有效结合了两种算法的优点,并能根据网络时延来选择最优路径,对于时延的判断是由下一跳的时延和剩余各跳的预测时延两个部分组成,从而有效避免路由信息的局部性。分析表明,新的路由算法是行之有效的。