【计算机】十大经典算法.pdf

### 十大经典算法概述 #### 一、搜索算法 搜索算法是计算机科学中的一个基本概念，用于在数据结构中查找特定元素或者解决方案的过程。它包括两种主要类型：深度优先搜索（DFS）和广度优先搜索（BFS），以及一种结合两者的优点的算法——迭代加深搜索（ID）。 ##### 深度优先搜索（DFS） **算法描述**： - **定义**：深度优先搜索是一种遍历或搜索树或图的算法。它首先深入到树的分支尽可能远，然后再回溯。 - **应用场景**：n皇后问题。 - **具体步骤**： - 从第0列开始搜索。 - 对于每一列，尝试将皇后放置在每一行中未被攻击的位置。 - 如果找到了解决方案，则打印结果并退出。 - 如果到达了最后一列仍未找到解决方案，则回溯到前一列并尝试下一个位置。 - **示例代码**（伪代码）： ```plaintext search(col): if filled all columns: print solution and exit for each row: if board(row, col) is not attacked: place queen at (row, col) search(col + 1) remove queen at (row, col) ``` **复杂度分析**： - **时间复杂度**：假设搜索树有d层（在n皇后问题中d=n），每个节点有c个子节点（同样c=n），那么整个搜索的时间复杂度与c^d成正比，即O(c^d)。 - **空间复杂度**：O(d)，因为只需要一个栈来存储当前路径所经过的节点。 ##### 广度优先搜索（BFS） **算法描述**： - **定义**：广度优先搜索是从根节点开始，然后依次访问每一层的所有节点。 - **应用场景**：骑士覆盖问题。 - **具体步骤**： - 将初始状态加入队列。 - 当队列不为空时，取出队首状态进行处理，并将所有可能的下一步状态加入队列。 - **示例代码**（伪代码）： ```plaintext process(state): for each possible next state from this one: enqueue next state search(): enqueue initial state while !empty(queue): state = get state from queue process(state) ``` **复杂度分析**： - **时间复杂度**：O(V+E)，其中V是顶点数，E是边数。 - **空间复杂度**：广度优先搜索的空间复杂度取决于每层的节点数。如果搜索树有k层，每个节点有c个子节点，则空间复杂度为O(c^k)。 ##### 迭代加深搜索（ID） **算法描述**： - **定义**：迭代加深搜索是一种结合了深度优先搜索和广度优先搜索优点的算法，通过限制深度来逐步扩展搜索的深度。 - **应用场景**：骑士覆盖问题。 - **具体步骤**： - 从限定深度0开始进行深度优先搜索。 - 如果没有找到解决方案，则增加限定深度1，重复上述步骤。 - 继续增加限定深度，直到找到解决方案为止。 - **示例代码**（伪代码）： ```plaintext truncated_dfsearch(next_pos, depth): if board is covered: print solution and exit if depth == 0: return for i from next_pos to n * n: put knight at i truncated_dfsearch(i + 1, depth - 1) remove knight at i dfid_search: for depth = 0 to max_depth: truncated_dfsearch(0, depth) ``` **复杂度分析**： - **时间复杂度**：与深度优先搜索相同，即O(c^d)。 - **空间复杂度**：O(d)，与深度优先搜索相同。 ### 总结 以上介绍了三种经典的搜索算法——深度优先搜索、广度优先搜索以及迭代加深搜索。这些算法在解决搜索问题时各有优势： - **深度优先搜索**适用于搜索空间较小或需要快速探索的场景。 - **广度优先搜索**适用于需要找到最短路径或确保找到最优解的情况。 - **迭代加深搜索**则是在兼顾时间和空间效率之间取得平衡的好方法。 这些算法不仅在理论研究中有重要意义，在实际应用中也极为广泛，如在人工智能、游戏开发、网络路由等领域都有着不可替代的作用。