极小化极大算法
Minimax算法（亦稱 MinMax or MM）又名极小化极大算法，是一种找出失败的最大可能性中的最小值（最小化最坏情况）的算法。 概述 Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。很多棋类游戏可以采取此算法，例如井字棋（tic-tac-toe）。 偽代碼 function minimax(no…
标签：#搜尋演算法
共 34 篇文章
格罗弗算法
格罗弗算法（）是一種量子算法，於1996年由電腦科學家洛夫·格罗弗提出。假設現在有一個未知的函數，格罗弗算法只需測試此未知的函數O(\sqrt{N})次，其中N為此未知函數的定义域的大小，即可以很高的概率找到一特定的輸入值，此輸入值能使此未知函數輸出特定的值。 同樣的問題在經典運算下，需要至少做 O(N) 次測試（因為在最壞的情況下，可能第N個定義域裡的值才是正確答案）。在格罗弗發表他的算法前後，Bennett, Bernstein, …
二分搜尋
{{各地中文名 | t = 1 | name = | cn = | hk = 二分查找（）是用于查找有序数组中目标值位置的搜索算法。二分查找比较目标值与数组中间元素的大小，如果两者不相等，则会舍弃不可能包含目标值的那一半区间，然后在剩余区间重复此过程：每次选取新的中间元素并与目标值比较，直至找到目标或区间为空。若区间为空，则说明目标值不存在。 二分查找在下的时间复杂度为对数级别，即需做O(\log n)次比较，其中n是数组元素的数量。除…
K-近邻算法
在模式识别领域中，最近鄰居法（KNN算法，又譯K-近邻算法）是一种用于分类和回归的無母數統計方法，由美国统计学家伊芙琳·费克斯和小約瑟夫·霍奇斯于1951年首次提出，后来由扩展。在这两种情况下，输入包含特徵空間中的k个最接近的训练样本。 : 在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的…
Alpha-beta剪枝
Alpha-beta剪枝是一种搜索算法，用以减少极小化极大算法（Minimax算法）搜索树的节点数。这是一种对抗性搜索算法，主要应用于机器游玩的二人游戏（如井字棋、象棋、围棋）。当算法评估出某策略的后续走法比之前策略的还差时，就会停止计算该策略的后续发展。该算法和极小化极大算法所得结论相同，但剪去了不影响最终决定的分枝。 历史 Allen Newell和Herbert A. Simon在1958年，使用了John McCarthy所谓的…
搜索算法
在计算机科学中，搜索算法是解决搜索问题的任何算法（即检索存储在某个数据结构中的信息，或者在问题的可行域中计算的信息。）这种结构的例子包括但不限于链表，数组或搜索树，合适的搜索算法通常取决于正在搜索的数据结构，并且还可能包括有关数据的先前知识。搜索还包含查询数据结构的算法，例如SQL SELECT命令。 搜索算法可以根据搜索机制进行分类。线性搜索算法以线性方式检查每个与目标关键字关联的记录。二分或折半搜索（二分查找算法）重复定位搜索结构的…
完美散列
对集合S的完美散列函数是一个将S的每个元素映射到一系列无冲突的整数的哈希函数。一个完美散列函数的应用与其他哈希函数的应用基本一致，但不需要任何冲突解决方案。在数学术语中，这是一个完全单射函数. 特性及使用 对于特定集合S的完美散列函数能在常数时间中被计算出，其映射值在一个相对小的范围内，能被一个随机化算法发现，该算法的操作次数与S的大小成正比.任何适合在哈希表中使用的完美散列函数需要至少与S的大小成正比的位数。 一个值的位数被限定范围的…
舞蹈链
问题的舞蹈链算法]] 在计算机科学中，舞蹈链（Dancing Links）算法，也叫DLX算法，是一种高德纳提出的数据结构，用于是快速实现他提出的的X算法。 X算法是一种递归算法，时间复杂度不确定，深度优先，通过回溯寻找精确覆盖问题所有可能的解。有一些著名的精确覆盖问题，包括铺砖块，八皇后问题，数独问题。 这一算法的名字来自于这个算法的工作方式。算法中的迭代让链接与同伴链接"跳舞"，很像“精心编排的舞蹈”。 该算法归功于 Hiroshi…
彩虹表
彩虹表（）是计算机安全领域中一种用于攻击密码散列函数的预计算表，主要用于在有限的时间内破解存储的密码哈希值。 彩虹表是时空权衡（Time-Memory Trade-off）理论的典型应用。它在暴力破解（花费大量时间、少量存储）和简单的查找表（花费少量时间、巨量存储）之间取得了平衡。通过预先计算并存储特殊的“哈希链”，彩虹表能够以比暴力破解快得多的速度破解哈希，同时所需的存储空间远小于存储所有可能哈希值的全量查找表。 彩虹表技术通常用于破…
线性搜索
在计算机科学中，线性搜索或顺序搜索是一种寻找某一特定值的搜索算法，指按一定的顺序检查数组中每一个元素，直到找到所要寻找的特定值为止。是最简单的一种搜索算法。 分析 假设一个数组中有 n 个元素，最好的情况就是要寻找的特定值就是数组里的第一个元素，这样仅需要1次比较就可以。而最坏的情况是要寻找的特定值不在这个数组或者是数组里的最后一个元素，这就需要进行 n 次比较。 實作範例 Julia (程式語言) Julia Sample: Line…
戴克斯特拉算法
{{Infobox algorithm |class=搜索算法 |image=Dijkstra Animation.gif |caption = 戴克斯特拉算法运行演示（找到A，B之间的最短路），本算法每次取出未访问结点中距离最小的，用该结点更新其他结点的距离。在演示过程中访问过的结点会被标为红色。 |data=图 堆/优先队列（算法优化） |best-time= |average-time= |SpaceComp=O(|E|+|V|)…
哈希表
散列表（）是根据键而直接访问在記憶體儲存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来讓人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名x到首字母F(x)的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取…
爬山算法
爬山算法是一种局部择优的方法，采用启發式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 透過爬山演算法解決凸問題的演算法包括線性規劃的單體法和二分搜尋。 爬山算法一般存在以下问题： #局部最大 #高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 #山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。 解决方法：随机重启爬山算法 參見 梯度下降法 貪婪演算法 瓦尔拉斯拍卖 …
迭代深化深度优先搜索
迭代深化深度优先搜索 （iterative deepening depth-first search (IDS or IDDFS)）是对状态空间的搜索策略。它重复地运行一个有深度限制的深度优先搜索，每次运行结束后，它增加深度并迭代，直到找到目标状态。 IDDFS 与广度优先搜索有同样的时间复杂度，但空间复杂度更低。 IDDFS 第一次访问节点的累积顺序是广度优先的。 例子 對於這張圖，若使用標準的深度優先搜索（DFS），則演算法會在B、…
散列函數
散列函数（）又称-{zh-cn:散列算法、哈希函数; zh-tw:雜湊演算法}-，是一种从任何一种数据中创建小的数字“指纹”的方法。散列函数把消息或数据计算成摘要，使得数据量变小，将数据的格式固定下来。该函数将数据打乱混合，重新创建一个叫做散列值（又叫哈希值）（，，，或）的指纹。散列值通常用一个短的随机字母和数字组成的字符串来代表。好的散列函数在输入域中很少出现散列冲突。如果在散列表和数据处理中，不抑制冲突来区别数据，会使得数据库记录更…
倒排索引
倒排索引（英语：Inverted index），也常被称为反向索引、置入档案或反向档案，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。它是文档检索系统中最常用的数据结构。 有两种不同的反向索引形式： 一条记录的水平反向索引（或者反向档案索引）包含每个引用单词的文档的列表。 一个单词的水平反向索引（或者完全反向索引）又包含每个单词在一个文档中的位置。 后者的形式提供了更多的兼容性（比如短语搜索），…
最邻近搜索
最邻近搜索（Nearest Neighbor Search, NNS）又称为“最近点搜索”（Closest point search），是一个在尺度空间中寻找最近点的优化问题。问题描述如下：在尺度空间M中给定一个点集S和一个目标点q ∈ M，在S中找到距离q最近的点。很多情况下，M为多维的欧几里得空间，距离由欧几里得距离或曼哈顿距离决定。 高德纳在《计算机程序设计艺术》（1973）一书的第三章中称之为邮局问题，即居民寻找离自己家最近的邮…
激活扩散
激活扩散（）是一种搜索关联网络、生物和人工神经网络或语义网络的方法。这一搜索过程是通过给一组源节点（例如语义网络中的概念）贴上权重或“激活”来启动的，然后迭代地将激活传播或“扩散”到与源节点相连的其他节点。大多数情况下，这些“权重”是真实的数值，伴随激活在网络中的传播而逐渐衰减。当权重值是离散的时，这个过程通常被称为标记传递。激活可能来自不同的路径，由不同的标记识别，并在两个备用路径到达同一节点时终止。大脑研究表明，几个不同的大脑区域在…
索引映射
索引映射（Index mapping）也稱為直接定址（direct addressing）或平凡散列函數（trivial hash function）是计算机科学中對陣列的應用，利用陣列查表來找到主键所有全集分別對應的值。 此方式適用在主鍵全集不大的情形，因此可以針對每一個可能的主鍵分配記憶體。 其效能是源至在任何陣列中查表的时间复杂度都是常數。 適用的陣列 有許多實例中的資料有效值限制在小範圍內。此時適合使用平凡散列函數，以數值作為查…
线性散列
线性散列是由Witold Litwin（1980）发明并被Paul Larson推广的一种动态散列（dynamic hash）算法。线性散列表的每次扩张仅增加一个槽（slot、bucket）， 频繁的单槽扩张可以非常有效控制的冲突链的长度，从而哈希表扩展的代价摊还在每一次插入操作中。因此非常适合用于交互式应用程序。 算法细节 散列表初始化时，先分配任意的数目的散列槽，并在运行过程中检测以下的值： N：最初分配的散列槽数目。 L：它是一个…