回溯法求解：工作分配问题-白红宇的个人博客

回溯法求解：工作分配问题

发布日期：2021-05-08 03:04:41 浏览次数：22 分类：精选文章

本文共 4793 字，大约阅读时间需要 15 分钟。

一、问题描述

设有n件工作分配给n个人。将工作i分配给j个人所需的费用为c_ij。试设计一个算法，为每个人都分配1件不同的工作，并使得总费用最小。

输入格式

第一行有1个正整数n（1≤n≤20）。接下来的n行，每行n个数，表示费用。

输出样例

例如，输入样例：

输出：

二、算法解析

求解该问题的整体思想就是利用回溯法的思想：将所有可能出现的解在逻辑上构造成“树”状，然后利用一些条件为这棵树“剪枝”（排除掉一些解情况），以达到更快求解的效果。

准备工作

使用一个二维数组money记录相应的费用，横坐标表示第几种工作，纵坐标表示第几个工人。

使用一个一维数组work表示已经分配工作的工人（0表示未分配，1表示已分配）。

使用全局变量minPay记录最小的总费用，局部变量nowPay表示计算过程中的局部累计费用。

使用变量t表示当前已求解问题的深度（即已经分派到了哪个工作）。

具体情形

情况①：nowPay大于minPay。表示当前累计的费用已经大于已知的最小值，没有继续下去的意义。

情况②：t < n。表示当前分配进展的深度还未到达“叶子结点”（即所有的工作还未分配完），继续进行相应的分配工作。

情况③：t == n。表示当前分配进展的深度达到了“叶子结点”（即所有的工作已经分配完了），此时比较nowPay和minPay的值，minPay取其中的最小值。

三、代码实现

import java.util.Scanner;
public class test {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[][] money = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                money[i][j] = s.nextInt();
            }
        }
        s.close();
        int[] work = new int[n + 1];
        int minPay = 0;
        for (int i = 1; i <= n; i++) {
            minPay += money[i][i];
        }
        int[] array = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minvalue = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++) {
                if (money[i][j] < minvalue) {
                    minvalue = money[i][j];
                }
            }
            array[i] = minvalue;
        }
        for (int i = n - 1; i >= 1; i--) {
            array[i] += array[i + 1];
        }
        searchMinPay(0, 0, n, money, work);
        System.out.println("最小费用为：" + minPay);
    }
    public static int minPay = 10000;
    public static int[] array = new int[30];
    public static int count = 0;
    /* 
     * t表示深度层级， 
     * nowPay表示当前的累计费用
     */
    public static void searchMinPay(int t, int nowPay, int n, int[][] money, int[] work) {
        count++;
        System.out.println("第" + count + "次：" + "nowPay：" + nowPay + "    minPay：" + minPay);
        if ((nowPay + array[t]) > minPay || t > n) {
            return;
        }
        if (t > n) {
            return;
        }
        if (t == n) {
            if (nowPay < minPay) {
                minPay = nowPay;
            }
            return;
        }
        for (int j = 1; j <= n; j++) {
            if (work[j] == 0) {
                work[j] = 1;
                searchMinPay(t + 1, nowPay + money[t + 1][j], n, money, work);
                work[j] = 0;
            }
        }
    }
}

四、优化思路

minPay的初始值优化：将minPay初始值设置为一个可行解的总费用，这样在回溯过程中更早地剪枝。可以通过将对角线上的工作分配给对应的工人来得到一个可行解。

分配方式的筛选机制优化：预处理费用数组，计算每一行的最小值并存储在一个一维数组中。这样，在分配时，可以快速判断当前分配是否会导致总费用超过minPay，从而剪枝。

进一步优化：将一维数组array初始化为二维数组money每一行元素的最小值，并对其进行反向累加。这样，在分配时，可以直接加上对应的数组元素，快速判断是否需要继续分配。

五：优化之后的代码

import java.util.Scanner;
public class test {
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = s.nextInt();
        int[][] money = new int[n + 1][n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++) {
                money[i][j] = s.nextInt();
            }
        }
        s.close();
        int[] work = new int[n + 1];
        int minPay = 0;
        for (int i = 1; i <= n; i++) {
            minPay += money[i][i];
        }
        int[] array = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int minvalue = Integer.MAX_VALUE;
            for (int j = 1; j <= n; j++) {
                if (money[i][j] < minvalue) {
                    minvalue = money[i][j];
                }
            }
            array[i] = minvalue;
        }
        for (int i = n - 1; i >= 1; i--) {
            array[i] += array[i + 1];
        }
        searchMinPay(0, 0, n, money, work);
        System.out.println("最小费用为：" + minPay);
    }
    public static int minPay = 10000;
    public static int[] array = new int[30];
    public static int count = 0;
    /* 
     * t表示深度层级， 
     * nowPay表示当前的累计费用
     */
    public static void searchMinPay(int t, int nowPay, int n, int[][] money, int[] work) {
        count++;
        System.out.println("第" + count + "次：" + "nowPay：" + nowPay + "    minPay：" + minPay);
        if ((nowPay + array[t]) > minPay || t > n) {
            return;
        }
        if (t > n) {
            return;
        }
        if (t == n) {
            if (nowPay < minPay) {
                minPay = nowPay;
            }
            return;
        }
        for (int j = 1; j <= n; j++) {
            if (work[j] == 0) {
                work[j] = 1;
                searchMinPay(t + 1, nowPay + money[t + 1][j], n, money, work);
                work[j] = 0;
            }
        }
    }
}

结论

通过上述优化，算法的效率得到了显著提升，能够更快地找到最小的总费用。代码实现了回溯法并结合剪枝技术，确保了在合理的时间内解决问题。

上一篇：8086汇编语言：输入一个十六进制的多位数将其转化为十进制输出

下一篇：操作系统：缓冲技术的相关介绍

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！