A-level 计算机科学/OCR/单元 2.3 算法
线性搜索简单地查看要搜索的每个值列表中的每个项目，直到找到正确的值。对于少量数据来说，这足够有效，但是一旦数据量增加，它就会变得效率低下得多。在大 O 符号中，它可以定义为 O(n)，因为搜索所花费的时间与要搜索的数据项数量成正比增加。
二分搜索要求在搜索数据之前对数据进行排序。它从将数据列表分成两半开始，并确定哪一半包含所需的值。不包含所需数据的另一半被忽略，并且该过程重复，直到找到该值。
冒泡排序是最简单的排序类型。它单独检查每个元素，并确定它的邻居是否比它大或小。如果较小，它将保留在当前位置，并且算法移动到下一个元素。如果它大于它的邻居，算法交换这两个元素。然后它遍历整个排序项，直到不再进行任何移位。此时，该项可以被认为已排序。
它通过创建两个单独的列表（一个排序列表和一个未排序列表）来工作。最初，一个项目从未排序列表中拉入排序列表。从这里，另一个项目被拉入，如果该项目大于排序列表中的当前项目，则将其放置在前面，否则将其放置在排序项目的后面。下一个项目被拉入并进行比较，如果它是最大的值，它将放在最前面，最小的值放在最后面，如果它介于两者之间，则将其放在中间。该过程重复，直到整个列表排序。
快速排序算法使用列表中称为枢纽的值。任何大于枢纽的值都放在右边，任何小于枢纽的值都放在左边。这会在枢纽两边创建两个子列表。该过程对两个列表重复，直到所有子列表都变成枢纽。此时，该列表可以被认为已排序。
Dijkstra 算法作用于一个图，并找到从一个节点到另一个节点的最短路径。一个图是一个节点集合，由弧连接。弧可以与它们相关联的值，被称为弧的成本。节点和弧可以表示许多不同的东西，因为它们通常是现实的抽象。例如，节点可以代表网络上的路由器，而弧可以是它们之间的物理连接，它们的成本是信号沿一条路线传播所花费的时间。或者，节点可能代表城镇，而弧可能代表它们之间的道路，它们的成本是沿着道路行驶所需的汽油量。
算法从用户设置的起始节点开始，并尝试计算遍历图以到达所有节点的累积最小成本，试图逐步改进计算的成本。
- 每个节点都赋予两个值。
- 一个临时成本（整数或浮点数），表示遍历弧以到达该节点的最小已知累积成本。最初，这对于除起始节点之外的所有节点都设置为无穷大，起始节点的临时成本设置为零，因为这是遍历到它的最小累积成本。
- 一个已访问标志（布尔值），表示当前节点是否已被访问。最初，这对于除起始节点之外的所有节点都设置为 false，起始节点设置为 true。
- 计算与当前节点相连的每个未访问节点的累积临时成本。
- 每条弧都有一个成本，因此每个节点的临时成本都设置为该值
- 对于 Dijkstra 算法的后续迭代，只有在计算的成本小于节点的当前临时成本时才更新临时成本。
- 遍历具有最小临时成本的节点。
- 它现在是当前节点。
- 它被标记为已访问。
- 重复步骤 2 和 3，直到与当前节点相连的每个节点都被访问。
- 此时，每个节点的累积临时成本可以被认为是最小可能的成本。
- 完成后，可以追溯路径以找到到达所需节点的最短路径。
这与 Dijkstra 算法基本相同，只是它使用启发式方法来提高搜索效率。一个启发式实际上是对从给定节点到目标节点的路径长度的估计。例如，在寻找城镇之间的路径时，启发式方法可能是城镇之间的直线距离。像这样始终是低估的启发式方法被称为可容许启发式方法，并且具有在与 A* 算法一起使用时始终会导致找到最佳路径的特性。然而，不可容许的启发式方法仍然可以使用，因为它们会严重减少在找到良好的路径之前需要查看的路径数量。在许多情况下，遵循 Dijkstra 算法将涉及查看许多不太可能是正确路径的路径，例如明显远离目标的路径。启发式方法为我们提供了一种使用这种知识来加快我们用来查找路径的算法的方法。
A* 与 Dijkstra 的不同之处在于它为每个节点存储三个值而不是两个：临时路径成本、最终路径成本和启发式成本。当选择一个节点进行扩展时，对于每个没有最终路径成本的节点，计算一个总值，该值是临时路径成本和启发式成本的总和。具有最低总值的节点将被扩展。