算法设计与分析-回溯法

算法设计与分析——批处理作业调度（回溯法）之前讲过⼀个相似的问题流⽔作业调度问题，那⼀道题最开始⽤动态规划，推到最后得到了⼀个Johnson法则，变成了⼀个排序问题，有兴趣的可以看⼀下本篇博客主要参考⾃⼀、问题描述给定n个作业的集合{J1,J2,…,Jn}。

每个作业必须先由机器1处理，然后由机器2处理。

作业Ji需要机器j的处理时间为t ji。

对于⼀个确定的作业调度，设Fji是作业i在机器j上完成处理的时间。

所有作业在机器2上完成处理的时间和称为该作业调度的完成时间和。

批处理作业调度问题要求对于给定的n个作业，制定最佳作业调度⽅案，使其完成时间和达到最⼩。

例：设n=3，考虑以下实例：看到这⾥可能会对这些完成时间和是怎么计算出来的会有疑问，这⾥我拿123和312的⽅案来说明⼀下。

对于调度⽅案（1,2,3）作业1在机器1上完成的时间是2，在机器2上完成的时间是3作业2在机器1上完成的时间是5，在机器2上完成的时间是6作业3在机器1上完成的时间是7，在机器2上完成的时间是10所以，作业调度的完成时间和= 3 + 6 + 10这⾥我们可以思考⼀下作业i在机器2上完成的时间应该怎么去求？作业i在机器1上完成的时间是连续的，所以是直接累加就可以。

但对于机器2就会产⽣两种情况，这两种情况其实就是上图的两种情况，对于（1,2,3）的调度⽅案，在求作业2在机器2上完成的时间时，由于作业2在机器1上还没有完成，这就需要先等待机器1处理完；⽽对于（3,1,2）的调度⽅案，在求作业2在机器2上完成的时间时，作业2在机器1早已完成，⽆需等待，直接在作业1被机器1处理之后就能接着被处理。

综上，我们可以得到如下表达式if(F2[i-1] > F1[i])F2[i] = F2[i-1] + t[2][i]elseF2[i] = F1[i] + t[2][i]⼆、算法设计类Flowshop的数据成员记录解空间的结点信息，M输⼊作业时间，bestf记录当前最⼩完成时间和，数组bestx记录相应的当前最佳作业调度。

算法设计与分析中的贪心算法与回溯法算法设计与分析领域中，贪心算法和回溯法是两种常用的解题方法。

本文将介绍这两种算法，并比较它们在不同场景下的优势和劣势。

一、贪心算法贪心算法是一种在每一步都选择当前最优解的策略，希望通过局部最优解的选择最终达到全局最优解。

贪心算法的实现较为简单，时间复杂度较低，适用于解决一些最优化问题。

贪心算法的基本思想是每次都选择当前状态下的最优解，并将其加入到解集中。

例如，在求解最小生成树的问题中，贪心算法会选择当前具有最小权值的边，并将其添加到最终结果中，直到生成树完成。

然而，贪心算法的局限性在于它只考虑了当前的最优解，无法保证找到全局最优解。

在某些问题中，贪心算法可能会陷入局部最优解而无法跳出。

因此，需要在具体问题中综合考虑问题的性质和约束条件来确定是否适合采用贪心算法。

二、回溯法回溯法是一种通过不断尝试可能的步骤来寻找问题解的方法。

它通常基于递归的思想，在每一步都尝试所有的可能选择，并逐步构建解空间，直到找到解或确定无解。

回溯法的核心思想是深度优先搜索，通过遍历解空间树来寻找解。

在每一步，回溯法都会考虑当前状态下的所有可能选择，并递归地进入下一步。

如果某一步的选择无法达到目标，回溯法会回退到上一步进行其他可能的选择。

回溯法常用于解决一些全排列、子集和组合等问题。

例如，在解决八皇后问题时，回溯法通过逐个放置皇后并进行合法性判断，直到找到所有解或遍历完所有可能的情况为止。

然而，回溯法的缺点在于其时间复杂度较高，其搜索过程包含了大量的重复计算。

因此，在使用回溯法解决问题时，需注意适当剪枝以减少搜索空间，提高算法效率。

三、贪心算法与回溯法的比较贪心算法和回溯法都是常用的算法设计与分析方法，但其适用场景和效果有所差异。

贪心算法在解决问题时能够快速找到局部最优解，并且具有较低的时间复杂度。

它适用于一些满足最优子结构性质的问题，例如最小生成树、单源最短路径等。

然而，贪心算法无法保证一定能找到全局最优解，因此需根据具体问题的特点来判断是否使用。

算法分析与设计实验报告--回溯法实验目的：通过本次实验，掌握回溯法的基本原理和应用，能够设计出回溯法算法解决实际问题。

实验内容：1.回溯法概述回溯法全称“试探回溯法”，又称“逐步退化法”。

它是一种通过不断试图寻找问题的解，直到找到解或者穷尽所有可能的解空间技术。

回溯法的基本思路是从问题的某一个初始状态开始，搜索可行解步骤，一旦发现不满足求解条件的解就回溯到上一步，重新进行搜索，直到找到解或者所有可能的解空间已经搜索完毕。

2.回溯法的基本应用回溯法可用于求解许多 NP 问题，如 0/1 背包问题、八皇后问题、旅行商问题等。

它通常分为两种类型：一种是通过枚举所有可能的解空间来寻找解；另一种则是通过剪枝操作将搜索空间减少到若干种情况，大大减少了搜索时间。

3.回溯法的解题思路（1）问题分析：首先需要对问题进行分析，确定可行解空间和搜索策略；（2）状态表示：将问题的每一种状况表示成一个状态；（3）搜索策略：确定解空间的搜索顺序；（4）搜索过程：通过逐步试探，不断扩大搜索范围，更新当前状态；（5）终止条件：在搜索过程中，如果找到了满足要求的解，或者所有的可行解空间都已搜索完毕，就结束搜索。

4.八皇后问题八皇后问题是指在一个 8x8 的棋盘上放置八个皇后，使得任意两个皇后都不在同一行、同一列或同一对角线上。

通过回溯法可以求解出所有的可能解。

实验过程：回溯法的实现关键在于搜索空间的剪枝，避免搜索无用的解；因此，对于八皇后问题，需要建立一个二维数组来存放棋盘状态，以及一个一维数组来存放每行放置的皇后位置。

从第一行开始搜索，按照列的顺序依次判断当前的空位是否可以放置皇后，如果可以，则在相应的位置标记皇后，并递归到下一行；如果不能，则回溯到上一行，重新搜索。

当搜索到第八行时，获取一组解并返回。

代码实现：```pythondef is_valid(board, row, col):for i in range(row):if board[i] == col or abs(board[i] - col) == abs(i - row):return Falsereturn True实验结果：当 n=4 时，求得的所有可行解如下：```[[1, 3, 0, 2],[2, 0, 3, 1]]```本次实验通过实现回溯法求解八皇后问题，掌握了回溯法的基本原理和应用，并对回溯法的核心思想进行了深入理解。

实验五：中国象棋中马的走法。

（回溯法）1.问题描述：在4×5的棋盘上已知马的起始坐标(x,y)，求马能够返回到起始位置的不重复的所有不同走法的总数。

问题分析：(1)读入马的起始位置，进行合法性判断；(2)从起始位置开始搜索，搜索方法采用深搜，累计总数；(3)输出结果。

#include <stdio.h>#include <stdlib.h>int array[2][8] = {{-1, -1, -2, -2, 2, 2, 1, 1},{-2, 2, 1, -1, 1, -1, 2, -2}};//表示马跳的8个方向int chess[4][5];//表示棋盘，1：表示已经在较早的时候走过，0：则没有int total = 0;//统计走法的个数int sx, sy;//(sx,sy)表示马的起始坐标void find_way(int p1, int p2);//回溯的过程void main(){ int i, j;for(i = 0; i < 4; i++)for(j = 0; j < 5; j++)chess[i][j] = 0;printf("输入马的起始坐标:\n");scanf("%d", &sx);scanf("%d", &sy);printf("sx = %d, sy = %d\n", sx, sy);if ((sx < 0)||(sx >= 4)||(sy < 0)||(sy >= 5))printf("ERROR\n");else{chess[sx][sy] = 1;find_way(sx, sy);//从起始位置开始试探printf("total = %d\n", total);getchar();}}void find_way(int p1, int p2){ int i, pi, pj;for(i = 0; i < 8; i++){//向8个方向试探pi = p1 + array[0][i];pj = p2 + array[1][i];if((sx == pi)&&(sy == pj))total++;//找到一种走法,(sx,sy)表示起点else if( (pi >= 0)&&(pi < 4)&&(pj >= 0)&&(pj < 5)&&(chess[pi][pj] == 0)){//继续试探chess[pi][pj] = 1;find_way(pi, pj);chess[pi][pj] = 0;}}//for}测试报告1.输入马的起始（3.4）2.运行结果。

沈阳理工大学算法实践与创新论文摘要对于计算机科学来说，算法的概念是至关重要的，算法是一系列解决问题的清晰指令，也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出。

为了更加的了解算法，本篇论文中，我们先研究一个算法---回溯法。

回溯法是一种常用的重要的基本设计方法。

它的基本做法是在可能的范围之内搜索，适于解一些组合数相当大的问题。

圆排列描述的是在给定n个大小不等的圆 C1,C2,…,Cn,现要将这n个圆排进一个矩形框中，且要求各圆与矩形框的底边相切。

圆排列问题要求从n个圆的所有排列中找出有最小长度的圆排列。

图着色问题用数学定义就是给定一个无向图G=（V, E），其中V为顶点集合，E为边集合，图着色问题即为将V分为K个颜色组，每个组形成一个独立集，即其中没有相邻的顶点。

其优化版本是希望获得最小的K值。

符号三角形问题要求对于给定的n，计算有多少个不同的符号三角形，使其所含的“+”和“-”的个数相同。

在本篇论文中，我们将运用回溯法来解决着图的着色问题，符号三角形问题，图排列问题，将此三个问题进行深入的探讨。

关键词: 回溯法图的着色问题符号三角形问题图排列问题目录第1章引言 (1)第2章回溯法的背景 (2)第3章图的着色问题 (4)3.1 问题描述 (4)3.2 四色猜想 (4)3.3 算法设计 (5)3.4 源代码 (6)3.5 运行结果图 (10)第4章符号三角形问题 (11)4.1 问题描述 (11)4.2 算法设计 (11)4.3 源代码 (12)4.4 运行结果图 (16)第5章圆的排列问题 (17)5.1 问题描述 (17)5.2 问题分析 (17)5.3 源代码 (18)5.4 运行结果图 (22)结论 (23)参考文献 (24)第1章引言在现实世界中，有相当一类问题试求问题的全部解或求问题的最优解。

最基本的方法是通过枚举法搜索问题的解空间。

但许多问题解空间的大小随问题规模n的增长呈指数规律增长，这就使问题理论上可解而实际不可行。

《算法设计与分析》课程实验报告实验序号：10实验项目名称：实验十一回溯法（二）一、实验题目1.图的着色问题问题描述：给定无向连通图G和m种不同的颜色。

用这些颜色为图G的各顶点着色，每个顶点着一种颜色。

如果有一种着色法使G中每条边的2个顶点着不同颜色，则称这个图是m可着色的。

图的m着色问题是对于给定图G和m种颜色，找出所有不同的着色法。

2.旅行商问题问题描述：给出一个n个顶点的带权无向图，请寻找一条从顶点1出发，遍历其余顶点一次且仅一次、最后回到顶点1的最小成本的回路——即最短Hamilton回路。

3.拔河比赛问题描述：某公司的野餐会上将举行一次拔河比赛。

他们想把参与者们尽可能分为实力相当的两支队伍。

每个人都必须在其中一只队伍里，两队的人数差距不能超过一人，且两队的队员总体重应该尽量接近。

4.批处理作业调度问题描述：给定n个作业的集合J=(J1,J2, .. Jn)。

每个作业J都有两项任务分别在两台机器上完成。

每个作业必须先由机器1处理，再由机器2处理。

作业i需要机器j的处理时间为tji(i=1,2, ..n; j=1,2)。

对于一个确定的作业调度，设Fji是作业i在机器j上完成处理的时间，则所有作业在机器2上完成处理的时间和，称为该作业调度的完成时间和。

批处理作业调度问题要求，对于给定的n个作业，制定最佳作业调度方案，使其完成时间和达到最小。

二、实验目的（1）通过练习，理解回溯法求解问题的解状态空间树与程序表达的对应关系，熟练掌握排列树、子集树的代码实现。

（2）通过练习，体会减少搜索解空间中节点的方法，体会解的状态空间树的组织及上界函数的选取对搜索的影响。

（3）通过练习，深入理解具体问题中提高回溯算法效率的方法。

（4）（选做题）：在掌握回溯法的基本框架后，重点体会具体问题中解的状态空间搜索时的剪枝问题。

三、实验要求（1）每题都必须实现算法、设计测试数据、记录实验结果，并给出时间复杂度分析。

四、实验过程（算法设计思想、源码）1.图的着色问题(1)算法设计思想用邻接矩阵a[i][j]存储无向图，对于每一个顶点有m种颜色可以涂。

《算法设计与分析》实验报告实验三回溯法3.迷宫问题一天Luna在森林里探险的时候不小心走入了一个迷宫，迷宫可以看成是由n * n的格点组成，每个格点只有2种状态，. 和#，前者表示可以通行后者表示不能通行。

同时当Luna处在某个格点时，她只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上，Luna想要从点A走到点B（不能走出迷宫）。

如果起点或者终点有一个不能通行(为#)，则看成无法办到。

[输入]第1行是测试数据的组数k，后面跟着k组输入。

每组测试数据的第1行是一个正整数n (1 <= n <= 100)，表示迷宫的规模是n * n 的。

接下来是一个n * n的矩阵，矩阵中的元素为. 或者#。

再接下来一行是4个整数ha, la, hb, lb，描述A处在第ha行, 第la列，B处在第hb 行, 第lb列。

注意到ha, la, hb, lb全部是从0开始计数的。

1.八皇后问题1.1解题思路八皇后问题的解法，很简单的解法。

通过回溯实现枚举。

对于当前行，尝试是否可在当前列放置皇后，然后进入下一行的尝试，同时尝试完毕以后，要将当前行回复（回溯），来进行下一次尝试。

到达最后一行的时候，即递归结束条件，打印结果即可。

1.2程序运行情况1.3所有的皇后解见附录。

（毕竟92个解...）1.4程序源码（含注释）2. 24点问题2.1 解题思路这题虽然使用dfs很简单，但是有一点思维在里面。

我很惭愧，自己没有想出来怎么如意的独立AC此题。

遇到的最大的问题——如何插入括号？枚举插入、和运算符一同排列都不靠谱。

解决方法是：用同等的办法转化。

每一次从待组合的是数字中，任取两个数，随机用运算符计算完毕后，再放回去。

下一次计算，再次重复这个过程，可以等价为有括号的运算方式了。

遇到第二个问题——如何实现这种“任取两个数”的选择方式。

这里就直接体现出了我个人能力的不足。

居然没想到。

尝试使用STL的set，但是没成功。