算法设计与分析:回溯算法

最小重量机器设计问题

问题描述

设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处够来的部件i的重量,cij是相应的价格。
试设计一个算法,给出总价格不超过c的最小重量机器设计。

算法设计:对于给定的机器部件重量和机器部件价格,计算总价值不超过d的最小重量机器设计。

数据输入:第一行由3个正整数n,m,d。接下来的2n行,每行m个数。前n行是c,后n行是w。

结果输出:将计算的最小重量及每个部件的供应商输出。

输入:             输出:
3 3 4             4
1 2 3             1 3 1
3 2 1
2 2 2 
1 2 3
3 2 1
2 2 2

算法描述

由于题目已经给出总价格的上限,因此算法通过使用回溯算法来选择合适的机器使得在总价格不超过d时得到的机器重量最小。

首先初始化当前花费cc = 0,当前重量cw = 0。此外,还要设置一个变量bestw表示选择零件的最小重量,初始化其为无穷大。在循环选择i号机器时,判断从j号供应商购买机器后的价格是否大于总价格,如果不大于则选择,否则不选,继续选择下一供应商进行判断。在得到一个合适的供应商后,继续选择下一机器的供应商,从第一个选到最后一个供应商。当所有机器选择结束后,判断得到的总重量是否比之前的bestw小,如果小就赋给bestw,然后从这一步开始,回溯到上一机器,选择下一合适供应商,继续搜索可行解,直到将整个排列树搜索完毕。这样,最终得到的bestw即为最优解。

考虑到算法的时间复杂度,还可以加上一个剪枝条件,即在每次选择某一机器时,再判断选择后的重量是否已经大于之前的bestw或选择后的花费已经大于d。如果大于就没必要继续搜索了,因为得到的肯定不是最优解。
a.部件有n个,供应商有m个,分别用二位数组c和w存储从供应商j 处购得的部件i的价格和重量,d为总价格的上限。
b.用递归函数backTrack(i)来实现回溯法搜索排列树(参数i表示排列树深度,也表示第i号零件)。
① 若cc>d,则为不可行解,剪去相应子树,返回到i-1层继续执行。
② 若cw>=bestw,则不是最优解,剪去相应子树,返回到i-1层继续执行。
③ 若i>n,则算法搜索到一个叶结点,用bestw对最优解进行记录,返回到i-1层继续执行;
④ 用for循环对部件i从m个不同的供应商购得的情况进行选择(0≤j<m)。
c.主函数调用一次backTrack(0)即可完成整个回溯搜索过程,最终得到的bestw即为所求最小总重量。

关键代码

	int n;//n种部件
    int m;//m个供应商
    int d;//总价格不超过
    int[][] c;
    int[][] w;
    int[] x;//当前解
    int[] bestx;//最优解
    int cw;//当前重量
    int cc;//当前价格
    int bestw;//最优重量	
	public void backTrace(int i) {
        if (i == n) {
            if (cw < bestw) {
                for (int j = 0; j < n; j++) {
                    if (x[j] == -1) {
                        //这个x不是解
                        return;
                    }
                }
                for (int j = 0; j < n; j++) {
                    bestx[j] = x[j];
                }
                bestw = cw;
            }
            return;
        }
        for (int k = 1; k <= m; k++) {
            //此路不通
            if (cc + c[i][k] > d || cw + w[i][k] > bestw) {
                continue;
            }
            cc += c[i][k];
            cw += w[i][k];
            x[i] = k;
            backTrace(i + 1);
            cc -= c[i][k];
            cw -= w[i][k];
            x[i] = -1;
        }
    }

结果分析

输入:

3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

输出

4

1 3 1

输入:

3 3 7
1 2 3
5 4 2
2 1 2
1 2 3
3 2 1
2 3 2

输出:

4

1 3 1

总共n个零件,每种零件都有m种供应商的选择,共计\(m^n\)种可能性,并且更新最优解的算法时间复杂度为\(O(n)\)。

即使有减枝操作,但是算法时间复杂度仍为\(O(n*m^n)\)

为了保存当前解需要使用数组,算法空间复杂度为\(O(n)\)

最佳调度

问题描述

有n个任务由k个可并行工作的机器完成。完成任务i需要的时间为ti。找出完成这n个任务的最佳调度,使得完成全部任务的时间最少

第一行有2个正整数n和k,第二行有n个正整数,表示ti

样例输入

7 3
2 14 4 16 6 5 3

样例输出

17

算法描述

从n个作业中找出有最小完成时间和的作业调度,所以批处理作业调度问题的解空间是一棵组合选择树,可以用回溯算法解决。

设t=[0,1, ... , n-1]是所给的n个作业的完成时间,数组machineTime=[0,1,..,k-1]用于记录k个机器当前的工作时间情况,bestx记录相应的当前最佳作业调度完成时间。记i为递归深度,也就是当前处理的作业序号。

当i<=n-1时,若当前扩展结点位于排列树的第i-1层,此时算法搜索第i号作业可供安排的机器,以深度优先方式递归的对相应的子树进行搜索,对不满足上界约束的选择。当选择结束后,撤销此次选择,向 i-1 层回溯。

当i=n时,深度优先搜索结束,得到一个新的作业调度方案。此时算法适时更新当前最优值;

关键代码

	int n;//n个任务
    int k;//k个机器
    int[] t;//每个任务的耗时
    int[] machineTime; //每个机器的所花费时间
    int bestx;//最少时间

    public void backTrace(int i) {
        if (i == n) {
            int x = -1;
            //x为当前调度策略所需要的时间花费
            for (int j = 0; j < k; j++) {
                x = Math.max(x, machineTime[j]);
            }
            bestx = Math.min(x, bestx);
            return;
        }
        for (int j = 0; j < k; j++) {
            if (machineTime[j] + t[i] >= bestx) {
                continue;
            }
            machineTime[j] += t[i];
            backTrace(i + 1);
            machineTime[j] -= t[i];
        }
    }

结果分析

输入:

7 3
2 14 4 16 6 5 3

输出:

17

输入:

10 7
12 13 13 10 5 1 4 5 6 7

输出:

13

总共n个作业,每个作业都有k个机器可供选择,共计\(k^n\)种可能性,并且需要用\(O(k)\)的时间计算出每次调度安排的所需时间。

即使有减枝操作,但是算法时间复杂度仍为\(O(k*k^n)\)

为了保存每个机器所花费的时间,需要使用数组,算法空间复杂度为\(O(k)\)

上一篇:nmap实验


下一篇:Python查找列表中某个元素返回所有下标