叶倩琳 201706061330 实验六1

在本实验中，主题是探讨如何使用回溯法和分支限界法来解决经典的问题——“n皇后问题”。n皇后问题是指在n×n的棋盘上放置n个皇后，使得任意两个皇后不能在同一行、同一列或同一条对角线上。实验的主要目标是熟悉这两种算法的应用场景和实现方法，并通过比较它们的效率来分析其优劣。 1. **回溯法**： 回溯法是一种试探性的解决问题方法，它尝试逐步构建解决方案，如果在某一步发现当前选择无法导致有效解，则退回一步，尝试其他可能的选择。在n皇后问题中，回溯法通常采用深度优先搜索策略。代码实现中，`Backtrack()`函数递归地尝试在每一行放置皇后，`Place()`函数用于检查当前位置是否合法。当达到最后一行且所有皇后都已放置时，解的个数增加。如果在某一行无法找到合法位置，就回溯到上一行重新尝试。 2. **分支限界法**： 分支限界法是一种全局优化算法，通过剪枝操作避免无效的搜索空间，从而提高效率。在n皇后问题中，可以使用广度优先搜索（BFS）策略。代码中，定义了一个`Node`类来存储每个状态（部分解），包括已放置的皇后个数、皇后数量以及皇后的位置。`check()`函数用于检查新皇后是否与已放置的皇后冲突。`QueenArrange()`函数创建一个初始节点，并使用队列进行BFS搜索。每一步中，只有通过剪枝检验的节点才会被加入队列，从而减少了无效的搜索。 3. **效率分析**： 回溯法在搜索过程中会尝试所有可能的路径，直到找到解决方案，因此在解决n皇后问题时，随着n的增大，搜索空间呈指数级增长，效率较低。而分支限界法通过剪枝机制，能够在搜索过程中剔除无效的分支，从而减少搜索空间，通常比回溯法更高效。 4. **其他问题**： 实验内容还涉及了单源最短路径问题，这里可以比较贪心算法与分支限界法在寻找最短路径上的表现。此外，还有二分搜索问题以及对快速排序的随机化改造，这些都涉及到不同的算法优化和性能比较。 在实际应用中，根据问题特点和数据规模，选择合适的算法至关重要。回溯法适用于约束条件较多、解空间较小的问题，而分支限界法则适合于需要全局最优解且解空间较大的问题。理解这两种算法的工作原理和实现方式，对于提升问题解决能力具有重要意义。