禁忌搜索
禁忌搜索（英语：Tabu Search，TS，又称禁忌搜寻法）是一种现代启发式算法，由美国科罗拉多大学教授弗雷德·格洛弗于1986年左右提出，并于1989年实现规范化。 这种搜寻法是一个用来跳脱局部最优解的搜索方法。其先创立一个初始化的方案；基于此，算法“移动”到一相邻的方案。经过许多连续的移动过程，提高解的质量。
原文地址：
https://zh.wikipedia.org/wiki/%E7%A6%81%E5%BF%8C%E6%90%9C%E7%B4%A2
在知识共享 署名-相同方式共享 3.0协议之条款下提供
本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 IT技术记录小站！
相关推荐
2022-12-25
K-近邻算法
在模式识别领域中，最近邻居法（KNN算法，又译K-近邻算法）是一种用于分类和回归的非参数统计方法。在这两种情况下，输入包含特征空间（Feature Space）中的k个最接近的训练样本。 在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。 在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。最近邻居法采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。 K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。 无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。 邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明...
2023-01-05
爬山算法
爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。 爬山算法一般存在以下问题： 1.局部最大 2.高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。 3.山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。解决方法：随机重启爬山算法 原文地址：https://zh.wikipedia.org/wiki/%E7%88%AC%E5%B1%B1%E7%AE%97%E6%B3%95 在知识共享 署名-相同方式共享 3.0协议之条款下提供
2022-12-31
八皇后问题
八皇后问题是一个以国际象棋为背景的问题：如何能够在8×8的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当n = 1或n ≥ 4时问题有解。 历史八皇后问题最早是由国际象棋棋手马克斯·贝瑟尔（Max Bezzel）于1848年提出。第一个解在1850年由弗朗兹·诺克（Franz Nauck）给出。并且将其推广为更一般的n皇后摆放问题。诺克也是首先将问题推广到更一般的n皇后摆放问题的人之一。 在此之后，陆续有数学家对其进行研究，其中包括高斯和康托，1874年，S.冈德尔提出了一个通过行列式来求解的方法[2]，这个方法后来又被J.W.L.格莱舍加以改进。 1972年，艾兹格·迪杰斯特拉用这个问题为例来说明他所谓结构化编程的能力[3]。他对深度优先搜索回溯算法有着非常详尽的描述2。 八皇后问题在1990年代初期的著名电子游戏《第七访客》和NDS平台的著名电子游戏《雷顿教授与不可思议的小镇》中都有出现。 解题...
2023-01-04
极小化极大算法
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)) ...
2022-12-26
X算法
维基百科，自由的百科全书跳到导航跳到搜索在计算机科学中，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矩阵。如果...
2022-12-28
倒排索引
倒排索引（英语：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...
