type
status
date
slug
summary
tags
category
icon
password
Property
稀疏矩阵（英语：sparse matrix）指的是在数值分析中绝大多数数值为零的矩阵。反之，如果大部分元素都非零，则这个矩阵是稠密的(Dense)。
在科学与工程领域中求解线性模型时经常出现大型的稀疏矩阵。
上图中左边就是一个稀疏矩阵，可以看到包含了很多 0 元素，右边是稠密的矩阵，大部分元素不是 0。
看一个简单例子：
上述稀疏矩阵仅包含 9 个非零元素，另外包含 26 个零元。其稀疏度为 74%，密度为 26%。
SciPy 的
scipy.sparse模块提供了处理稀疏矩阵的函数。我们主要使用以下两种类型的稀疏矩阵：
- CSC - 压缩稀疏列（Compressed Sparse Column），按列压缩
- CSR - 压缩稀疏行（Compressed Sparse Row），按行压缩
CSR 矩阵
type
status
date
slug
summary
tags
category
icon
password
Property
图结构是算法学中最强大的框架之一。
图是各种关系的节点和边的集合，节点是与对象对应的顶点，边是对象之间的连接。
SciPy 提供了 scipy.sparse.csgraph 模块来处理图结构。
邻接矩阵
邻接矩阵（Adjacency Matrix）是表示顶点之间相邻关系的矩阵。
邻接矩阵逻辑结构分为两部分：V 和 E 集合，其中，V 是顶点，E 是边，边有时会有权重，表示节点之间的连接强度。
用一个一维数组存放图中所有顶点数据，用一个二维数组存放顶点间关系（边或弧）的数据，这个二维数组称为邻接矩阵。
看下下图实例：
顶点有 A、B、C，边权重有 1 和 2。
A 与 B 是连接的，权重为 1。
type
status
date
slug
summary
tags
category
icon
password
Property
空间数据又称几何数据，它用来表示物体的位置、形态、大小分布等各方面的信息，比如坐标上的点。
SciPy 通过 scipy.spatial 模块处理空间数据，比如判断一个点是否在边界内、计算给定点周围距离最近点以及给定距离内的所有点。
三角测量
三角测量在三角学与几何学上是一借由测量目标点与固定基准线的已知端点的角度，测量目标距离的方法。
多边形的三角测量是将多边形分成多个三角形，我们可以用这些三角形来计算多边形的面积。
拓扑学的一个已知事实告诉我们：任何曲面都存在三角剖分。
假设曲面上有一个三角剖分， 我们把所有三角形的顶点总个数记为 p(公共顶点只看成一个)，边数记为 a，三角形的个数记为 n，则 e=p-a+n 是曲面的拓扑不变量。 也就是说不管是什么剖分，e 总是得到相同的数值。 e 被称为称为欧拉示性数。
对一系列的点进行三角剖分点方法是 Delaunay() 三角剖分。
注：三角形顶点的 id 存储在三角剖分对象的 simplices 属性中
type
status
date
slug
summary
tags
category
icon
password
Property
ODR代表正交距离回归，用于回归研究。 基本线性回归通常用于通过在图上绘制最佳拟合线来估计两个变量
y和x之间的关系。用于此的数学方法称为最小平方，旨在最小化每个点的平方误差总和。 这里的关键问题是如何计算每个点的误差(也称为残差)？在一个标准的线性回归中，目的是从
X值预测Y值 ， 因此明智的做法是计算Y值的误差(如下图所示的灰线所示)。 但是，有时考虑X和Y的误差(如下图中的红色虚线所示)更为明智。例如 当知道对
X的测量是不确定的，或者当不想关注一个变量相对于另一个变量的错误时。
正交距离回归(ODR)是一种可以做到这一点的方法(正交在这里表示为垂直 - 所以它计算垂直于线的误差，而不仅仅是’垂直’)。
单变量回归的scipy.odr实现
type
status
date
slug
summary
tags
category
icon
password
Property
图的基本概念
- 图（Graph）：图是由若干顶点和连接顶点的边所构成关系结构
- 顶点（Node）：图中的点称为顶点，也称节点
- 边（Edge）：顶点之间的连线，称为边
- 平行边（Parallel edge）：起点相同、终点也相同的两条边称为平行边
- 循环（Cycle）：起点和终点重合的边称为循环
- 有向图（Digraph）：图中的每条边都带有方向，称为有向图
- 无向图（Undirected graph）：图中的每条边都没有方向，称为无向图
- 赋权图（Weighted graph）：图中的每条边都有一个或多个对应的参数，称为赋权图。该参数称为这条边的权，权可以用来表示两点间的距离、时间、费用
- 度（Degree）：与顶点相连的边的数量，称为该顶点的度
图、顶点和边的操作
Networkx很容易创建图、向图中添加顶点和边、从图中删除顶点和边，也可以查看、删除顶点和边的属性
type
status
date
slug
summary
tags
category
icon
password
Property
最短路径问题是图论研究中的经典算法问题，用于计算图中一个顶点到另一个顶点的最短路径。
- 在图论中，最短路径长度与最短路径距离却是不同的概念和问题，经常会被混淆
- 求最短路径长度的常用算法是 Dijkstra 算法、Bellman-Ford 算法和Floyd 算法，另外还有启发式算法 A*
最短路径问题
最短路径问题是图论研究中的经典算法问题，用于计算图中一个顶点到另一个顶点的最短路径。
最短路径问题有几种形式：确定起点的最短路径，确定终点的最短路径，确定起点和终点的最短路径，全局最短路径问题。
最短路径长度与最短路径距离
在日常生活中，最短路径长度与最短路径距离好像并没什么区别。但在图论中最短路径长度与最短路径距离却是不同的概念和问题，经常会被混淆。
图论中有无权图和有权图，无权图中的边没有权，赋权图的边带有权，可以表示距离、时间、费用或其它指标。在问题文字描述中，往往并不直接指出是无权图还是有权图，这时就要特别注意最短路径与最短加权路径的区别。
路径长度是把每个顶点到相邻顶点的长度记为 1，而不是指这两个顶点之间道路的距离——两个顶点之间的道路距离是 连接边的权（weight）。
通俗地说，路径长度可以认为是飞行棋的步数，或者公交站点的站数，相邻顶点之间为一步，相隔几个顶点就是几站。路径长度是从路径起点到终点的步数，计算最短路径是要计算从起点到终点步数最少的路径。
如果问题不涉及相邻顶点间的距离，要计算从起点到终点的最短路径及对应的最短路径长度，是指这条路径从起点到终点有几步（站），在图论中称为最短路径长度。但是，如果问题给出相邻顶点之间的道路长度或距离，姑且称为各路段的距离，要计算从起点到终点的最短路径及对应的最短距离，显然并不是要找经过最少步数的路径，而是在找路径中各路段的距离之和最小的路径，在图论中称为最短加权路径长度——这里权重是路段距离。
type
status
date
slug
summary
tags
category
icon
password
Property
最短路径问题是图论中求两个顶点之间的最短路径问题，通常是求最短加权路径。
条件最短路径，指带有约束条件、限制条件的最短路径。例如，顶点约束，包括必经点或禁止点的限制；边的约束，包括必经路段或禁止路段；还包括无权路径长度的限制，即经过几步到达终点。进一步地，还有双目标限制的最短路径问题，求最短距离中花费最小的路线；交通限制条件下的最短路径问题，需要考虑转向限制和延误的约束。
求解带有限制条件的最短路径问题，总体可以分为两类基本方法：一类是基于不带限制条件的最短路径算法，对求解过程中的每一条有效路径，都用限制条件进行判断，如果满足所有限制条件则继续，如果不满足限制条件则放弃该路径；另一类方法是基于具体问题和选择算法的特点，将问题转化为有约束的规划问题来处理。
但是，如果使用 NetworkX 求解带有限制条件的最短路径问题，采用这两类方法都会有一些困难。原因在于NetworkX 提供的 Dijkstra 算法、Bellman-Ford 算法、Floyd 算法和启发式算法 A* 都是封装函数，没有提供设置约束条件的选项和接口，因此用户不能把条件判断语句加入这些封装函数的程序内部。
不过，NetworkX 可以生成两个顶点之间的所有简单路径，而且可以获得所有简单路径的边的列表。利用简单路径算法，可以通过对约束条件的判断来求解带有顶点约束和边约束的最短路径问题。
问题案例：蚂蚁的最优路径分析
蚁巢有若干个储藏间（图中圆圈表示），储藏间之间有路径相连（路径拓扑结构如图所示）。该图为无向图，路径通行的花费如图中线路上的数字所示，路径正反方向通行的花费相同。要求从起点 N0 到终点 N17 的最优路径，并需要满足限制条件：
- 需要尽可能以最少的花费到达终点；
- 必须经过图中的绿色节点；
- 必须经过图中的两段绿色路段；
- 必须避开图中的红色路段。
type
status
date
slug
summary
tags
category
icon
password
Property
- 最小生成树（MST）是图论中的基本问题，具有广泛的实际应用
- 路线设计、道路规划、官网布局、公交路线、网络设计，都可以转化为最小生成树问题，如要求总线路长度最短、材料最少、成本最低、耗时最小。
- 最小生成树的典型算法有普里姆算法（Prim算法）和克鲁斯卡算法（Kruskal算法）。
最小生成树
生成树
树是图论中的基本概念。连通的无圈图称为树（Tree），就是不包含循环的回路的连通图。
对于无向连通图，如下图所示，生成树（Spanning tree）是原图的极小连通子图，它包含原图中的所有 个顶点，并且有保持图连通的最少的边，即只有足以构成一棵树的条边。
生成树满足：（1）包含连通图中所有的顶点；（2）任意两顶点之间有且仅有一条通路。因此，生成树中边的数量 = 顶点数 - 1。
对于非连通无向图， 遍历每个连通分量中的顶点集合所经过的边是多颗生成树，这些连通分量的生成树构成非连通图的生成森林 。
最小生成树和最大生成树
遍历连通图的方式通常有很多种，也就是说一张连通图可能有多种不同的生成树
type
status
date
slug
summary
tags
category
icon
password
Property
- 流在生活中十分常见，例如交通系统中的人流、车流、物流，供水管网中的水流，金融系统中的现金流，网络中的信息流。网络流优化问题是基本的网络优化问题，应用非常广泛
- 网络流优化问题最重要的指标是边的成本和容量限制，既要考虑成本最低，又要满足容量限制，由此产生了网络最大流问题、最小费用流问题、最小费用最大流问题
网络流优化
网络流
网络流优化问题是基本的网络优化问题，应用非常广泛，遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等领域。
流从源点流出、通过路径输送、流入到汇点，从而将目标从源点输送到汇点。流在生活中十分常见，例如交通系统中的人流、车流、物流，供水管网中的水流，金融系统中的现金流，网络中的信息流。
现实中的任何路径都有最大流量（容量）的限制，在网络中也是如此，并以边的容量（Capacity）表示，一条边的流量不能超过它的容量。
把这些现实问题抽象为网络流问题，其特征是：（1）有向图上的每条边具有容量限制；（2）从源点流出的流量，等于汇点流入的流量；（3）源点和汇点之外的所有中间节点，流出的流量等于流入的流量。
注意在网络流问题中有几组概念容易混淆：
- 源点/汇点，起点/终点，供应点/需求点：源点是只进不出的点，汇点是只出不进的点。源点/汇点 可以指定为问题的 起点/终点，但本质上源点/汇点是由网络结构特征决定的，而不是被指定的。供应点的供应量和需求点的需求量是固定/确定的，而源点/汇点的目标是发出/接收的流量最大，不是固定值。
- 容量 与 流量：容量是路径（边、弧）允许的最大流通能力，用 c(i,j) 表示；流量则是路径（边、弧）上的实际流量，用 f(i,j) 表示。
典型的网络流优化问题
type
status
date
slug
summary
tags
category
icon
password
Property
流在生活中十分常见，例如交通系统中的人流、车流、物流，供水管网中的水流，金融系统中的现金流，网络中的信息流。网络流优化问题是基本的网络优化问题，应用非常广泛，遍及通讯、运输、电力、工程规划、任务分派、设备更新以及计算机辅助设计等领域。
网络流优化问题最重要的指标是每条边的成本和容量限制，既要考虑成本最低（最短路径问题），又要满足容量限制（最大流问题），由此产生了网络最大流问题、最小费用流问题和最小费用最大流问题。
不论在实际工作中，还是在数模竞赛中，网络最大流问题、最小费用流问题和最小费用最大流问题都有很多延伸和推广的应用。
本文选择多源多汇物流转运问题、多商品流问题案例，详细介绍网络流问题的分析方法和解决方案，并使用线性规划方法建模和编程。
网络最大流问题的应用与推广
指定流量的可行流
网络最大流的算法如果不是计算最大流，而是要计算指定流量 v 的可行流，可以用如下图所示的增广路（相当于辅助线）方法处理。
（1）在容量网络 G 上增加一个顶点 t’ 和一条边 (t,t’)，构建一个新的容量网络 G’，令边 (t,t’) 的容量为 v；
（2）对于容量网络 G‘，计算从源点 s 到汇点 t’ 的最大流 ，显然 ；
（3）若 ，则容量网络 G 不存在满足流量 v 的可行流；若，则从最大流 的路径中去掉边 (t,t’) 即得到容量网络 G 满足流量 v 的可行流。
另一种思路是，设置源点 s /汇点 t 的流量为 v，再按最小费用流即可。这种方法不仅得到了流量 v 的可行流，而且是最小费用流，但该方法的计算量较大。