广度优先搜索是完备的吗知乎（广度优先搜索是完备的吗知乎怎么搜）



加权图：图中边会加上权重，带权重的图。
权重：每条边都有关联数字的图，这些数字称为权重。
广度优先搜索：计算非加权图中的最短路径。
狄克斯特拉算法：计算加权图中的最短路径，适用于有向无环图。

狄克斯特拉算法步骤：

1. 找出最便宜的节点，即可在最短时间内前往的节点。
2. 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
3. 重复这个过程，直到对图中的每个节点都这样做了。
4. 计算最终路径。

实现方法：绘制表格，不断更新表格中的数据，从而确定花费最少的路径。
基本逻辑：找到图中最便宜的节点，并确保没有到该节点的更便宜的路径。

逐层对各结点的路径进行计算，并保留最短路径的父节点，最终确定最短路径。

但是狄克斯特拉算法不适用于负权边的计算，因为该算法中节点一旦被认为是最短路径被处理，就意味着没有前往该结点的更短的路径。
在包含负权边的图中寻找最短路径，可以采用贝尔曼-福德算法。

需要三个散列表：节点邻居节点表Graph、到达该节点花销表Cost和节点父节点表Parents

算法流程图：

贪婪算法解决思路：每步都采取最优的做法。就是你每步都选择局部最优解，最终得到的就是全局最优解。
优点：简单易行。

NP完全问题判断：

1. 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
2. 涉及“所有组合”的问题通常是NP完全问题。
3. 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
4. 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
5. 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
6. 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是NP完全问题。

• 教室调度问题：选出最早的课，然后再接着排最临近的没有冲突的课。
• 背包问题：一定空间内装入最大价值的物品。（有时候，你只需找到一个能够大致解决问题的算法，此时贪婪算法正好可派上用场，因为它们实现起来很容易，得到的结果又与正确结果相当接近。）

近似算法（贪婪算法），当获得精确解需要的时间太长时，可使用近似算法。判断近似算法的优劣标准如下：速度有多快；得到的近似解与最优解的接近程度。

• 5个城市有120钟不同的排列方式。
• 涉及6个城市时，需要执行720次操作。
• 涉及7个城市时，需要执行5040次操作。
• 涉及n个城市时，需要执行n!(n的阶乘)次操作。因此运行时间为O(n!)，即阶乘时间。

解决思路：：随便选择出发城市，然后每次选择要去的下一个城市时，都选择还没去的最近的城市。

傅里叶变换作用：分析物体的组成成分。

分布式算法：一种特殊的并行算法。MapReduce是一种流行的分布式算法，你可通过流行的开源工具Apache Hadoop来使用它。
分布式算法非常适合用于在短时间内完成海量工作，其中的MapReduce基于两个简单的理念：映射（map）函数和归并（reduce）函数。

• 映射函数
  映射函数很简单，它接受一个数组，并对其中的每个元素执行同样的处理。
  
  
  
• 归并函数
  归并函数的理念是将很多项归并为一项。映射是将一个数组转换为另一个数组。
  
  MapReduce使用这两个简单概念在多台计算机上执行数据查询。数据集很大，包含数十亿行时，使用MapReduce只需几分钟就可获得查询结果，而传统数据库可能要耗费数小时。
  
  
  

给定一个元素，你需要判断它是否包含在这个集合中。为快速做出这种判断，可使用散列表。

• 布隆过滤器
  布隆过滤器是一种概率型数据结构，它提供的答案有可能不对，但很可能是正确的。布隆过滤器可能出现错报的情况，不可能出现漏报的情况。
  
• HyperLogLog
  HyperLogLog是一种类似于布隆过滤器的算法。
  HyperLogLog近似地计算集合中不同的元素数，与布隆过滤器一样，它不能给出准确的答案，但也八九不离十，而占用的内存空间却少得多。
  
  

安全散列算法（secure hash algorithm，SHA）函数，给定一个字符串，SHA返回其散列值。

SHA是一个散列函数，它生成一个散列值——一个较短的字符串。用于创建散列表的散列函数根据字符串生成数组索引，而SHA根据字符串生成另一个字符串。

你可使用SHA来判断两个文件是否相同，这在比较超大型文件时很有用。假设你有一个4 GB的文件，并要检查朋友是否也有这个大型文件。为此，你不用通过电子邮件将这个大型文件发送给朋友，而可计算它们的SHA散列值，再对结果进行比较。

SHA算法可以用来检查密码。
SHA实际上是一系列算法：SHA-0、SHA-1、SHA-2和SHA-3。SHA-0和SHA-1已被发现存在一些缺陷。如果你要使用SHA算法来计算密码的散列值，请使用SHA-2或SHA-3。当前，最安全的密码散列函数是bcrypt，但没有任何东西是万无一失的。

如何对消息进行加密，以便只有收件人才能看懂呢？

Diffie-Hellman算法解决了如下两个问题：

1. 双方无需知道加密算法。他们不必会面协商要使用的加密算法。
2. 要激活成功教程加密的消息比登天还难。

Diffie-Hellman使用两个密钥：公钥和私钥。，公钥就是公开的，可将其发布到网站上，通过电子邮件发送给朋友，或使用其他任何方式来发布。你不必将它藏着掖着。有人要向你发送消息时，他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道私钥，就只有你才能解密消息！

线性规划用于在给定约束条件下最大限度地改善指定的指标。

所有的图算法都可使用线性规划来实现。线性规划是一个宽泛得多的框架，图问题只是其中的一个子集。线性规划可使用Simplex算法。

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/38773.html