梁友栋-柏世奇算法
梁友栋—柏世奇算法（以梁友栋和的名字命名）是计算机图形学中的一个线段裁剪算法。梁友栋—柏世奇算法使用直线的参数方程和不等式组来描述线段和裁剪窗口的交集。求解出的交集将被用于获知线的哪些部分是应当绘制在屏幕上的。这一算法比科恩－苏泽兰算法（）要更加高效，梁友栋—柏世奇算法的基本思想是：在计算线段与裁剪窗交集之前做尽可能多的判断。 算法描述 考虑直线的参数方程： :x = x_0 + t (x_1 - x_0) = x_0 + t \Del…
标签：#算法
共 60 篇文章
萊文斯坦距離
莱文斯坦距离（）是编辑距离的一种。指两个字串之間，由一个转成另一个所需的最少编辑操作次数。 允许的编辑操作包括： 将一个字符替换成另一个字符 插入一个字符 刪除一个字符 俄羅斯科學家弗拉基米尔·莱文斯坦在1965年提出這個概念。 定义 如果分别用 |a| 和 |b| 表示 a, b 两个字符串的长度，那么它们的列文斯坦距离为 \operatorname{lev}_{a,b}(|a|,|b|)，它符合： :\qquad\operatorn…
凸包
在一个实数向量空間V中，对于给定集合X，所有包含X的凸集的交集S被称为X的凸包。 : S := \bigcap_{X \subseteq K \subseteq V \atop K\ \mathrm{is\ convex}} K. X的凸包可以用X内所有点(x_1, \ldots, x_n)的线性组合来构造。 : S := \left\{ \left. \, \sum_{j=1}^n t_j x_j\, \right| x_j \in …
算法工程
算法工程是指與计算机算法的设计、分析、实现、优化、剖析和实验评估有關的領域，它在算法理论和软件工程中算法的实际应用之间架起了一座桥梁。1997年，在组织的第一届算法工程研讨会 (WAE97) 上首次提到了算法工程這一說法。 参考文献
预估-校正方法
在数值分析中，预估-校正方法是一类求解常微分方程的算法 - 找到一个未知的函数以满足一定微分方程。 所有这类算法以如下两个步骤进行： 首先，"预估"步，基于之前若干步的一组函数值及导数值拟合出的函数出发，进而外插此函数在后续点的值。 其次，"校正"步，通过使用函数的 预估 值和 另一种方法 改进初始近似，以内插这一未知的函数在相同后续点的值。 预估-校正方法求解常微分方程 对于常微分方程(ODE)的数值解，预估–校正方法通常使用一个显式…
鸵鸟算法
在计算机科学中，鸵鸟算法（）是一个忽略潜在问题的一种算法策略，这种策略对计算机程序可能出现的问题采取无视态度（类似于鸵鸟在遇到危险时将头埋在地里，装作看不见）。鸵鸟算法的使用前提是，问题出现的概率很低。 参考 *[https://web.archive.org/web/20180820080310/http://netsecurity.51cto.com/art/201708/548188.htm 别当鸵鸟！网络安全实施工作中的6大障碍…
速率单调调度算法
速率单调调度算法（，縮寫：RMS）是刘炯朗和J·萊蘭（J. Layland）提出的单处理机实时周期性任务静态优先级调度算法。 该算法的按照任务的速率分配优先级。速率越大，优先级越高；速率越小，优先级越低。 刘炯朗和萊蘭给出了可行调度的充分非必要条件： U=\sum_{i=1}^n{\frac{c_i}{p_i}}\leq{n(\sqrt[n]{2}-1)}. 其中，U是处理机使用率，c是作业的计算时间，p是任务的周期，n是任务的数目。 …
萨瑟兰-霍奇曼算法
萨瑟兰-霍奇曼算法（）是裁剪多边形的算法。它通过轮流延长每个凸多边形的边，并且只选择在可见一侧的顶点来完成任务。 描述 该算法从目标多边形中所有顶点的输入列表开始。接下来，剪裁多边形的一条边在两个方向上无限延伸，同时遍历目标多边形的边。如果输入列表中的顶点位于扩展的剪裁多边形线的可见侧，则它们会插入到输出列表中，并且目标多边形与剪裁多边形的延长后的边相交的顶点会添加到输出列表。 使用一个阶段的输出列表作为下一个阶段的输入列表，对每个剪辑…
激活扩散
激活扩散（）是一种搜索关联网络、生物和人工神经网络或语义网络的方法。这一搜索过程是通过给一组源节点（例如语义网络中的概念）贴上权重或“激活”来启动的，然后迭代地将激活传播或“扩散”到与源节点相连的其他节点。大多数情况下，这些“权重”是真实的数值，伴随激活在网络中的传播而逐渐衰减。当权重值是离散的时，这个过程通常被称为标记传递。激活可能来自不同的路径，由不同的标记识别，并在两个备用路径到达同一节点时终止。大脑研究表明，几个不同的大脑区域在…
模拟退火
，求出连接125个点的最小路线长度]] 模擬退火（，缩写作SA）是一種逼近给定函数全局最优的通用概率演算法，具体来说，它是一种元启发算法，常用來在一定時間內，尋找在一個很大搜尋空間中的近似全局最優解。在有大量局部最优解时，模拟退火算法可以找到全局最优解。 模拟退火常用于搜索空间离散的情形（如旅行推销员问题、布尔可满足性问题、蛋白质结构预测、作业车间调度问题等）。对于在固定时间内找到近似全局最优优先于找到精确局部最优的问题，模拟退火算法可…
贪心算法
贪心算法（），又称-{zh-cn:贪婪; zh-tw:貪心;}-算法，是一种在每一步选择中都采取在当前状态下最好或最优（即最有利）的选择，从而希望导致结果是最好或最优的算法。比如在旅行推销员问题中，如果旅行员每次都选择最近的城市，那这就是一种贪心算法。 贪心算法在有最优子结构的问题中尤为有效。最优子结构的意思是局部最优解能决定全局最优解。简单地说，问题能够分解成子问题来解决，子问题的最优解能递推到最终问题的最优解。 贪心算法与动态规划的…
算法导论
《算法导论》（）是基础算法方面最权威、最详细的著作之一，在很多国际著名大学被用于算法课的教材。诸多算法方面的论文将其列入参考文献当中。 该书详细的介绍了诸多常见的算法及数据结构，并用严谨的证明来论证其正确性。每个章节均有例题，适合学习者深入理解。第一版刊行于1990年，2022年最新版为第四版。在许多国家常常以作者姓名首个英文字母被称为CLRS（第一版则简称为CLR）。 参见 计算理论 可计算性理论 計算複雜性理論 计算机程序设计艺术 …
多数投票算法
博耶-摩尔多数投票算法（）,中文常作多数投票算法、摩尔投票算法等，是一种用来寻找一组元素中占多数元素的常数空间复杂度、线性时间复杂度算法。这一算法由和在1981年发表，也是的一种典型算法。 这一算法应用的问题原型是在集合中寻找可能存在的多数元素，这一元素在输入的序列重复出现并占到了序列元素的一半以上；在第一遍遍历之后应该再进行一个遍历以统计第一次算法遍历的结果出现次数，确定其是否为众数；如果一个序列中没有占到多数的元素，那么第一次的结果…
左偏树
左偏树（），也可称为左偏堆、左倾堆，是计算机科学中的一种树，是一种优先队列实现方式，属于可并堆，在信息学中十分常见，在统计问题、最值问题、模拟问题和贪心问题等等类型的题目中，左偏树都有着广泛的应用。斜堆是比左偏树更为一般的数据结构。 不同于斜堆合并的,左偏堆的合并操作的为 O(log n)，而完全二叉堆为 O(n)，所以左偏堆适合基于合并操作的情形。 由于左偏堆已经不是完全二叉树，因此不能用数组存储表示，需要用链接结构。 定义 左偏树是…
禁忌搜索
禁忌搜索（，TS，又稱禁忌搜尋法）是一種現代啟發式算法，由美國科罗拉多大学教授弗雷德·格洛弗于1986年左右提出，并于1989年实现规范化。这种搜寻法是一個用來跳脫局部最优解的搜索方法。其先创立一個初始化的方案；基于此，算法“移动”到一相邻的方案。經過許多连续的移動过程，提高解的质量。 参考文献
最小生成树
和它的最小生成树。在该图中，边的长度正比于权值A。]] 最小生成树（，簡稱MST）是最小權重生成樹（）的簡稱，是一个连通加权无向图中一棵权值最小的生成树。 在一給定的無向圖 G = (V, E) 中，(u, v) 代表連接頂點 u 與頂點 v 的邊（即 (u, v)\in E），而 w(u, v) 代表此邊的權重，若存在 T 為 E 的子集（即 T\subseteq E）且 (V, T) 為樹，使得： :w(T) = \sum_{(u,…
最大期望算法
最大期望演算法（，又譯期望最大化算法）在统计中被用于寻找，依赖于不可观察的隐性变量的概率模型中，参数的最大似然估计。 在统计计算中，最大期望（EM）算法是在概率模型中寻找参数最大似然估计或者最大后验估计的算法，其中概率模型依赖于无法观测的隐变量。最大期望算法经常用在机器学习和计算机视觉的数据聚类（Data Clustering）领域。最大期望算法经过两个步骤交替进行计算，第一步是计算期望（E），利用对隐藏变量的现有估计值，计算其最大似然…
德卡斯特里奥算法
数学子领域数值分析中的德卡斯特里奥算法（），以发明者保尔·德·卡斯特里奥命名，是计算伯恩斯坦形式的多项式或貝茲曲線的递归方法。 虽然对于大部分的体系结构，该算法和直接方法相比较慢，但它在数值上更为稳定。 定义 贝兹曲线B（角度为n，控制点\beta_0, \ldots, \beta_n）可用以下方式运用德卡斯特里奥算法 :B(t) = \sum_{i=0}^{n}\beta_{i}b_{i,n}(t) , 其中b为 : b_{i,n}(…
伪代码
伪代码（），又称为-{zh-cn:虚拟代码; zh-tw:偽代碼; zh-hk:虛擬代碼;}-，是一种高层次描述算法的方法。它不是现实存在的编程语言（已经出现了类似伪代码的语言，参见Nuva）；它可能综合使用多种编程语言的语法、保留字，甚至会用到自然语言。 它以编程语言的书写形式指明算法的职能。相比于程序语言（例如Java、C++、C、Delphi 等等）它更类似自然语言。它是-{zh-hans:半形式化;zh-hant:半形式化}-、…
数据结构与算法术语列表
本列表参考《NIST数据结构与算法词典》撰写，該词典为美国国家标准协会（NIST）所出版。它收集了大量计算机科学技术与数据结构和算法的相關條目。 为了方便对照查找，本列表按照术语的英语拼写组织排序。 NOTOC A 绝对性能保证（absolute performance guarantee） 抽象数据类型（abstract data type） （a,b）-树（(a,b)-tree） 接收状态（accepting state） 阿克曼函…