算法
  1. Dotcpp
  2. 算法

列表

简述随机增量法

简述随机增量法

随机增量算法是计算几何的一个重要算法，它对理论知识要求不高，算法时间复杂度低，应用范围广大。增量法(IncrementalAlgorithm)的思想与第一数学归纳法类似，它的本质是将一个问题化为规模刚好小一层的子问题。解决子问题后加入当前的对象。
计算几何 2022年04月05日
半平面交的定义和解法

半平面交的定义和解法

一、定义半平面交是什么？我们知道一条直线可以把平面分为两部分，其中一半的平面就叫半平面。那半平面交，就是多个半平面的相交部分。我们在学习线性规划时就有用过。（1）半平面一条直线和直线的一侧。半平面是一个点集，因此是一条直线和直线的一侧构成的点集。
计算几何 2022年04月11日
简述旋转卡壳

简述旋转卡壳

1978年，M.I.Shamos'sPh.D.的论文"ComputationalGeometry"标志着计算机科学的这一领域的诞生。当时他发表成果的是一个寻找凸多边形直径的一个非常简单的算法，即根据多边形的一对点距离的最大值来确定。一、定义旋转卡壳算法在凸包算法的基础上，
计算几何 2022年02月04日
什么是凸包？

什么是凸包？

凸包（ConvexHull）是一个计算几何（图形学）中的概念。在一个实数向量空间V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。X的凸包可以用X内所有点(X1，...Xn)的线性组合来构造.在二维欧几里得空间中，凸包可想象为一条刚好包著所有点的橡皮圈。
计算几何 2022年01月25日
二分图的最大匹配、完美匹配和匈牙利算法

二分图的最大匹配、完美匹配和匈牙利算法

二分图：简单来说，如果图中点可以被分为两组，并且使得所有边都跨越组的边界，则这就是一个二分图。准确地说：把一个图的顶点划分为两个不相交集U和V，使得每一条边都分别连接U、V中的顶点。如果存在这样的划分，则此图为一个二分图。二分图的一个等价定义是：不含有「含奇数条边的环」的图。
图论 2022年01月30日
什么是Prufer序列？

什么是Prufer序列？

Prufer序列可以将一个带标号n个结点的树用[1,n]中的n-2个整数表示。你也可以把它理解为完全图的生成树与数列之间的双射。显然你不会想不开拿这玩意儿去维护树结构。这玩意儿常用组合计数问题上。HeinzPrufer于1918年发明这个序列来证明凯莱定理。
图论 2022年02月11日
简述LGV引理

简述LGV引理

LGV引理可以用于在DAG上求解不相交路径方案数问题，下面我们简单介绍一下。一、简介LGV引理英文全称是Lindström–Gessel–Viennotlemma，可以用来处理有向无环图上不相交路径计数等问题。在此之前，大家要先了解图论相关概念、矩阵、高斯消元求行列式等知识，
图论 2022年04月20日
什么是弦图？

什么是弦图？

什么是弦图？下面的图我们看到后，第一感觉应该虽然看着很酷炫，但是会感觉很复杂，感觉无所适从，不知怎么来看这个图表。今天我们就来介绍下这个图表是怎么用的？这个图表叫做弦图，弦图主要用于展示多个对象之间的关系，连接圆上任意两点的线段叫做弦，弦（两点之间的连线）就代表着两者之间的关联关系。
图论 2022年01月18日
简述最大团搜索算法

简述最大团搜索算法

一、引入在计算机科学中，团问题指的是在给定的图中找到团（顶点的子集，都彼此相邻，也称为完全子图）的计算问题。团的问题在现实生活中也有体现。例如我们考虑一个社交网络，其中图的点代表用户，图的边代表其所连接的两个用户互相认识。那么我们找到了一个团，也就找到了一群互相认识的人。
图论 2022年05月24日
上下界网络流总结

上下界网络流总结

上下界网络流可以看做普通网络流的升级版，现在对于流量网络，我们不再只关注其流量的上界，而是同时关注流量的上下界。一、无源汇有上下界可行流这是上下界网络流中最简单的一种，给定一个没有源点和汇点、每条边的流量有上下界的流量网络，问是否存在一种可行流使得流量平衡。
图论 2022年02月01日