爬山算法
爬山算法是一种局部择优的方法，采用启发式方法，是对深度优先搜索的一种改进，它利用反馈信息帮助生成解的决策。
爬山算法一般存在以下问题：
- 1.局部最大
- 2.高地：也称为平顶，搜索一旦到达高地，就无法确定搜索最佳方向，会产生随机走动，使得搜索效率降低。
- 3.山脊：搜索可能会在山脊的两面来回震荡，前进步伐很小。
解决方法：随机重启爬山算法
原文地址：
https://zh.wikipedia.org/wiki/%E7%88%AC%E5%B1%B1%E7%AE%97%E6%B3%95
在知识共享 署名-相同方式共享 3.0协议之条款下提供
本站所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来源 IT技术记录小站！
相关推荐
2023-01-05
线性散列
线性散列 (LH) 是一种动态数据结构，它实现哈希表并一次增加或收缩一个存储桶。它是由Witold Litwin于1980年发明的。巴埃萨-耶茨和索萨-波尔曼对此进行了分析。 它是许多称为动态散列的方案中的第一个，例如拉尔森的线性散列与部分扩展，线性散列与优先级分割，线性散列与部分扩展和优先级分割，或递归线性散列。 动态散列数据结构的文件结构会适应文件大小的变化，因此避免了昂贵的定期文件重组。线性哈希文件通过拆分进行扩展 将一个预定的桶一分为二，通过将两个预定的桶合并为一个来收缩。重建的触发因素取决于方案的风格;它可能是存储桶或负载因子(记录数除以存储桶数)的溢出，超出了预定范围。 在线性哈希中有两种类型的桶，一种是要拆分的，另一种是要拆分的 已经分裂了。虽然可扩展散列只拆分溢出的存储桶，但螺旋散列(又名螺旋存储)在桶上不均匀地分布记录，例如 插入、删除或检索成本高的存储桶最早排队 进行拆分。 线性哈希也已制成可扩展的分布式数据结构 LH。在 LH 中，每个存储桶驻留在不同的服务器上。 LH 本身已扩展，可在存在 失败的存储桶。LH 和 LH 中基于键的操作(插入、删除、更新、读...
2022-12-25
K-近邻算法
在模式识别领域中，最近邻居法（KNN算法，又译K-近邻算法）是一种用于分类和回归的非参数统计方法。在这两种情况下，输入包含特征空间（Feature Space）中的k个最接近的训练样本。 在k-NN分类中，输出是一个分类族群。一个对象的分类是由其邻居的“多数表决”确定的，k个最近邻居（k为正整数，通常较小）中最常见的分类决定了赋予该对象的类别。若k = 1，则该对象的类别直接由最近的一个节点赋予。 在k-NN回归中，输出是该对象的属性值。该值是其k个最近邻居的值的平均值。最近邻居法采用向量空间模型来分类，概念为相同类别的案例，彼此的相似度高，而可以借由计算与已知类别案例之相似度，来评估未知类别案例可能的分类。 K-NN是一种基于实例的学习，或者是局部近似和将所有计算推迟到分类之后的惰性学习。k-近邻算法是所有的机器学习算法中最简单的之一。 无论是分类还是回归，衡量邻居的权重都非常有用，使较近邻居的权重比较远邻居的权重大。例如，一种常见的加权方案是给每个邻居权重赋值为1/ d，其中d是到邻居的距离。 邻居都取自一组已经正确分类（在回归的情况下，指属性值正确）的对象。虽然没要求明...
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矩阵。如果...
2023-01-04
插值搜索
插值搜索法（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))}次比较操作。因为用插值公式计算搜索键...
2022-12-29
元启发算法
元启发算法（英文：metaheuristic）, 又称 万能启发式算法、万用启发式算法。在计算机科学和数学优化中，元启发是一种高级的程序或启发式算法，专门用于搜索、生成或选取一个启发式结果（局部搜索算法），该结果可以为一个最优化问题提供足够好的求解，尤其适用于信息不完备或者计算能力受限时的最优化问题。 特色元启发算法(metaheuristic)，meta 代表其比一般启发式算法在搜寻能力上更为高阶。而 heuristic 则代表其算法能够在一个合理的计算成本内找到一个接近真实最佳解的解，但启发式算法并不能够保证其解的可行性与最佳性。 式通常是使用大量的试误以在庞大的解空间中搜寻最佳解。 元启发算法皆在全域搜索与区域搜索中取得权衡，若算法着重区域搜索能力则容易落入区域最佳解陷阱，若着重全域搜索则可能无法收敛解。 算法 模拟退火法 (Simulated annealing algorithm, SA) 社会认知算法 (Social cognitive optimization, SCO) 简化群体算法 (Simplified swarm optimizatiom, SSO) 调和搜...
2023-01-06
迭代深化深度优先搜索
迭代深化深度优先搜索 （iterative deepening depth-first search (IDS or IDDFS))）是对状态空间的搜索策略。它重复地运行一个有深度限制的深度优先搜索，每次运行结束后，它增加深度并迭代，直到找到目标状态。 IDDFS 与广度优先搜索有同样的时间复杂度，而空间复杂度远优。 IDDFS 第一次访问节点的累积顺序是广度优先的。 例子 走这张图 深度0 A，没了 深度1 ABCE，没了 深度2 A, B, D, F, 这时该往回走 C, G, E,完了， F（F撞了） 深度3 A, B, D, F, E, 这时该往回走 C, G,完了， E, F, B（这三个撞了） 算法以下虚拟码展示了由递归地使用限制深度的 DFS (深度优先搜索) 算法来实现的 IDDFS 算法 (叫作 DLS). 123456789101112131415procedure IDDFS(root) for depth from 0 to ∞ found ← DLS(root, depth) if found ≠ null ...
