排序方式: 共有46条查询结果,搜索用时 15 毫秒
11.
一类背包问题的可解性 总被引:1,自引:0,他引:1
马绍汉 《山东大学学报(理学版)》1985,(4)
本文的主要结果是,对K背包问题给出了时间、空间复杂性为O(nM~k)的拟多项式算法;证明了若P≠NP,则该问题不存在完全多项式时间ε近似算法;对动态背包问题给出了时间复杂性为O(nM~k)的拟多项式算法。 相似文献
12.
对资源短时占用型作业调度的问题给出了一个数学描述模型 ,并讨论了该问题求解的时间复杂性 .基于该模型提出了对不同情况最佳或近似最佳的实用的联机调度算法 ,并讨论了这些算法在其他类似问题上的应用 . 相似文献
13.
在限定处理机个数的 CREW PRAM并行计算模型上,给出了图论中一些基本问题的并行算法.所给并行算法的费用c(n)=p(n)*t(n)是目前已知的最好结果,其中p(n),t(n)分别是对一具有n个顶点图实施并行算法所用处理机的个数和最坏情况下的时间复杂性。 相似文献
14.
图G的K分割问题可描述为:输入(Ⅰ)G=(V,E),G为简单无向图,其中|V|=n,|E|= m;(Ⅱ)a_1,a_2,…,a_k k个G中不同的顶点;(Ⅲ)n_1,n_2,…,n_k k个正整数满足 n_1+n_2+…,+n_k= n.输出(V_1,V_2,…,V_k),对1≤i≤k,满足(Ⅰ)a_i∈V_i;(Ⅱ)G[V_i]是连通图;(Ⅲ)|V_i|=n_i.本文给出时间复杂性为O(knm)通用K连通图的k分割多项式算法. 相似文献
15.
16.
Huang首次利用n元组相邻位的相异数为索引,生成德·布鲁因序列.由前几位产生下一位需4n 位存贮单元,4n 个时间单元.本文,首先改进Huang 的算法,使产生一位需4n 位存贮单元,2n 个时间单元;然后给出一个利用n 元组相异数为索引,生成德·布鲁因序列的新算法,由前n 位产生下一位需4n 位存贮单元,n 个时间单元.新算法与原算法同样具备可从任意n 元组开始计算的特点. 相似文献
17.
马绍汉 《山东大学学报(理学版)》1984,(1)
多层印刷线路板布线中如何减少金属导孔是一个重要问题。本文将这个问题化为在2—部超图G[S、V、E]中寻找一类限制树问题。证明了该问题为Np—Complete,并给出它的多项式时间heuristric算法。 相似文献
18.
19.
提出两种基于竞争的神经网络联想存储器学习算法—CC算法和ACC算法 ,并证明算法得到的神经网络对任一输入模式的竞争收敛性 ,由CC算法得到的网络 ,利用 p n个神经元存储p个n维样本模式 ;每个样本点都是吸引中心 ,不存在假吸引中心 ;对任一输入模式 ,总被吸引到与之海明距离最小的样本点上 ;不产生拒识点 .ACC算法是CC算法的改进形式 ,所得网络可在自适应学习中收敛 ,竞争次数较CC算法大大降低 本文算法得到的网络在存储容量、容错能力方面好于Hopfield联想存储器及作为联想存储器使用的BP网络 . 相似文献
20.