图的最大权团的DNA计算

给定顶点赋权的无向图,图的最大权团问题是寻找每个顶点都相邻的顶点子集(团)具有最大权.这个问题是寻找无权图的最大团问题的推广.图的最大团和最大权团都是著名的NP-完全问题,没有非常有效的算法.1994年Adleman博士首先提出用DNA计算解决NP-完全问题,使得NP-完全问题的求解可能得到解决.本文给出了基于质粒技术的无向图的最大权团问题的DNA算法,依据Head T等的实验手段,本文提出的算法是有效并且可行的.     

A simple simulated annealing algorithm for the maximum clique problem

Simulated annealing technique has mostly been used to solve various optimization and learning problems, and it is well known that the maximum clique problem is one of the most studied NP-hard optimization problems owing to its numerous applications. In this note, a simple simulated annealing algorithm for the maximum clique problem is proposed and tested on all 80 DIMACS maximum clique instances. Although it is simple, the proposed simulated annealing algorithm is efficient on most of the DIMACS maximum clique instances. The simulation results show that the proposed simulated annealing algorithm outperforms a recent efficient simulated annealing algorithm proposed by Xu and Ma, and the solutions obtained by the proposed simulated annealing algorithm have the equal quality with those obtained by a recent trust region heuristic algorithm of Stanislav Busygin.     

无线认知网络中一种团划分的频谱感知算法

提出了一种基于节点之间竞争关系以及感知代价的分布式频谱感知算法.该算法基于分布式最小团划分理论,将节点划分至不同的团中,然后再根据团的结构来计算最优频谱感知分配.该算法的时间复杂度仅为O(N2+M×N),其中,N为网络中节点数,M为信道数目.大量的仿真实验结果表明,该算法能够有效地提高网络性能.     

基于最大权团的曲面粗匹配算法

提出一种将曲面匹配问题转化为图论中的最大权团搜索问题、将最优的点对应关系用最大权团表示的曲面粗匹配算法,该算法分为点匹配、点对应图构造和最大权团生成等3个阶段.点匹配使用高曲率点和均匀采样点作为候选点,通过自旋图进行匹配计算,构造初始点对应集合;点对应图构造使用距离约束、法矢约束和唯一性约束构造图的边,并使用自旋图相关系数为顶点赋权值;最大权团生成使用基于分支限界的团搜索算法,从对应点图中提取出代表最优对应的最大权团.实验结果表明,文中算法稳定、有效、可扩展,能够进行部分曲面匹配,并且适用于欠特征曲面.     

COMPUTING MAXIMUM CLIQUES OF CIRCULAR ARCS IN PARALLEL*

Given a set S of n proper circular arcs, it is required to identify a largest cardinality subset K[S] of S each two of whose members intersect. This paper describes an optimal parallel algorithm to compute K[S]. The algorithm is not based on any previously known sequential solution, and is designed for the CREW PRAM model of computation. It uses 0(n/logn) processors and runs in O(logn) time. An interesting feature of the algorithm is that it transforms the computational geometric problem at hand, to a problem involving computations on 0-1 matrices, and then transforms the latter back into a ray shooting problem in computational geometry.     

贝叶斯网络在空间机械臂故障诊断中的应用研究

空间机械臂在空间设施中广泛应用,如何准确快速判断其运行状态成为需要解决的重要问题。文中首先介绍了机械臂在国内外空间设施的应用背景,然后采用基于故障树与贝叶斯网络的故障诊断方法,包括：基于系统组成结构的故障树建模、贝叶斯网络转化、团树传播算法和最大后验估计(MAP)推理结果分析。最后利用单点故障实验和多点故障实验对所提方法进行了验证,结果表明将故障树分析和贝叶斯网络结合应用到空间机械臂故障诊断是有效的、可行的。     

The TTA's Approach to Resilience after Transient Upsets

The Time-Triggered Architecture, as architecture for safety-critical real-time applications, incorporates fault-tolerance mechanisms to ensure correct system operation despite failures. The primary fault hypothesis of the TTA claims to tolerate either the arbitrary failure of any one of its nodes or the passively arbitrary failure of any one of its communication channels. To cover these failure modes, active redundancy techniques are used, which basically means that nodes and channels are physically replicated. The primary fault hypothesis, is, however, not strong enough for certain applications that have to tolerate transient upsets of multiple, possibly all, components in the system. Such a transient upset of the system may break up the synchrony of the nodes and leave disjoined sets of nodes synchronized to each other while the overall synchronization is lost. Although the TTA provides a clique avoidance algorithm that is able to correct a wide class of such multiple transient failures, a stronger algorithm is needed for full coverage. In this paper we discuss a secondary fault hypothesis for the TTA that addresses the transient upset of multiple components and present a new clique resolving algorithm based on the TTA's integrated diagnosis and startup service. This paper is a revised version of Steiner et al. (2003). This work has been funded by the European Project DECOS (Project number: IST-511764). Michael Paulitsch is currently affiliated with Honeywell International.     

基于深度卷积生成对抗网络和拓展近邻重排序的行人重识别

在刑事侦查、智能监控、图像检索等领域,行人重识别一直是研究的热点.由于现有的大部分方法依赖有标注数据集,因此标签的缺乏使得无监督的行人重识别技术变得更具挑战性.为了克服这一问题,提出了一个用于生成可靠伪标签的框架,这些生成标签可以为现有监督行人重识别模型提供监督信号.假设数据集内的大部分图片都满足同一个摄像头拍摄的图片差异主要在于前景（行人）、同一个行人被不同摄像头拍摄到的图片差异主要在于背景.为了消除图片背景带来的差异,首先把数据集中的图片依据摄像头编号分成若干个域,通过计算每个域内的图片间的欧式距离,建立图模型,执行最大团算法寻找最相似的若干个图片并认为它们属于同一个行人;紧接着计算不同摄像头域间的团的相似度,据此进行合并;最终给出全局伪标签.所提的框架无需人为标注数据,以一种无监督的方式运行,并在Market1501和DukeMTMC-ReID数据集上进行实验,实验发现所提方法比其他相关方法具有更高的精度,从而进一步证明了所提方法的有效性.

     

求解图的最大团的一种算法

图的最大团问题是一个著名的ＮＰ－完全问题．现有求解图的最大团的算法或者只适用于某些特殊的图,或者需要指数级时间代价,效率较低．以图的区间表示的概念为基础,提出了一种求解最大团的算法．该算法能够适用于任意的简单图,并且在一定的条件下,该算法只需要多项式时间就可以完成运行.     

Generation of Primary Input Blocking Pattern for Power Minimization during Scan Testing

In this paper we propose a new approach to generate a primary input blocking pattern for applying to the primary inputs during shift cycle such that the switching activity occurred in the combinational part of the circuit under test can be suppressed as much as possible. The primary input blocking technique suppresses transitions of gates in the combinational part during scan by assigning controlling values to one of the gates' inputs. However, simultaneously assigning controlling values to the gates may result in conflicts in the setting of binary values on the primary inputs. Instead of the heuristics based on fanout in other approaches, we use the impact function which is based on transition density to determine the priorities of the gates to be blocked. Experiments performed on the ISCAS 89 benchmark circuits show that the proposed approach can always produce better results than the existing approaches.