共查询到20条相似文献,搜索用时 187 毫秒
1.
2.
树状网络上的Web代理服务器最优放置问题 总被引:1,自引:0,他引:1
一般网络上Web代理服务器(Web proxy)最优放置问题是一个NP困难问题.此文讨论树状网络上的最优放置问题,改进了已有结果,得到了一个时间复杂度为O(nhk)的多项式时间算法,这里n为网络结点数,h为树的高度,而k为要放置的代理服务器个数. 相似文献
3.
《数学的实践与认识》2017,(18)
构造(m,n,k)指派问题的最小费用流模型,并将基于对偶原理的最小费用流的允许边算法求解该模型,提出求解(m,n,k)指派问题的一种算法.算法直接在其对应的网络中保持互补松弛条件不变,通过调整节点势以扩大允许网络从而寻求增广链并进行流量增广,直至在网络中得到流量为k的最小费用流,此时非O流边对应(m,n,k)指派问题的最优解.给出了(m,n,k)指派问题的最优解及多重最优解的重要性质,数值试验表明算法有效可行. 相似文献
4.
5.
本文研究随机排列的最优成组剖分问题。这一问题源于铁路列车的最优调度计划方法的设计问题。寻找切实可行的有效算法是问题的焦点。1978年这一问题被列入文献的公开问题之一。1986年许国志、陈庆华和刘继勇提出猜测:此乃NP-完全问题,即多项式时间的算法可能不会存在,除非NP=P。 本文引入一种强同构剪枝策略,以标号树形上的隐式枚举法为工具,得到了上述问题精确最优解的一个算法。其计算时间复杂度为O(n32n-2),其中n为随机排列中相异数字的个数。算法在给定n的条件下, 相似文献
6.
《数学理论与应用》2017,(2)
分支降阶被广泛用来求解NP-Hard问题,该技术的核心思想是将原问题分解成若干个子问题并递归求解这些子问题,但是用来分析算法时间复杂度的常规分析技术不够精确,无法得到较好的时间复杂度.本文设计了一个基于分支降阶的递归算法求解加权最大团问题,对于提出的精确算法,首先运用常规技术对该算法进行时间复杂度分析,得出其时间复杂度为O(1.4656~np(n)),其中n代表图中结点总个数,p(n)代表n的多项式函数;然后运用加权分治技术对原算法进行时间复杂度分析,将该算法的时间复杂性由原来的O(1.4656~np(n))降为O(1.3765~np(n)).研究结果表明运用加权分治技术能够得到较为精确的时间复杂度. 相似文献
7.
8.
本文提出一个解线性规划问题的新算法.其最优解是通过求一个相容方程组的非负解而得到.这算法的计算量在最坏情况下是O(mnτ),其中τ是相应方程的m×n矩阵非零元素的个数. 相似文献
9.
10.
11.
关于整数向量卷积的一个算法的时间复杂度 总被引:2,自引:1,他引:1
众所周知,两个n维整数向量循环卷积的常规算法(即按定义计算)的时间复杂度为O(n~2),现在已有时间复杂度为O(nlog_2n)的快速算法,[1]中提出一个新算法,称其时间复杂度为O(n),因而是最佳的。 本文首先指出[1]的错误原因,再根据算法分析理论得出[1]中算法的时间复杂度不低于O(n~2log_2n),因而比常规算法的运算量还大。 相似文献
12.
关于矩阵乘法的一个改进算法的时间复杂度 总被引:2,自引:0,他引:2
两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n3),文献[1]提出一个“运算次数”为O(n2)的“最佳”算法,文献[2]对此算法做了进一步研究,提出三种改进策略.本文根据算法分析理论,得出改进后的算法的时间复杂度仍不低于O(n3logn),因而其阶仍高于常规算法的运算量的阶. 相似文献
13.
关于矩阵乘法的一个算法的时间复杂度 总被引:4,自引:1,他引:3
两个n阶非负整数方阵相乘,常规算法的时间复杂度为O(n3),文献[1]提出一个“运算次数”为O(n2)的“最佳”算法,本文根据算法分析理论得出此算法的时间复杂度不低于O(n3log2n),因而比常规算法的运算量还大. 相似文献
14.
An Optimal Deterministic Algorithm for Computing the Diameter of a Three-Dimensional Point Set 总被引:1,自引:0,他引:1
E. A. Ramos 《Discrete and Computational Geometry》2001,26(2):233-244
We describe a deterministic algorithm for computing the diameter of a finite set of points in R
3
, that is, the maximum distance between any pair of points in the set. The algorithm runs in optimal time O(nlog n) for a set of n points. The first optimal, but randomized, algorithm for this problem was proposed more than 10 years ago by Clarkson and
Shor [11] in their ground-breaking paper on geometric applications of random sampling. Our algorithm is relatively simple
except for a procedure by Matoušek [25] for the efficient deterministic construction of epsilon-nets. This work improves previous
deterministic algorithms by Ramos [31] and Bespamyatnikh [7], both with running time O(nlog
2
n) . The diameter algorithm appears to be the last one in Clarkson and Shor's paper that up to now had no deterministic counterpart
with a matching running time.
Received May 10, 2000, and in revised form November 3, 2000. Online publication June 22, 2001. 相似文献
15.
We present a hybrid optimization approach for solving automated parameter estimation models. The hybrid approach is based on the coupling of the Simultaneous Perturbation Stochastic Approximation (SPSA) [1] and a Newton-Krylov Interior-Point method (NKIP) [2] via a surrogate model. The global method SPSA performs a stochastic search to find target regions with low function values. Next, we generate a surrogate model based on the points of regions on which the local method NKIP algorithm is applied for finding an optimal solution. We illustrate the behavior of the hybrid optimization algorithm on one testcase. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) 相似文献
16.
Next-generation sequencing technologies have redefined the way genome sequencing is performed. They are able to produce tens of millions of short sequences (reads), during a single experiment, and with a much lower cost than previously possible. Due to the dramatic increase in the amount of data generated, a challenging task is to map (align) a set of reads to a reference genome. In this paper, we study a different version of this problem: mapping these reads to a dynamically changing genomic sequence. We propose a new practical algorithm, which employs a suitable data structure that takes into account potential dynamic effects (replacements, insertions, deletions) on the genomic sequence. The presented experimental results demonstrate that the proposed approach can be extended and applied to address the problem of mapping short reads to multiple related genomes. 相似文献
17.
In this paper, we consider the Online Target Date Assignment Problem (OnlineTDAP) for general downstream problems, where the downstream cost are nonnegative, additive and satisfy the triangle inequality.We analyze algorithm smart, which was introduced by Angelelli et al. [3] and give its exact competitive ratio depending on the number of requests. Since the obtained competitive ratio is at most we answer the question posed in Angelelli et al. [4] if smart has a competitive ratio strictly less than 2.Moreover, we introduce a new algorithm called clever and show that this strategy has a competitive ratio of 3/2. We show that this is asymptotically optimal by proving that no online algorithm can perform better than 3/2−ε. 相似文献
18.
Given an n-vertex outer-planar graph G and a set P of n points in the plane, we present an O(nlog3n) time and O(n) space algorithm to compute a straight-line embedding of G in P, improving upon the algorithm in [8,12] that requires O(n2) time. Our algorithm is near-optimal as there is an Ω(nlogn) lower bound for the problem [4]. We present a simpler O(nd) time and O(n) space algorithm to compute a straight-line embedding of G in P where lognd2n is the length of the longest vertex disjoint path in the dual of G. Therefore, the time complexity of the simpler algorithm varies between O(nlogn) and O(n2) depending on the value of d. More efficient algorithms are presented for certain restricted cases. If the dual of G is a path, then an optimal Θ(nlogn) time algorithm is presented. If the given point set is in convex position then we show that O(n) time suffices. 相似文献
19.
20.
Batch sizing and job sequencing on a single machine 总被引:7,自引:0,他引:7
E. G. Coffman Jr. M. Yannakakis M. J. Magazine C. Santos 《Annals of Operations Research》1990,26(1):135-147
We study a single-machine scheduling problem in which the items to be processed have to be batched as well as sequenced. Since processed items become available in batches, flow times are defined to be the same for all items in the same batch. A constant set-up delay is incurred between consecutive batches. For any fixed, but arbitrary item sequence, we present an algorithm that finds a sequence of batches such that the total flow time of the items is minimized; we prove that for a set ofn items, the algorithm runs inO(n) time. We show that, among all sequences, the one leading to the minimum flow time has the items in non-decreasing order of running times. Thus, the optimal algorithm for the combined problem, called thebatch-sizing problem, runs inO(n logn) time. We also prove that this algorithm yields an improved solution to a scheduling problem recently studied by Baker [1]. 相似文献