关于“TSP”的算法研究

n阶完全图（边赋权）的矩阵每行每列最小元素对应着一个次数为n的置换，若从这些最小元素组成的所有圈中每圈至少取出一个元素并令其为∞，那么仅包含这些元素的子矩阵可以经过初等变换将这些元素置于主对角线上形成一个新矩阵，其每行每列最小元素又对应一个新的置换。在满足一定条件时，两个置换合成能够得到一个次数为n的循环置换。运用这些方法，可使求TSP解的算法得到简化。     

基于矩阵初等变换的粗糙集

提出了近似空间中集合X的增广矩阵及其初等变换的概念,证明了初等变换矩阵中不含元素1的所有列对应的划分类的并为集合X的下近似,含元素R○的所有列对应的划分类的并为集合X的上近似,并由此给出了一种计算粗糙集的快速高效算法。     

行(列)满秩阵的几点性质

以矩阵的秩为基础,给出了两种特殊的矩阵:行满秩阵和列满秩阵,并对照矩阵的性质给出了行(列)满秩阵的几条性质,在此基础上研究了线性方程组AX=B对任一m维列向量B都有解的充要条件,进一步给出了矩阵方程AX=B有唯一解的条件。     

行(列)满秩阵的几点性质

以矩阵的秩为基础,给出了两种特殊的矩阵:行满秩阵和列满秩阵,并对照矩阵的性质给出了行(列)满秩阵的几条性质,在此基础上研究了线性方程组AX=B对任一m维列向量B都有解的充要条件,进一步给出了矩阵方程AX=B有唯一解的条件.     

拟置换矩阵的若干性质

为了叙述方便,我们先引进拟置换矩阵和拟单位矩阵两个概念。定义1 设Q为n 阶矩阵。若Q的每行、每列恰好有一个元素为1或-1,其余元素全为0,则称Q为拟置换矩阵。定义2 n阶矩阵     

素理想参数化的符号算法

Ｇａｏ等给出了素理想参数的一种随机算法,Ｇａｌｌｏ等估计了这种算法的计算复杂度,并将此算法改进为确定性的算法,避免了上机实现可能出现的“随机陷阱”尽管如此,由于这种算法可能需要计算多次特征列,使复杂度提高,应用受到很大限制,本文给出了素理想参数化的一种符号算法,只需计算两次特征列,就能得到原理想的参数化,并同时可以确定“例外集”。     

用矩阵图法求逆矩阵

文献[1]提出的矩阵图,是一种矩阵的图形表示方法,同时,用矩阵图的图形变换可实现对应的矩阵初等行(列)变换。本文给出了用矩阵图法实现求逆矩阵的方法。     

解大型稀疏线性方程组的一种算法

设A=(?)是一m×n阶矩阵,A_1是m阶方阵.当perC[G_c(A_1)]=,2,3,4时,本文给出了解线方程组AX=C的一种算法.G_c(A)是矩阵A的伴随有向图(Coates图),C[G_C(A)]是图G_C(A)的邻接矩阵.此算法将高斯消元过程直接在G_C(A)上进行,省去了化A为某种标准形的麻烦.此算法显示了对大型稀疏方程是有效的,因此时C[G_C(A)]的积和式perC[G_C(A)]往往较小.Bengt Aspall和Yossi Shiloach对系数矩阵A的每行仅含至多两个非零元时的情形给出了解AX=C的一个特殊的图算法.本文给出的算法包容了这一特殊情况.     

信息检索的一个数学模型(Ⅱ)

§6.压缩存贮与压缩检索运算上面我们讨论的特征矩阵与提问矩阵,一般都是庞大的稀疏矩阵。这种矩阵在现代电脑中进行存贮与计算实际上是不可能的,当然也就无法得到检索答案。因此,我们对于这种矩阵必须进行压缩。如果X是一个无二义(0,1)矩阵(就是可用连续删除全0、全1行或者全0、全1列,最后删空的矩阵),那末可用存贮“行和”与“列和值序”的方法把原信息大大压缩(所谓“行和”就是一个行向量中全部1相加的和。“列和值序”就是按各“列和”值的大小排成     

关于"TSP"的算法研究

n阶完全图 (边赋权 )的矩阵每行每列最小元素对应着一个次数为n的置换 ,若从这些最小元素组成的所有圈中每圈至少取出一个元素并令其为∞ ,那么仅包含这些元素的子矩阵可以经过初等变换将这些元素置于主对角线上形成一个新矩阵 ,其每行每列最小元素又对应一个新的置换 .在满足一定条件时 ,两个置换合成能够得到一个次数为n的循环置换 .运用这种方法 ,可使求TSP解的算法得到简化     

基于Floyd算法的反恐防暴机器人腿部变形策略

反恐防暴机器人的腿部变形,能够改变机器人的运行姿态,适应不同的路况,完成跨越壕沟、翻越高墙等障碍物的任务;这就要求机器人能够准确、快速、平稳的变形到相应的姿态以适应不同的路况。通过Floyd算法实现了这一变形要求,Floyd算法是一种求解有向图中两个节点之间最短路径的算法。把机器人几种常用的姿态简化为有向图中的节点,用姿态变换过程中电机旋转角度和机器人重心偏移量来确定节点之间的连接权值。实验证明,Floyd算法能够快速找到两个姿态之间最短的变换路径,实现了机器人准确、快速、平稳的变形。     

基于BDD的图表示及其算法

给出基于二元判决图BDD的无权图和有权图的符号化表示,同时给出该表示下的算法设计及实现,并以连通度算法和最短路径算法作为例子。     

一种判定树同构的BULT算法

将判定两棵树的同构问题转化成"图的同构"问题和"两棵树根结点之间的对应关系"问题的判定.基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom-Up Layer Traversing)的方法,简称 BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明.该算法很容易扩展为图同构的判定算法.     

求图的总体最佳2—划分的有效启发式算法

本文提出一个求图的总体最佳2—划分的有效启发式算法,是对文献[1]中提出的算法的改进。它仍以划分之间的连线条数最少为约束条件,对系统的连接矩阵进行操作,使子矩阵相应的两个子系统,成为所求的总体最佳2—划分。     

基于禁忌搜索的模拟退火算法在最小控制集中的应用

图的控制集问题是在给定的简单无向图中求出阶数最小的控制点的集合,目前它已被证明是一个NP-完全问题．针对现阶段已有的模拟退火算法提出了一种改进的基于禁忌搜索的模拟退火算法,并通过与贪心算法、传统模拟退火算法进行比较,证明了该算法可以获得较小的控制集阶数．     

关于图染色的算法

本文给出了图上顶点染色,边染色的算法.其中边染色算法是一个非多项式时间的精确算法,该算法是先求出所有极大匹配,然后再求极小匹配覆盖,最后得出最优边染色.顶点染色算法是一个多项式时间的近似算法,该算法的时间复杂性为O(n~3logn),空间复杂性为O(n~3)的近似算法,它是由贪吃策略得到的.对于任意的图,该算法所用的期望颜色数为「log(n 1)」.     

任意无向加权图K点连通扩充的逐次改善算法

为了对网络的可靠性寻求较好的近似算法,研究了任意无向不加权图情况下的极小K 点连通扩充算法;在此基础上提出无向加权图G总边数和各点的连通度均保持不变时,使图G的总权值变小的一种可行边交换方法;同时得出一个可行边交换的引理,并加以证明.最终推出了任意无向加权图K点连通最小扩充的逐次改善算法,应用该算法作了大量例题,得到比较满意的效果.为解决任意无向加权图最小扩充问题给出了一种新途径.     

有交双圈图邻接矩阵的奇异性

含有n个顶点,n 1条边的简单连通图称为双圈图.若双圈图G中存在两个圈,它们有公共交点,则称G是有交双圈图.本文给出了有交双圈图的邻接矩阵是奇异的充分必要条件.     

6-阶图与路的笛卡儿积交叉数

图的交叉数是指把图画在平面上边与边产生的交叉数目的最小值。图的交叉数只在好画法中得到,好画法是指满足边自身不交叉,相关联的边不交叉,任意两条交叉的边至多交叉一次的画法。图的交叉数已被证明是一个NP-完全问题,由于其难度,要知道图的确切交叉数是非常困难的。到目前为止,只知道少数图的交叉数,其中大部分是特殊图的笛卡儿积图的交叉数,比如路,圈以及星图与点数较“少”的图的笛卡儿积交叉数。在这些基础上,应用数学归纳法,把相关结果拓展到4个6-阶图与长为的路的笛卡儿积交叉数。     

Floyd算法的一个通用程序及在图论中的应用

给出了图结构中Floyd算法的一个通用程序,并应用该程序提出了图的许多重要性质的充分必要判别条件和图论中若干重要问题的不同于传统的新解法．提出的实现动态数组的思想对设计以多维数组为参数的通用程序具有普遍意义．