马丙鹏_计算机算法设计与分析_第六章__11

马丙鹏_计算机算法设计与分析_第六章_11 本资源主要讲解了计算机算法设计与分析的第六章回溯法，包括一般方法、8-皇后问题、子集和数问题、图的着色问题、0/1背包问题等内容。 一、一般方法 回溯法是一种基本的算法设计方法，用于求解问题的一组特定性质的解或满足某些约束条件的最优解。回溯法是比贪心法和动态规划法更一般的方法。问题的解可以用一个n元组(x1, …, xn)来表示，其中的xi取自于某个有穷集Si。问题的求解目标是求取一个使某一规范函数P(x1, …, xn)取极值或满足该规范函数条件的向量(也可能是满足P的所有向量)。 可以用硬性处理法或回溯法来求取满足规范函数的元组。硬性处理法是构造出所有可能的n-元组并逐一测试它们是否满足P，从而找出该问题的所有最优解。但是，实际中很少使用，因为候选解的数量通常都非常大。回溯法则是避免盲目求解，对可能的元组进行系统化搜索。在求解的过程中，逐步构造元组分量，并在此过程中，通过不断修正的规范函数(有时称为限界函数)去测试正在构造中的n元组的部分向量(x1, …, xi)，看其能否可能导致最优解。如果判定(x1, …, xi)不可能导致最优解，则将可能要测试的mi+1…mn个向量一概略去，相对于硬性处理可大大减少计算量。 二、8-皇后问题 8-皇后问题是指在一个8*8棋盘上放置8个皇后，且使得每两个之间都不能互相“攻击”，也就是使得每两个都不能在同一行、同一列及同一条斜角线上。可以用8元组(x1, x2, …, x8)来表示，其中xi是放置第i行皇后所在的列号。使用这种表示的显式约束条件是Si={1, 2, 3, 4, 5, 6, 7, 8}，1≤i≤8。隐式约束条件是用来描述xi之间的关系，即没有两个xi可以相同且没有两个皇后可以在同一条斜角线上。 三、子集和数问题 子集和数问题是指已知n+1个正数(w1, w2, …, wn)和M，均为正数，要求找出wi的和数等于M的所有子集。可以用k-元组或n-元组来表示解向量。例如，若n=4，(w1, w2, w3, w4)=(11, 13, 24, 7)，M=31，则满足要求的子集：(11, 13, 7) 和 (24, 7)。 四、图的着色问题 图的着色问题是指将图的每个顶点分配一个颜色，使得相邻的顶点的颜色不同。可以用回溯法来解决图的着色问题。 五、0/1背包问题 0/1背包问题是指在满足一定的约束条件下，选择某些物品，使得总重量或总价值达到最大。可以用回溯法来解决0/1背包问题。 本资源主要讲解了计算机算法设计与分析的第六章回溯法，包括一般方法、8-皇后问题、子集和数问题、图的着色问题、0/1背包问题等内容。回溯法是一种基本的算法设计方法，用于求解问题的一组特定性质的解或满足某些约束条件的最优解。