<svg xmlns="http://www.w3.org/2000/svg" style="display: none;"> <path stroke-linecap="round" d="M5,0 0,2.5 5,5z" id="raphael-marker-block" style="-webkit-tap-highlight-color: rgba(0, 0, 0, 0);"></path> </svg> <p></p> 讯享网
加权图：图中边会加上权重，带权重的图。
权重：每条边都有关联数字的图，这些数字称为权重。
广度优先搜索：计算非加权图中的最短路径。
狄克斯特拉算法：计算加权图中的最短路径，适用于有向无环图。
讯享网
狄克斯特拉算法步骤：
- 找出最便宜的节点，即可在最短时间内前往的节点。
- 对于该节点的邻居，检查是否有前往它们的更短路径，如果有，就更新其开销。
- 重复这个过程，直到对图中的每个节点都这样做了。
- 计算最终路径。
实现方法：绘制表格，不断更新表格中的数据，从而确定花费最少的路径。
基本逻辑：找到图中最便宜的节点，并确保没有到该节点的更便宜的路径。
逐层对各结点的路径进行计算，并保留最短路径的父节点，最终确定最短路径。
但是狄克斯特拉算法不适用于负权边的计算，因为该算法中节点一旦被认为是最短路径被处理，就意味着没有前往该结点的更短的路径。
在包含负权边的图中寻找最短路径，可以采用贝尔曼-福德算法。
需要三个散列表：节点邻居节点表Graph、到达该节点花销表Cost和节点父节点表Parents
讯享网
算法流程图：
讯享网
贪婪算法解决思路：每步都采取最优的做法。就是你每步都选择局部最优解，最终得到的就是全局最优解。
优点：简单易行。
NP完全问题判断：
- 元素较少时算法的运行速度非常快，但随着元素数量的增加，速度会变得非常慢。
- 涉及“所有组合”的问题通常是NP完全问题。
- 不能将问题分成小问题，必须考虑各种可能的情况。这可能是NP完全问题。
- 如果问题涉及序列（如旅行商问题中的城市序列）且难以解决，它可能就是NP完全问题。
- 如果问题涉及集合（如广播台集合）且难以解决，它可能就是NP完全问题。
- 如果问题可转换为集合覆盖问题或旅行商问题，那它肯定是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算法解决了如下两个问题：
- 双方无需知道加密算法。他们不必会面协商要使用的加密算法。
- 要激活成功教程加密的消息比登天还难。
Diffie-Hellman使用两个密钥：公钥和私钥。，公钥就是公开的，可将其发布到网站上，通过电子邮件发送给朋友，或使用其他任何方式来发布。你不必将它藏着掖着。有人要向你发送消息时，他使用公钥对其进行加密。加密后的消息只有使用私钥才能解密。只要只有你知道私钥，就只有你才能解密消息！
线性规划用于在给定约束条件下最大限度地改善指定的指标。
所有的图算法都可使用线性规划来实现。线性规划是一个宽泛得多的框架，图问题只是其中的一个子集。线性规划可使用Simplex算法。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/202605.html