Python 数据结构和算法实用指南（四）（2）https://developer.aliyun.com/article/1507641
最短路径算法
最短路径问题要求我们找出图中节点之间最短可能的路径。在制定从点 A 到点 B 的最有效路径时，这对于地图和路径规划具有重要应用。
迪杰斯特拉算法是解决这个问题的一种非常流行的方法。该算法用于在图中找到从源到所有其他节点或顶点的最短距离。在这里，我们解释了如何使用贪婪方法来解决这个问题。
迪杰斯特拉算法适用于加权有向和无向图。该算法产生了从加权图中给定源节点 A 到最短路径的列表的输出。算法的工作原理如下：
- 最初，将所有节点标记为未访问，并将它们从给定源节点的距离设置为无穷大（源节点设置为零）。
- 将源节点设置为当前节点。
- 对于当前节点，查找所有未访问的相邻节点；计算从源节点通过当前节点到该节点的距离。将新计算的距离与当前分配的距离进行比较，如果更小，则将其设置为新值。
- 一旦我们考虑了当前节点的所有未访问的相邻节点，我们将其标记为已访问。
- 接下来，考虑下一个未访问的节点，该节点距离源节点最近。重复步骤 2 到 4。
- 当未访问节点的列表为空时，我们停止，这意味着我们已经考虑了所有未访问的节点。
考虑以下带有六个节点[A，B，C，D，E，F]的加权图的示例，以了解迪杰斯特拉算法的工作原理：
通过手动检查，最初看起来节点 A 和节点 D 之间的最短路径似乎是距离为 9 的直线。然而，最短路径意味着最低总距离，即使这包括几个部分。相比之下，从节点 A 到节点 E，然后到节点 F，最后到节点 D 的旅行将产生总距离为 7，这使得它成为更短的路径。
我们将使用单源最短路径算法。它将确定从原点（在本例中为 A）到图中任何其他节点的最短路径。
在第八章中，图和其他算法，我们讨论了如何用邻接列表表示图。我们使用邻接列表以及每条边上的权重/成本/距离来表示图，如下面的 Python 代码所示。表用于跟踪从图中源到任何其他节点的最短距离。Python 字典将用于实现此表。
这是起始表：
| 节点 | 距离源的最短距离 | 前一个节点 |
| A | 0 | None |
| B | ∞ | None |
| C | ∞ | None |
| D | ∞ | None |
| E | ∞ | None |
| F | ∞ | None |
图和表的邻接列表如下：
graph = dict() graph['A'] = {'B': 5, 'D': 9, 'E': 2} graph['B'] = {'A': 5, 'C': 2} graph['C'] = {'B': 2, 'D': 3} graph['D'] = {'A': 9, 'F': 2, 'C': 3} graph['E'] = {'A': 2, 'F': 3} graph['F'] = {'E': 3, 'D': 2}
嵌套字典保存了距离和相邻节点。
当算法开始时，给定源节点（A）到任何节点的最短距离是未知的。因此，我们最初将所有其他节点的距离设置为无穷大，除了节点 A，因为从节点 A 到节点 A 的距离为 0。
当算法开始时，没有先前的节点被访问。因此，我们将节点 A 的前一个节点列标记为 None。
在算法的第一步中，我们开始检查节点 A 的相邻节点。要找到从节点 A 到节点 B 的最短距离，我们需要找到从起始节点到节点 B 的前一个节点的距离，这恰好是节点 A，并将其添加到从节点 A 到节点 B 的距离。我们对 A 的其他相邻节点（B、E 和 D）也是这样做的。这在下图中显示：
我们将相邻节点 B 作为其从节点 A 的距离最小；从起始节点（A）到前一个节点（None）的距离为 0，从前一个节点到当前节点（B）的距离为 5。这个和与节点 B 的最短距离列中的数据进行比较。由于 5 小于无穷大（∞），我们用两者中较小的 5 替换∞。
每当一个节点的最短距离被较小的值替换时，我们需要为当前节点的所有相邻节点更新前一个节点列。之后，我们将节点 A 标记为已访问：
在第一步结束时，我们的表如下所示：
| 节点 | 源的最短距离 | 前一个节点 |
| A* | 0 | None |
| B | 5 | A |
| C | ∞ | None |
| D | 9 | A |
| E | 2 | A |
| F | ∞ | None |
此时，节点 A 被视为已访问。因此，我们将节点 A 添加到已访问节点的列表中。在表中，我们通过将文本加粗并在其后附加星号来显示节点 A 已被访问。
在第二步中，我们使用我们的表找到最短距离的节点作为指南。节点 E 的值为 2，具有最短距离。这是我们从节点 E 的表中可以推断出来的。要到达节点 E，我们必须访问节点 A 并覆盖距离 2。从节点 A，我们覆盖 0 的距离到达起始节点，即节点 A 本身。
节点 E 的相邻节点是 A 和 F。但是节点 A 已经被访问过，所以我们只考虑节点 F。要找到到节点 F 的最短路径或距离，我们必须找到从起始节点到节点 E 的距离，并将其添加到节点 E 和 F 之间的距离。我们可以通过查看节点 E 的最短距离列来找到从起始节点到节点 E 的距离，其值为 2。从节点 E 到 F 的距离可以从我们在本节早些时候开发的 Python 中的邻接列表中获得。
这个距离是 3。这两个加起来是 5，小于无穷大。记住我们正在检查相邻的节点 F。由于节点 E 没有更多相邻的节点，我们将节点 E 标记为已访问。我们更新的表和图将具有以下值：
| 节点 | 源的最短距离 | 前一个节点 |
| A* | 0 | None |
| B | 5 | A |
| C | ∞ | None |
| D | 9 | A |
| E* | 2 | A |
| F | 5 | E |
访问节点 E 后，我们在表的最短距离列中找到最小值，即节点 B 和 F 的值为 5。让我们选择 B 而不是 F，纯粹基于字母顺序（我们也可以选择 F）。
节点 B 的相邻节点是 A 和 C，但是节点 A 已经被访问。根据我们之前建立的规则，从 A 到 C 的最短距离是 7。我们得到这个数字是因为从起始节点到节点 B 的距离是 5，而从节点 B 到 C 的距离是 2。
由于 7 小于无穷大，我们将最短距离更新为 7，并用节点 B 更新前一个节点列：
现在，B 也被标记为已访问。表和图的新状态如下：
| 节点 | 源的最短距离 | 前一个节点 |
| A* | 0 | None |
| B* | 5 | A |
| C | 7 | B |
| D | 9 | A |
| E* | 2 | A |
| F | 5 | E |
最短距离但尚未访问的节点是节点F。F的相邻节点是节点D和E。但是节点E已经被访问过。因此，我们专注于找到从起始节点到节点D的最短距离。
我们通过将从节点A到F的距离与从节点F到D的距离相加来计算这个距离。这相加得到 7，小于9。因此，我们将9更新为7，并在节点D的上一个节点列中用F替换A：
节点F现在被标记为已访问。这是更新后的表格和到目前为止的图：
| Node | Shortest distance from source | Previous node |
| A* | 0 | None |
| B* | 5 | A |
| C | 7 | B |
| D | 7 | F |
| E* | 2 | A |
| F* | 5 | E |
现在，只剩下两个未访问的节点，C和D，都具有距离成本为7。按字母顺序，我们选择检查C，因为这两个节点都与起始节点A的最短距离相同：
然而，所有与C相邻的节点都已经被访问。因此，我们除了将节点C标记为已访问外，没有其他事情要做。此时表格保持不变：
最后，我们取节点D，发现它的所有相邻节点也都已经被访问。我们只将其标记为已访问。表格保持不变：
| Node | Shortest distance from source | Previous node |
| A* | 0 | None |
| B* | 5 | A |
| C* | 7 | B |
| D* | 7 | F |
| E* | 2 | A |
| F* | 5 | E |
让我们用我们的初始图表来验证这个表格。从图表中，我们知道从A到F的最短距离是5。我们需要通过E到达节点F：
根据表格，从源列到节点F的最短距离是 5。这是正确的。它还告诉我们，要到达节点F，我们需要访问节点E，然后从E到节点A，这实际上是最短路径。
为了实现 Dijkstra 算法以找到最短路径，我们开始编写程序，通过表示能够跟踪图中变化的表格来找到最短距离。对于我们使用的图表，这是表格的字典表示：
table = dict() table = { 'A': [0, None], 'B': [float("inf"), None], 'C': [float("inf"), None], 'D': [float("inf"), None], 'E': [float("inf"), None], 'F': [float("inf"), None], }
表格的初始状态使用float("inf")表示无穷大。字典中的每个键映射到一个列表。在列表的第一个索引处，存储了从源头 A 到达的最短距离。在第二个索引处，存储了上一个节点：
DISTANCE = 0 PREVIOUS_NODE = 1 INFINITY = float('inf')
为了避免使用魔术数字，我们使用前面的常量。最短路径列的索引由DISTANCE引用。上一个节点列的索引由PREVIOUS_NODE引用。
现在一切都准备就绪，算法的主要函数将接受图（由邻接列表表示）、表格和起始节点作为参数：
def find_shortest_path(graph, table, origin): visited_nodes = [] current_node = origin starting_node = origin
我们将访问过的节点列表保存在visited_nodes列表中。current_node和starting_node变量都将指向我们选择的图中的起始节点。origin值是相对于找到最短路径的其他节点的参考点。
整个过程的重要工作是通过使用while循环完成的：
while True: adjacent_nodes = graph[current_node] if set(adjacent_nodes).issubset(set(visited_nodes)): # Nothing here to do. All adjacent nodes have been visited. pass else: unvisited_nodes = set(adjacent_nodes).difference(set(visited_nodes)) for vertex in unvisited_nodes: distance_from_starting_node = get_shortest_distance(table, vertex) if distance_from_starting_node == INFINITY and current_node == starting_node: total_distance = get_distance(graph, vertex, current_node) else: total_distance = get_shortest_distance (table, current_node) + get_distance(graph, current_node, vertex) if total_distance < distance_from_starting_node: set_shortest_distance(table, vertex, total_distance) set_previous_node(table, vertex, current_node) visited_nodes.append(current_node) if len(visited_nodes) == len(table.keys()): break current_node = get_next_node(table,visited_nodes)
让我们分解一下while循环在做什么。在while循环的主体中，我们获取我们想要调查的图中的当前节点，使用adjacent_nodes = graph[current_node]。现在，current_node应该在之前已经设置好。if语句用于查找current_node的所有相邻节点是否都已经被访问。
当while循环第一次执行时，current_node将包含 A，adjacent_nodes将包含节点 B、D 和 E。此外，visited_nodes也将为空。如果所有节点都已经被访问，我们只会继续执行程序中的其他语句。否则，我们将开始一个全新的步骤。
语句set(adjacent_nodes).difference(set(visited_nodes))返回尚未访问的节点。循环遍历这个未访问的节点列表：
distance_from_starting_node = get_shortest_distance(table, vertex)
get_shortest_distance(table, vertex)辅助方法将返回我们表中最短距离列中存储的值，使用vertex引用的未访问节点之一：
if distance_from_starting_node == INFINITY and current_node == starting_node: total_distance = get_distance(graph, vertex, current_node)
当我们检查起始节点的相邻节点时，distance_from_starting_node == INFINITY and current_node == starting_node 将评估为 True，在这种情况下，我们只需要通过引用图找到起始节点和顶点之间的距离：
total_distance = get_distance(graph, vertex, current_node)
get_distance方法是我们用来获取vertex和current_node之间的边的值（距离）的另一个辅助方法。
如果条件失败，那么我们将把total_distance赋值为从起始节点到current_node的距离和current_node到vertex的距离之和。
一旦我们有了总距离，我们需要检查total_distance是否小于我们表中最短距离列中的现有数据。如果是，我们就使用这两个辅助方法来更新该行：
if total_distance < distance_from_starting_node: set_shortest_distance(table, vertex, total_distance) set_previous_node(table, vertex, current_node)
此时，我们将current_node添加到已访问节点列表中：
visited_nodes.append(current_node)
如果所有节点都已经被访问，那么我们必须退出while循环。为了检查所有节点是否都已经被访问，我们将visited_nodes列表的长度与我们表中的键的数量进行比较。如果它们相等，我们就简单地退出while循环。
get_next_node辅助方法用于获取下一个要访问的节点。正是这个方法帮助我们使用我们的表从起始节点中找到最短距离列中的最小值。
整个方法最终返回更新后的表。要打印表，我们使用以下语句：
shortest_distance_table = find_shortest_path(graph, table, 'A') for k in sorted(shortest_distance_table): print("{} - {}".format(k,shortest_distance_table[k]))
这是前面语句的输出：
>>> A - [0, None] B - [5, 'A'] C - [7, 'B'] D - [7, 'F'] E - [2, 'A'] F - [5, 'E']
为了完整起见，让我们找出这些辅助方法在做什么：
def get_shortest_distance(table, vertex): shortest_distance = table[vertex][DISTANCE] return shortest_distance
get_shortest_distance函数返回我们表中索引 0 处存储的值。在该索引处，我们始终存储从起始节点到vertex的最短距离。set_shortest_distance函数只设置该值如下：
def set_shortest_distance(table, vertex, new_distance): table[vertex][DISTANCE] = new_distance
当我们更新节点的最短距离时，我们使用以下方法更新其上一个节点：
def set_previous_node(table, vertex, previous_node): table[vertex][PREVIOUS_NODE] = previous_node
请记住，PREVIOUS_NODE常量等于 1。在表中，我们将previous_node的值存储在table[vertex][PREVIOUS_NODE]处。
为了找到任意两个节点之间的距离，我们使用get_distance函数：
def get_distance(graph, first_vertex, second_vertex): return graph[first_vertex][second_vertex]
最后的辅助方法是get_next_node函数：
def get_next_node(table, visited_nodes): unvisited_nodes = list(set(table.keys()).difference(set(visited_nodes))) assumed_min = table[unvisited_nodes[0]][DISTANCE] min_vertex = unvisited_nodes[0] for node in unvisited_nodes: if table[node][DISTANCE] < assumed_min: assumed_min = table[node][DISTANCE] min_vertex = node return min_vertex
get_next_node函数类似于在列表中找到最小项的函数。
该函数首先通过使用visited_nodes来获取两个列表集合的差异来找到我们表中未访问的节点。unvisited_nodes列表中的第一项被假定为table中最短距离列中的最小值。
如果在for循环运行时找到了更小的值，min_vertex将被更新。然后函数将min_vertex作为未访问的顶点或距离源点最短的节点返回。
Dijkstra 算法的最坏运行时间是O(|E| + |V| log |V|)，其中*|V|是顶点数，|E|*是边数。
复杂度类
复杂度类根据问题的难度级别以及解决它们所需的时间和空间资源进行分组。在本节中，我们讨论了 N、NP、NP-Complete 和 NP-Hard 复杂度类。
P 与 NP
计算机的出现加快了某些任务的执行速度。总的来说，计算机擅长完善计算的艺术和解决可以归结为一组数学计算的问题。
然而，这种说法并非完全正确。有一些类别的问题对计算机来说需要大量时间来做出合理的猜测，更不用说找到正确的解决方案了。
在计算机科学中，计算机可以使用逻辑步骤的逐步过程在多项式时间内解决的问题类别被称为 P 类型，其中 P 代表多项式。这些问题相对容易解决。
然后还有另一类被认为很难解决的问题。术语难问题用于指代在寻找解决方案时问题难度增加的方式。然而，尽管这些问题的难度增长率很高，但可以确定一个提议的解决方案是否在多项式时间内解决问题。这些被称为 NP 类型问题。这里的 NP 代表非确定性多项式时间。
现在百万美元的问题是，P = NP吗？
P* = NP*的证明是克莱数学研究所的百万美元问题之一，为正确解决方案提供了百万美元的奖金。
旅行推销员问题是 NP 类型问题的一个例子。问题陈述如下：在一个国家中给定n个城市，找到它们之间的最短路线，从而使旅行成本有效。
当城市数量较小时，这个问题可以在合理的时间内解决。然而，当城市数量超过两位数时，计算机所需的时间就会非常长。
许多计算机和网络安全系统都基于 RSA 加密算法。该算法的强度基于它使用的整数因子问题，这是一个 NP 类型问题。
找到由许多位数组成的质数的质因数是非常困难的。当两个大质数相乘时，得到一个大的非质数。这个数的因数分解是许多加密算法借用其强度的地方。
所有 P 类型问题都是NP问题的子集。这意味着任何可以在多项式时间内解决的问题也可以在多项式时间内验证：
但是P = NP调查了可以在多项式时间内验证的问题是否也可以在多项式时间内解决。特别是，如果它们相等，这意味着可以在不需要实际尝试所有可能的解决方案的情况下解决通过尝试多个可能解决方案来解决的问题，从而不可避免地产生某种快捷证明。
当最终发现证明时，它肯定会对密码学、博弈论、数学和许多其他领域产生严重影响。
NP-Hard
如果 NP 中的所有其他问题都可以在多项式时间内可归约或映射到它，那么问题就是 NP-Hard。它至少和 NP 中最难的问题一样难。
NP-Complete
NP-Complete问题是最困难的问题。如果一个问题是NP-Hard问题，同时也在NP类中找到，那么它被认为是NP-Complete问题。
在这里，我们展示了各种复杂性群的维恩图：
数据中的知识发现
为了从给定数据中提取有用信息，我们首先收集要用于学习模式的原始数据。接下来，我们应用数据预处理技术来去除数据中的噪音。此外，我们从数据中提取重要特征，这些特征代表了数据，用于开发模型。特征提取是机器学习算法有效工作的最关键步骤。一个好的特征必须对机器学习算法具有信息量和区分度。特征选择技术用于去除不相关、冗余和嘈杂的特征。此外，突出的特征被输入到机器学习算法中，以学习数据中的模式。最后，我们应用评估措施来评判开发模型的性能，并使用可视化技术来可视化结果和数据。以下是步骤：
- 数据收集
- 数据预处理
- 特征提取
- 特征选择
- 机器学习
- 评估和可视化
总结
在本章中，我们详细讨论了算法设计技术，在计算机科学领域非常重要。在没有太多数学严谨的情况下，我们还讨论了一些算法分类的主要类别。
该领域中的其他设计技术，如分治、动态规划和贪婪算法，也被涵盖，以及重要样本算法的实现。最后，我们对复杂度类进行了简要讨论。我们看到，如果 P = NP 的证明被发现，它肯定会在许多领域产生重大影响。
在下一章中，我们将讨论一些真实世界的应用、工具和机器学习应用的基础知识。
第十四章：实现、应用和工具
学习算法而没有任何现实生活的应用仍然是一种纯粹的学术追求。在本章中，我们将探讨正在塑造我们世界的数据结构和算法。
这个时代的一个黄金机会是数据的丰富。电子邮件、电话号码、文本文档和图像包含大量的数据。在这些数据中，有着使数据更加重要的有价值信息。但是要从原始数据中提取这些信息，我们必须使用专门从事这项任务的数据结构、过程和算法。
机器学习使用大量算法来分析和预测某些变量的发生。仅基于纯数字的数据分析仍然使得许多潜在信息埋藏在原始数据中。因此，通过可视化呈现数据，使人们能够理解并获得有价值的见解。
在本章结束时，您应该能够做到以下几点：
- 精确修剪和呈现数据
- 为了预测，需要同时使用监督学习和无监督学习算法。
- 通过可视化呈现数据以获得更多见解
技术要求
为了继续本章，您需要安装以下包。这些包将用于对正在处理的数据进行预处理和可视化呈现。其中一些包还包含对我们的数据进行操作的算法的良好实现。
最好使用pip安装这些模块。因此，首先，我们需要使用以下命令为 Python 3 安装 pip：
sudo apt-get updatesudo apt-get install python3-pip
此外，需要运行以下命令来安装numpy、scikit-learn、matplotlib、pandas和textblob包：
# pip3 install numpy # pip3 install scikit-learn # pip3 install matplotlib # pip3 install pandas # pip3 install textblob
如果您使用的是旧版本的 Python（即 Python 2），则可以使用相同的命令来安装这些包，只需将pip3替换为pip。
您还需要安装nltk和punkt包，这些包提供了内置的文本处理功能。要安装它们，请打开 Python 终端并运行以下命令：
>>import nltk >>nltk.download('punkt')
这些包可能需要先安装其他特定于平台的模块。请注意并安装所有依赖项：
- NumPy：一个具有操作 n 维数组和矩阵功能的库。
- Scikit-learn：用于机器学习的高级模块。它包含许多用于分类、回归和聚类等算法的实现。
- Matplotlib：这是一个绘图库，利用 NumPy 绘制各种图表，包括折线图、直方图、散点图，甚至 3D 图表。
- Pandas：这个库处理数据操作和分析。
数据预处理
首先，要分析数据，我们必须对数据进行预处理，以去除噪音并将其转换为适当的格式，以便进一步分析。来自现实世界的数据集大多充满噪音，这使得直接应用任何算法变得困难。收集到的原始数据存在许多问题，因此我们需要采取方法来清理数据，使其适用于进一步的研究。
处理原始数据
收集到的数据可能与随时间收集的其他记录不一致。重复条目的存在和不完整的记录要求我们以这样的方式处理数据，以揭示隐藏的有用信息。
为了清理数据，我们完全丢弃了不相关和嘈杂的数据。缺失部分或属性的数据可以用合理的估计值替换。此外，当原始数据存在不一致性时，检测和纠正就变得必要了。
让我们探讨如何使用NumPy和pandas进行数据预处理技术。
缺失数据
如果数据存在缺失值，机器学习算法的性能会下降。仅仅因为数据集存在缺失字段或属性并不意味着它没有用处。可以使用几种方法来填补缺失值。其中一些方法如下：
- 使用全局常数填补缺失值。
- 使用数据集中的均值或中位数值。
- 手动提供数据。
- 使用属性的均值或中位数来填补缺失值。选择基于数据将要使用的上下文和敏感性。
例如，以下数据：
import numpy as np data = pandas.DataFrame([ [4., 45., 984.], [np.NAN, np.NAN, 5.], [94., 23., 55.], ])
可以看到，数据元素data[1][0]和data[1][1]的值为np.NAN，表示它们没有值。如果不希望在给定数据集中存在np.NAN值，可以将其设置为一个常数。
让我们将值为np.NAN的数据元素设置为0.1：
print(data.fillna(0.1))
数据的新状态如下：
0 1 2 0 4.0 45.0 984.0 1 0.1 0.1 5.0 2 94.0 23.0 55.0
要应用均值，我们需要做如下操作：
print(data.fillna(data.mean()))
为每列计算均值，并将其插入到具有np.NAN值的数据区域中：
0 1 2 0 4.0 45.0 984.0 1 49.0 34.0 5.0 2 94.0 23.0 55.0
对于第一列，列0，均值通过(4 + 94)/2得到。然后将结果49.0存储在data[1][0]中。对列1和2也进行类似的操作。
特征缩放
数据框中的列称为其特征。行称为记录或观察。如果一个属性的值比其他属性的值具有更高的范围，机器学习算法的性能会下降。因此，通常需要将属性值缩放或归一化到一个公共范围内。
考虑一个例子，以下数据矩阵。这些数据将在后续部分中被引用，请注意：
data1= ([[ 58., 1., 43.], [ 10., 200., 65.], [ 20., 75., 7.]]
特征一的数据为58、10和20，其值位于10和58之间。对于特征二，数据位于1和200之间。如果将这些数据提供给任何机器学习算法，将产生不一致的结果。理想情况下，我们需要将数据缩放到一定范围内以获得一致的结果。
再次仔细检查发现，每个特征（或列）的均值都在不同的范围内。因此，我们要做的是使特征围绕相似的均值对齐。
特征缩放的一个好处是它提升了机器学习的学习部分。scikit模块有大量的缩放算法，我们将应用到我们的数据中。
Python 数据结构和算法实用指南（四）（4）https://developer.aliyun.com/article/1507679
