集合划分问题的粒子群优化算法

建立了集合划分问题的优化数学模型,结合遗传算法的思想提出的粒子群算法来解决集合划分问题。经过比较测试,6种粒子群算法的效果都比较好,特别交叉策略A和变异策略A的混合粒子群算法是最好的且简单有效的算法。

一种通用的求解图的多划分问题的改进遗传算法

针对图的多划分问题的特点 ,本文提出了一种适合于求解这一类问题的改进遗传算法 .该算法无论在编码方式、算子设计乃至算子功能的界定上 ,都与经典遗传算法有着很大差别 .实例验证 ,该算法是通用的和有效的 .它既充分利用了遗传算法全局性的搜索能力 ,又增强了遗传算法的局部搜索能力 ,明显地提高了收敛速度 .该算法的提出 ,大大减轻了用户解决具体应用问题的负担 .

集合划分问题的蚁群算法

集合划分问题是一个典型的NP完全问题,建立了集合划分问题的优化数学模型,采用蚁群算法解决了此问题。对蚁群算法参数的合理选取进行了实验分析,给出了算法参数选取的基本原则。与贪心法作了比较,结果表明该方法比较有效。

基于遗传算法的集合划分问题求解

集合划分问题是组合优化领域中有着广泛应用基础的著名问题,属于NP难问题。通过引入精英策略提出对遗传算法的改进,并为了能把遗传算法应用到集合划分问题,对数学模型进行了等价变换。针对集合划分问题,设计出一种高效的基因表示,避免了组合优化中处理约束条件的麻烦。解决了传统二进制基因编码无法精确适应离散优化问题,首次提出一种离散编码解决方案。最后,使用VisualC++6编程实现,取得较好的结果。

矩形的三角形划分问题研究

给出了矩形的三角形划分问题的定义,该问题是三角形Packing问题的一个特例,证明了该问题是NP完全的,并给出了该问题有解的一个必要条件。

三划分问题可多项式归约为唯一可达向量Petri网可达性问题

为了对基于唯一可达向量Petri网(URV-PN)的密码体制进行密码分析工作,有必要对唯一可达向量网系统的数学本质和各种性质进行深入的研究.定义了扩展的三划分问题,三划分问题是扩展的三划分问题的一种特殊情况;给出了一个一般的多项式时间复杂度算法构造扩展的三划分问题的Petri网模型;证明扩展的三划分问题有解当且仅当所构造的Petri网模型中某个标识可达;从而说明三划分问题可多项式归约为唯一可达向量Petri网系统的可达性问题,从而给出了求解唯一可达向量网系统可达性问题的一个复杂度下界.

一种求解划分问题的新算法

划分问题是 VL SI- CAD设计中的基本问题 .针对近似划分问题、划分问题、背包问题 ,提出了一种行之有效的快速算法 ,其核心思想是基于拟物思路构造目标函数 .

饮用水水源保护区划分问题探讨

阐述了国内外划定饮用水水源保护区的方法和原则,并举例说明了辽宁省水库水源保护区的划分情况以及相关的技术发展趋势、法律程序等。

赋权超图划分问题的多水平迁移优化算法研究

伴随着赋权超图划分问题的规模不断地增长,对赋权超图划分的处理效率和能力、准确性有了更高程度的要求.本文采用形式化符号描述了赋权超图优化划分问题,阐明了基于多水平思想求解该问题的粗化、初始划分和迁移优化三个阶段;提出了基于离散粒子群和多水平思想的迁移优化算法,在|V|维空间中每个粒子所处的位置对应于超图划分方案;伴随着投影优化阶段的细化,每个粒子对应的划分方案映射到下一水平层的粗化超图;随着划分问题解空间的维度|V|增加,粒子的自由度增大;将结点迁移的收益值作为粒子的启发式搜索信息,利用粒子之间聚集协同表现出的智能行为有效地搜索解空间;给出了赋权超图的改进压缩存储格式,提出了割切值和收益值的快速计算方法,有效降低了划分算法的时空复杂度.基于ISPD98测试基准的对比实验数据表明:与基于迁移方法的赋权图、赋权超图优化划分算法相比,本文算法有效地增强了迁移优化算法逃离局部最优的能力.

有元素类型约束的k-划分问题研究

研究有元素类型约束且每个元素权重为正数的κ-集合划分问题,元素类型约束指κ-划分后每个集合所包含的元素的类型均不同,该问题是对κ-划分问题(κ-partitioning problem)的一个拓展,在一人可拥有多技能执照的行业有广泛的应用背景,提出基于LPT算法思想的贪婪算法,并得出以下结论:κ≤2,该算法给出最优解:κ>2,最坏情况下的性能比为2-m^(-1),这里m指待分配集合的数量。

用神经网络求解划分问题

划分问题是一类常见的 NP完备的优化问题 ,本文利用推广的 Hopfield神经网络模型解决了划分问题 ,并取得了较好的效果 ,为这个问题的解决提供了一条新的途径。同时 ,也为解决其它优化问题提供了有益的启示。

线性划分问题的一个改进算法

给定一个由n个非负数构成的序列X={x1,x2,…,xn}及正整数k≤n,线性划分问题要求将该序列划分为不大于k段子序列,使得最小化各段子序列元素之和为最大值。目前已知该问题的最好算法是时间复杂度为O(kn2)和空间复杂度为O(kn)的动态规划算法。利用非负数序列的性质,给出一个快速改进算法,其时间复杂度为O(knlogn),空间复杂度为O(n)。

基于关系的最粗粒度划分问题的并行算法

关系最粗粒度的划分问题 RCPP在并发系统的验证方面起着重要的作用。本文提出了RCPP问题的一种有效的并行算法 ,其中假设标号转移系统中有 m个转移和 n个状态 ,利用 m/nε个CREW处理器算法所需的运行时间为 O( n1+ε) (对于任意固定的 ε<1 )。

区域农业污染事故多主体污染责任划分问题探析——以广西某大气污染侵权纠纷上诉案为例

基本案情和处理经过 2011年4月25日，广西壮族自治区南宁市中级人民法院依法受理了上诉人武呜县苞桥林化厂不服武呜县人民法院（2010）武民二初字第42号民事判决，而提起的上诉请求，并进行审理。

整数集合的划分问题

把整数集合P分拆成若干个非空的真子集P1、P2、…、Pn,并且使得 （1）Pi∩Pj=φ（i、j=1、2、…、n,且i≠j） ;（2）P1∪P2∪…∪Pn=P。则称Pi（i=1、2、…、n）为P的一个划分。 近些年来,整数集合及其子集的划分问题是国内外较高层次的数学竞赛的热门题型。就其题型分类而言,常归结为两类:其一讨论子集划分的存在型;

解答划分问题的新拟多项式时间算法

利用一种称为平衡技术的新方法解答划分问题。证明若划分问题存在满足条件的子集,则该子集一定是平衡集,仅对平衡集进行枚举即可解答划分问题。若划分问题给定集合中每个元素的长度都被一个常数M所界定,结合动态规划技术且仅考虑平衡集,解答划分问题的时间复杂度为O(nM),此算法在时间效率上对现有算法有较大改进。

从副词的归属谈词类划分问题

副词是实词还是虚词,这是我国语法界长期以来议无定论的一个问题。从我国最早的语法书《马氏文通》到目前为止,对于副词的归属问题有三种不同的意见:一是认为副词应归属于实词,持这种意见的人不多,主要有马建忠、胡裕树、黄伯荣、张静等人;一是认为副词应归属于虚词,这大概是我国语法界大多数人的意见和习惯的分法,如杨树达、杨伯峻、刘景农、王力、张志公等人持这种意见;高名凯、吕叔湘等人,则把副词的归属问题先挂起来,期待解决。笔者认为,高名凯先生和吕叔湘先生提出的问题是值得深思的,也是目前我国语法界亟待解决的。副词归属于实词对呢,还是归属于虚词对呢?

背越式跳高技术类型划分问题的探讨

在背越式技术中存在着不同技术类型这一事实,近年来各国都注意到了。尽管各国对不同类型技术的称呼不同,但基本上都是分成两种类型,称之为速度型和力量型、速度型和幅度型、或背越式Ⅰ型(即速度型)和背越式Ⅱ型(即幅度型)等。对于背越式跳高技术类型的划分问题,国内尚未见到有关的研究文章;国外虽有一些文章对不同技术类型进行了对照研究,并提出了一些具体的数字。但是,总的来看,这些资料还存在下面三个问题:一、没有说明取得数据的方法。有的文章只是说某人认为怎样。

差异演化算法求解集合划分问题

集合划分问题是组合优化中典型的NP难题,建立了集合划分问题模型,采用差异演化算法对其进行求解。通过对其它文献中仿真实例的计算和结果对比,表明了算法对求解集合划分问题的可行性和有效性。

关于国内现代蒙古语的方言划分问题

我国境内的蒙古族,主要分布在内蒙古自治区、辽宁、吉林、黑龙江、甘肃、宁夏、青海、河北等省和新疆维吾尔自治区的一些地方。绝大部分地区的蒙古族人民都使用着本民族语言,有些地区的蒙古族人民兼通汉语,青海省的蒙古族有些人兼通藏语,新疆的蒙古族有些人兼通维吾尔语,还有少数蒙古族由于长期与其他民族杂居而转用了其他民族语言。 蒙古语言文字不但是蒙古族人民的重要交际工具。