张拓的博客

禁忌搜索（英语：Tabu Search，TS，又称禁忌搜寻法）是一种现代启发式算法，由美国科罗拉多大学教授弗雷德·格洛弗于1986年左右提出，并于1989年实现规范化。 这种搜寻法是一个用来跳脱局部最优解的搜索方法。其先创立一个初始化的方案；基于此，算法“移动”到一相邻的方案。经过许多连续的移动过程，提高解的质量。 原文地址：https://zh.wikipedia.org/wiki/%E7%A6%81%E5%BF%8C%E6%90%9C%E7%B4%A2 在知识共享 署名-相同方式共享 3.0协议之条款下提供

爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 爬山算法一般存在以下问题： 1.局部最大 2.高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 3.山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。解决方法：随机重启爬山算法 原文地址：https://zh.wikipedia.org/wiki/%E7%88%AC%E5%B1%B1%E7%AE%97%E6%B3%95 在知识共享 署名-相同方式共享 3.0协议之条款下提供

激活扩散（英语：Spreading activation）是一种搜索关联网络、生物和人工神经网络或语义网络的方法。这一搜索过程是通过给一组源节点（例如语义网络中的概念）贴上权重或“激活”来启动的，然后迭代地将激活传播或“扩散”到与源节点相连的其他节点。大多数情况下，这些“权重”是真实的数值，伴随激活在网络中的传播而逐渐衰减。当权重值是离散的时，这个过程通常被称为标记传递。激活可能来自不同的路径，由不同的标记识别，并在两个备用路径到达同一节点时终止。大脑研究表明，几个不同的大脑区域在语义处理中都起着重要作用。 在认知心理学中，激活扩散作为模型的语义网络中模拟扇出效应。 传播激活也可以应用于信息检索， 通过代表文件和这些文件所含术语的节点网络来实现。 认知心理学在认知心理学中，传播激活是关于大脑如何通过关联思维网络进行迭代以检索特定信息的理论。扩散激活理论将我们记忆中的概念阵列呈现为认知单元，每个单元由一个节点及其相关元素或特征组成，都由它们之间的边缘连接起来。 传播激活网络可以示意性地表示为在网络图中两个节点之间的直线最短，这意味着这些想法的关系相对更为密切，通常会更快地与元概念联系起 ...

深度优先搜索算法（英语：Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。这个算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。这种算法不会根据图的结构等信息调整执行策略。 深度优先搜索是图论中的经典算法，利用深度优先搜索算法可以产生目标图的拓扑排序表，利用拓扑排序表可以方便的解决很多相关的图论问题，如无权最长路径问题等等。 因发明“深度优先搜索算法”，约翰·霍普克洛夫特与罗伯特·塔扬在1986年共同获得计算机领域的最高奖：图灵奖。 演算方法 1.首先将根节点放入stack中。 2.从stack中取出第一个节点，并检验它是否为目标。 如果找到目标，则结束搜寻并回传结果。 否则将它某一个尚未检验过的直接子节点加入stack中。 3.重复步骤2。 4.如果不存在未检测过的直接子节点。 将上一级节点加入stack中。 重复步骤2。 5.重复步骤4 ...

在量子计算中，Grover算法，也称为量子搜索算法，是指用于非结构化搜索的量子算法，该算法高概率地找到产生特定输出值的黑盒函数的唯一输入，仅使用仅{\displaystyle O({\sqrt {N}})})函数的评估，其中{\displaystyle n}是函数域的大小。它是由Lov Grover在1996年设计的。 经典计算中的类似问题不能在少于{\displaystyle O(N)}评估(因为平均而言，必须检查一半的域才能获得50%的机会找到正确的输入)。Charles H. Bennett，Ethan Bernstein，Gilles Brassard和Umesh Vazirani证明，该问题的任何量子解决方案都需要评估函数{\displaystyle \Omega ({\sqrt {N}})}次，所以格罗弗的算法是渐近最优的。 由于NP完全问题的经典算法需要指数级的许多步骤，并且Grover算法最多提供非结构化搜索的经典解决方案的二次加速，这表明Grover算法本身不会为NP完全问题提供多项式时间解(因为指数函数的平方根是指数函数，而不是多项式函数)。 与其他量子算法不同，其 ...

Minimax算法（亦称 MinMax or MM）又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法。 概述Minimax算法常用于棋类等由两方较量的游戏和程序。该算法是一个零总和算法，即一方要在可选的选项中选择将其优势最大化的选择，另一方则选择令对手优势最小化的方法。而开始的时候总和为0。很多棋类游戏可以采取此算法，例如井字棋（tic-tac-toe）。 伪代码12345678910111213function minimax(node, depth, maximizingPlayer) is if depth = 0 or node is a terminal node then return the heuristic value of node if maximizingPlayer then value := −∞ for each child of node do value := max(value, minimax(child, depth − 1, FALSE)) ...

暴力搜索或穷举搜索，在计算机科学中也称生成与测试，是一种非常低效的解决问题的技术，方法包括了系统地枚举解决方案的所有可能候选项，以及检查每个候选项是否符合问题描述。 找出自然数n的约数的暴力搜索算法将枚举出从1到n的所有整数，并检查它们中的每一个是否除n后没有余数。针对八皇后问题的暴力搜索算法会检查所有在8X8棋盘上八个“皇后”可能的摆放方法，并且，对每一种摆放方法，检查其每一个“皇后”是否能攻击到其它人。 虽然暴力搜索很容易实现，并且如果解决方案存在，它就一定能够找到。但是它的代价是和候选方案的数量成正比，由于这一点，在很多实际问题中，消耗的代价会随着问题规模的增加而快速地增长。因此，当问题规模有限，或当存在可用于将候选解决方案的集合减少到可管理大小的针对特定问题的启发式算法时，通常使用暴力搜索。另外，当实现方法的简单度比速度更重要的时候，也会用到这种方法。 例如，在关键的应用中，或当用计算机证明数学定理时，算法中的任何错误将会导致严重的后果。暴力搜索也可在其他基准化算法和启发式算法里用作基准方法。事实上，暴力搜索可以被看作最简单的启发式算法。暴力搜索与回溯概念是不相同的，在回溯算法 ...

在计算机科学中，搜索树是一种树状数据结构，它的作用是能更方便地从一个集合中找到所要查找的键。搜索树规定其每个节点的键必须大于其左子树中的任何一个键且小于其右子树中的任何一个键。二叉查找树、三叉搜索树、B树等都属于搜索树。 原文地址：https://zh.wikipedia.org/wiki/%E6%90%9C%E7%B4%A2%E6%A0%91 在知识共享 署名-相同方式共享 3.0协议之条款下提供

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

插值搜索法（Interpolation search）是利用插值公式来计算猜测搜索键值的位置。搜索方式与二分搜索相同。 插值公式： 插值 = (设算数 -­ 最小数) / (最大数 -­ 最小数)： 搜索键值 = left + parseInt( ( key - data[left] ) / ( data[right] - data[left] ) )*( right - left ) ) 算法插值搜索之算法与二分搜索算法几乎完全相同，差别在： 二分搜索法：猜测键值在中间位置(middle) 插值搜索法：用插值公式计算键值位置 时间复杂度二分搜索在一般的情况下时间复杂度是对数时间，进行{\displaystyle O(\log n)}次比较操作（{\displaystyle n}在此处是数组的元素数量，{\displaystyle O}是大O记号，{\displaystyle \log } 是对数）。 插值搜索的最坏时间复杂度是{\displaystyle O(n)}，平均进行{\displaystyle O(\log(\log n))}次比较操作。因为用插值公式计算搜索键值，能 ...