张拓的博客

Alpha-beta剪枝是一种搜索算法，用以减少极小化极大算法（Minimax算法）搜索树的节点数。这是一种对抗性搜索算法，主要应用于机器游玩的二人游戏（如井字棋、象棋、围棋）。当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝。 历史Allen Newell和Herbert A. Simon在1958年，使用了John McCarthy所谓的“近似”alpha-beta算法，此算法当时“应已重新改造过多次”。Arthur Samuel有一个早期版本，同时Richards、Hart、Levine和/或Edwards在美国分别独立发现了alpha-beta。McCarthy在1956年达特默思会议上提出了相似理念，并在1961年建议给他的一群学生，其中包括MIT的Alan Kotok。Alexander Brudno独立发现了alpha-beta算法，并在1963年发布成果。Donald Knuth和Ronald W. Moore在1975年优化了算法，Judea Pearl在1982年证明了其最 ...

倒排索引（英语：Inverted index），也常被称为反向索引、置入文件或反向文件，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。 有两种不同的反向索引形式： 一条记录的水平反向索引（或者反向文件索引）包含每个引用单词的文档的列表。 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。 后者的形式提供了更多的兼容性（比如短语搜索），但是需要更多的时间和空间来创建。 例子以英文为例，下面是要被索引的文本： {\displaystyle T_{0}=}0. "it is what it is" {\displaystyle T_{1}=}1. "what is it" {\displaystyle T_{2}=}2. "it is a banana" 我们就能得到下面的反向文件索引： 12345"a": {2}"banana": {2
...

哈希函数（英语：Hash function）又称散列算法、哈希函数，是一种从任何一种数据中创建小的数字“指纹”的方法。哈希函数把消息或数据压缩成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做哈希值（hash values，hash codes，hash sums，或hashes）的指纹。哈希值通常用一个短的随机字母和数字组成的字符串来代表。[1]好的哈希函数在输入域中很少出现哈希冲突。在哈希表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更难找到。 如今，散列算法也被用来加密存在数据库中的密码（password）字符串，由于散列算法所计算出来的散列值（Hash Value）具有不可逆（无法逆向演算回原本的数值）的性质，因此可有效的保护密码。 哈希函数的性质所有哈希函数都有如下一个基本特性：如果两个哈希值是不相同的（根据同一函数），那么这两个哈希值的原始输入也是不相同的。这个特性是哈希函数具有确定性的结果，具有这种性质的哈希函数称为单向哈希函数。但另一方面，哈希函数的输入和输出不是唯一对应关系的，如果两个哈希值相同，两个输入值很可能是相同的，但也 ...

在计算机科学中，二分查找算法（英语：binary search algorithm），也称折半搜索算法（英语：half-interval search algorithm）、对数搜索算法（英语：logarithmic search algorithm），是一种在有序数组中查找某一特定元素的搜索算法。搜索过程从数组的中间元素开始，如果中间元素正好是要查找的元素，则搜索过程结束；如果某一特定元素大于或者小于中间元素，则在数组大于或小于中间元素的那一半中查找，而且跟开始一样从中间元素开始比较。如果在某一步骤数组为空，则代表找不到。这种搜索算法每一次比较都使搜索范围缩小一半。 二分查找算法在最坏情况下是对数时间复杂度的，需要进行{\displaystyle O(\log n)}次比较操作（{\displaystyle n}在此处是数组的元素数量，{\displaystyle O}是大O记号，{\displaystyle \log }是对数）。二分查找算法使用常数空间，对于任何大小的输入数据，算法使用的空间都是一样的。除非输入数据数量很少，否则二分查找算法比线性搜索更快，但数组必须事先被排序。尽 ...

维基百科，自由的百科全书跳到导航跳到搜索在计算机科学中，X算法可用来求解精确覆盖问题。此名称最早在高德纳的论文《舞蹈链》中出现，他认为此算法是“试错法中最显而易见”的。 就技术而言，X算法是一个深度优先的不确定性回溯算法。由于X算法是一个解决精确覆盖问题的简洁方法，高德纳希望通过该算法体现舞蹈链数据结构的高效性，他把使用后者的X算法称为DLX。 X算法用由0和1组成的矩阵A来表示精确覆盖问题，目标是选出矩阵的若干行，使得其中的1在所有列中出现且仅出现一次。 X算法的步骤如下： 如果矩阵A为空（没有任何列），则当前局部解即为问题的一个解，返回成功；否则继续。 根据一定方法选择第c列。如果某一列中没有1，则返回失败，并去除当前局部解中最新加入的行。 选择第r行，使得Ar, c = 1（该步是不确定的）。 将第r行加入当前局部解中。 对于满足Ar, j = 1的每一列j，从矩阵A中删除所有满足Ai, j = 1的行，最后再删除第j列。 对所得比A小的新矩阵递归地执行此算法。 选择r的不确定性意味着算法将派生出若干独立的子算法，每个子算法都从其父算法中继承了去除部分行列的A矩阵。如果其中有 ...

线性散列（英语：Linear Hashing）是一种散列方法，它有几项特点： 没有目录。 可借由控制负荷因子来延迟分裂。 分裂指标 ：指向下一个要分裂的资料栏，在完整扩张后要重设分裂指标。 档案等级 ：在完整扩张后要档案等级。 区块数目 ：区块数目会线性增加。 算法插入 输入资料先放入同一资料栏内，每次输入资料都要运算负荷因子，以便检查负荷因子是否超过门槛，如果超过负荷因子，则要针对分裂指标所指的资料栏进行完整扩张。 如果完整扩张则要重设分裂指标，而完整扩张会使分裂因子所指的资料栏分裂为原来的两倍。 持续输入资料直到资料输入完毕。 原文地址：https://zh.wikipedia.org/wiki/%E7%B7%9A%E6%80%A7%E9%9B%9C%E6%B9%8A 在知识共享 署名-相同方式共享 3.0协议之条款下提供

对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致，但不需要任何冲突解决方案。在数学术语中，这是一个完全单射函数. 特性及使用对于特定集合S的完美散列函数能在常数时间中被计算出，其映射值在一个相对小的范围内，能被一个随机化算法发现，该算法的操作次数与S的大小成正比.任何适合在哈希表中使用的完美散列函数需要至少与S的大小成正比的位数。 一个值的位数被限定范围的完美散列函数能应用于高效查找操作中：假定查找键(key)与集合S（或与集合S关联的值）对应，然后将完美散列函数应用于查找键，得到哈希值（一个整数），然后在查找表中取出该整数对应的值。在集合S极少更新且查询频率非常多的情况下，使用完美hash函数是非常有效的。对集合S更新频率的限定是由于对任何集合S的修改，都将导致该完美散列函数退化为非完美散列函数。每次集合S被修改后自动更新hash函数的解决方案被称为dynamic perfect hashing，但这类方法非常复杂，难以实现。一个简单的允许动态更新集合S的完美散列函数的替代品叫cuckoo hashing ...

在模式识别领域中，最近邻居法（KNN算法，又译K-近邻算法）是一种用于分类和回归的非参数统计方法。在这两种情况下，输入包含特征空间（Feature Space）中的k个最接近的训练样本。 在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。 在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。最近邻居法采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。 K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。 无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。 邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明确的训 ...

A*搜索算法（A* search algorithm）是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或网络游戏的BOT的移动计算上。 该算法综合了最良优先搜索和Dijkstra算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（需要评估函数满足单调性）。 在此算法中，如果以{\displaystyle g(n)}表示从起点到任意顶点{\displaystyle n}的实际距离，{\displaystyle h(n)}表示任意顶点{\displaystyle n}到目标顶点的估算距离（根据所采用的评估函数的不同而变化），那么A*算法的估算函数为： {\displaystyle f(n)=g(n)+h(n)}这个公式遵循以下特性： 如果{\displaystyle g(n)}为0，即只计算任意顶点{\displaystyle n}到目标的评估函数{\displaystyle h(n)}，而不计算起点到顶点{\displaystyle n}的距离，则算法转化为使用贪心策略的最良优先搜索，速度最快，但可能得不出最优解； 如 ...

计数排序（Counting sort）是一种稳定的线性时间排序算法。该算法于1954年由 Harold H. Seward 提出。计数排序使用一个额外的数组{\displaystyle C} ，其中第i个元素是待排序数组{\displaystyle A}中值等于{\displaystyle i}的元素的个数。然后根据数组{\displaystyle C} 来将{\displaystyle A}中的元素排到正确的位置。 计数排序的特征当输入的元素是{\displaystyle n}个{\displaystyle 0}到{\displaystyle k} 之间的整数时，它的运行时间是{\displaystyle \Theta (n+k)}。计数排序不是比较排序，因此不被 {\displaystyle \Omega (n\log n)}的下界限制。 由于用来计数的数组{\displaystyle C} 的长度取决于待排序数组中数据的范围（等于待排序数组的最大值与最小值的差加上1），这使得计数排序对于数据范围很大的数组，需要大量时间和内存。例如：计数排序是用来排序0到100之间的数字的最好的算 ...