统筹图的矩阵表示及计算

其中 t_(ij)为工序(i,j)需要的时间,S_k 为从始点到终点的第 k 条路线,它是由一系列工序组成的.对于较复杂的统筹图如果要把从始点到终点所有路线需要的时间都一一算出来,然后从中找出需要时间最长的一条,是比较麻烦的,有些计算是重复的.所以,华罗庚在[1]中指出:“对于较熟悉的人来说,用逐步比较的办法,就可以较快地找出主要矛盾线”.例如,图1中按定义逐条路线求主要矛盾线,其中⑤→⑦和⑥→⑦都重复用了两次.     

树的笛卡儿积的测地数

图G内的任意两点u和υ,u-υ测地线是指u和υ之间的最短路.I(u,υ)表示位于u一υ测地线上所有点的集合,对于子集S∈V(G),I(s)表示所有,(u,υ)的并,这里u,υ∈S.图G的测地数g(G)是使,I(s):V(G)的点集S的最小基数.本文研究了任意连通图G与树T笛卡儿积的测地数的界,同时,给出了任意两个树T1与T2笛卡儿积的测地数和树T与圈C笛卡儿积的测地数.     

最优化原理视角下的两道全国高中数学联赛加试题

1最优化原理 最优化原理是说一个问题的最优化策略有这样一个性质：不论以前的决策如何,对于当前的子问题而言,其余的决策一定构成最优问题．简而言之,一个最优策略的子策略总是最优的．例如,四个城市A、B、C、D间的路线如图1所示,如果从A到D的最短路线为A→B→D,那么从B到D的最短路线为B→D．用反证法证明之．如果从B到D的最短路线不是B→D,     

集合笛卡儿积集中文氏图的一种推广

介绍了涉及集合笛卡儿积(Cartesian product)的运算性质讨论的一种类似于文氏图(Venn diagram)的方法.     

蚂蚁爬行中的数学问题

蚂蚁从几何体的某点出发,爬行到另一点或某直线上,求蚂蚁爬行的最短距离的问题,单凭直观想象很难找到爬行的路线．因而难度较大,解决这类问题通常是把几何体展开成平面图形,再利用“两点之间线段最短”或“点到直线垂线段最短”等性质,找出蚂蚁爬行的最短路线,然后再通过计算求得结果．     

邮政运输网络中的邮路规划和邮车调度

本题是一道VRP问题,它涉及到最短路线、最小费用等条件下的优化问题.问题一中,我们论证出最少需要3辆邮车才能满足要求.然后对C1区域根据装载量、时间要求遍历出所有的可行路线,最后选出因空车率而减小的收入最小的邮路,其减少的收入为49.35元.问题二中,将整个区域进行划分,在每个小区域应用分枝定界法求出运行成本的路线.再通过对区域的微调讨论出使邮车数目更小的、更节省运行成本的邮路规划方案.问题三中,由于我们将Z55,Z57由县局X1负责运送,Z27由县局X2负责运送.问题四是一个选址问题.我们借助于中心点算法,考虑各支局在本县区域内的位置,并结合与地市局的距离,提出了相应的选址方案.     

k-平均问题及其变形的算法综述

k-平均问题是计算机科学和组合优化领域的经典问题之一.k-平均聚类作为最受重视而且最简单易懂的一种聚类分析方法流行于数据挖掘领域.k-平均问题可描述为:给定n个元素的观测集,其中每个观测点都是d维实向量,目标是把这n个观测点划分到k(≤n)个集合中,使得所有集合中的点到对应的聚类中心的距离的平方和最小,其中一个集合的聚类中心指的是该集合中所有观测点的均值.k-平均问题在理论上是NP-难的,但有高效的启发式算法,广泛应用在市场划分、机器视觉、地质统计学、天文学和农业等实际背景中.随着实际问题中遇到的k-平均问题更加复杂,数据量更加庞大,还需学者进行更深一步的研究.罗列出k-平均问题及其诸多变形及推广问题的经典算法,并总结k-平均中尚待研究的若干问题.     

对三类最短路线问题的探讨

一、网络最短路线问题 例1某城市纵、横分别有6、5条路,构成如图1所示的矩形道路网,（1）从西南角A地到东北角B地,最短路线有多少条？（2）从西南角A地经过C到东北角B地,最短路线共有多少条？     

反超图的笛卡儿积的上色数

讨论反超图的笛卡儿积的着色理论 ,求出了满足一定条件的反超图的笛卡儿积的上色数 .     

矩形网格最短路线探讨

<正>问题如图1所示,m×n矩形网格,沿网格线到对角(从A点到B点)最短路线有几条?分析一(公式法)从A点到B点最短路线,即从A点只能向右、向上走,直到B点结束.最原始的办法是一条一条地数,我们将m=0或n=0的情况(即纵向或横向线段)也包含进去.将结果做成表,见表1.     

灾情巡视路线的设计

本文建模的主要思想是将巡视路线的设计分为两个部分:首先生成一个可行的巡视路线,然后利用启发式算法对巡视路线进行调整优先,对可行路线的生成给出了三种方法,1.采用直观判断,较为简单,2.借鉴了求Hamilton圈的方法,3.基于最小生成树,求出的路线总路程较短,为553.6公理。本文采用方法3得出的路线作为启发式算法的初始路线。 本文提出了一系列启发式算法并采用一定的调整规则对初始路线进行了调整,较好地解决了所提出的问题。对于问题1,给出了均衡度的概念来衡量各组路线的均衡性,解为总路程587.2公理,均衡度0.16;对于问题2,采用点调整的规则求出用4组完成巡视所需的最短的时间22.62小时,对于问题3,采用一种最短路线调整法求出在最短的时间6.43小时内,用22组就可以完成巡视     

点面距离，一招三式

求点到平面的距离是立体几何的重要内容 ,在高考中也经常出现 ,并且直线到平面的距离 ,两个平面间的距离也可以转化成点到平面的距离去求解 .因此 ,点面距离就成了这一类距离问题的交汇点 .直接作出点面距离而得解的例题不多 ,很多情况下都必须把点面距离通过转化变换成较为熟悉简单的模型求解 .本文给出求解点面距离的一招三式———一招 :转化思想 ;三式 :等积转化 ,平行转化 ,比例转化 .下面通过几个具体例子一起来探索题型规律 ,掌握相应的解题方法 .1　等积转化———构造三棱锥模型通过三棱锥模型 ,把点面距离看成棱锥的顶点到对面三…     

图的笛卡儿积及字典式积的连通性

文章给出了两个图的笛卡儿积及字典式的积为最大边连通的、最大连通的、super-λ,super-κ及hyper-κ的充分条件,同时证明了其中一些条件也是必要的.此外,对这两种积的局部割集和广义割集的性质也进行了考虑.     

k-均值算法的初始化方法综述

k-均值问题自提出以来一直吸引组合优化和计算机科学领域的广泛关注, 是经典的NP-难问题之一. 给定N个d维实向量构成的观测集, 目标是把这N个观测点划分到k(\leq N)个集合中, 使得所有集合中的点到对应的聚类中心距离的平方和最小, 一个集合的聚类中心指的是该集合 中所有观测点的均值. k-均值算法作为解决k-均值问题的启发式算法,在实际应用中因其出色的收敛速度而倍受欢迎. k-均值算法可描述为: 给定问题的初始化分组, 交替进行指派(将观测点分配到离其最近的均值点)和更新(计算新的聚类的均值点)直到收敛到某一解. 该算法通常被认为几乎是线性收敛的. 但缺点也很明显, 无法保证得到的是全局最优解, 并且算法结果好坏过于依赖初始解的选取. 于是学者们纷纷提出不同的初始化方法来提高k-均值算法的质量. 现筛选和罗列了关于选取初始解的k-均值算法的初始化方法供读者参考.     

伟大的创造——笛卡儿和解析几何

1596年3月31日,笛卡儿在法国一个名叫拉哈耶的小城里诞生了.他刚出世几天,母亲便溘然长逝,留下虚弱多病的小笛卡儿.笛卡儿从小就十分喜欢科学,他最喜爱听父亲讲一些科学发明的故事,并喜欢寻根究底地问个明白.8岁时,父亲把他送到国王亨利赫四世     

κ-均值算法的初始化方法综述

k-均值问题自提出以来一直吸引组合优化和计算机科学领域的广泛关注,是经典的NP-难问题之一.给定N个d维实向量构成的观测集,目标是把这N个观测点划分到k(≤N)个集合中,使得所有集合中的点到对应的聚类中心距离的平方和最小,一个集合的聚类中心指的是该集合中所有观测点的均值.k-均值算法作为解决k-均值问题的启发式算法,在实际应用中因其出色的收敛速度而倍受欢迎.k-均值算法可描述为:给定问题的初始化分组,交替进行指派(将观测点分配到离其最近的均值点)和更新(计算新的聚类的均值点)直到收敛到某一解.该算法通常被认为几乎是线性收敛的.但缺点也很明显,无法保证得到的是全局最优解,并且算法结果好坏过于依赖初始解的选取.于是学者们纷纷提出不同的初始化方法来提高k-均值算法的质量.现筛选和罗列了关于选取初始解的k-均值算法的初始化方法供读者参考.     

区间直觉模糊集的相似性测度及其应用

在度量两个集合时,用相似性测度来表示两集合的相似性程度.在度量区间直觉模糊集的相似性程度时,现有的很多方法都没有把犹豫度考虑在内.针对这个问题,根据区间直觉模糊集理论,在Szmidt的区间直觉模糊集的海明距离、规范化海明距离、欧几里得距离、规范化欧几里得距离的基础上.定义了基于Szmidt的区间直觉模糊集的加权海明距离和基于Szmidt的区间直觉模糊集的加权欧几里得距离,分别包含了隶属度,非隶属度和犹豫度,并给出了定理和证明.然后定义了两种区间直觉模糊集的相似性测度.最后将这两种相似性测度应用到模式识别领域.     

K2,4× Pn 的交叉数

该文确定了完全二部图 $K_{2,4}$ 与路 $P_n$ 的笛卡儿积图的交叉数.     

有限集相等的性质及其应用

已知元素中含有参数的两个有限集合相等 ,要确定参数或求出集合 .解决这类问题的常用方法是运用分类讨论思想列方程组求解 .其思维过程具有一定的发散性 .因而学生不时出错 .可否回避分类讨论呢 ?笔者发现 ,对两个相等的有限集合 ,由相等的定义可知 ,两个集合中的元素全部相同 .据此可得如下性质 :1 )　两个集合中所有元素之和相等 .2 )　两个集合中所有元素之积相等 .利用这两个性质就可以回避分类讨论而解决上述有限集相等的问题 .例 1　已知M ={2 ,a ,b},N ={2a ,2 ,b2 },且M =N ,求a ,b的值 .解　∵M =N ,∴ 2 +a +b =2a + 2 +b2 ,2a…     

网格中行进路径数的算法

引例如图1所示为某城市道路规划图,计有纵向路7条,横向路5条.若“希望”号公交车从A处出发到B处.试问:从A到B 的最短路线有__条. 解析与上述问题等价的问题是:若规定公交车只能向东或向北方向行驶,则从A处出发到达B处共有__种不同走法.