欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

任务分配问题 | 分支限界法(限下界)

程序员文章站 2022-05-19 15:53:20
...

任务分配问题

成绩 10 开启时间 2020年04月14日 星期二 10:10
折扣 0.8 折扣时间 2020年05月30日 星期六 23:55
允许迟交 关闭时间 2020年05月30日 星期六 23:55

只有一组测试用例。
输入:第一行是操作员的人数n(4=<n<=11),接下来的n行里每行有n个数,分别表示第i名操作员完成第i项任务的时间。
输出:完成所有任务的最短时间。

  测试输入 期待的输出 时间限制 内存限制 额外进程
测试用例 1 以文本方式显示
  1. 4↵
  2. 3 8 4 12↵
  3. 9 12 13 5↵
  4. 8 7 9 3↵
  5. 12 7 6 8↵
以文本方式显示
  1. 21↵
1秒 64M 0

       此题当然可以使用回溯法解决,但是这里也可以用分支限界。不管怎样,都是遍历所有的决策树,只是分支限界这里是 bfs 遍历。我们针对每一个任务来讨论,为它分配未被选取的人员


1、构造 min_cost 数组(贪心最小选取)

        这里是求最小消耗时间,那么我们必须要限定下界,即该决策路可以达到的最小消耗。首先我们将第 i 件事的最小耗时存储在 min_cost [ i ] 中。

/* 找到数组a中的最小元素 */
int findMin(int a[]) {
    int ans = INT_MAX;
    for (int i = 1; i <= n; i++)
        ans = min(ans, a[i]);
    return ans;
}

int min_cost[MAXN];  //min_cost[i]:完成 i 的最小消耗

void setMinCost() {
    for (int i = 1; i <= n; i++) {
        int temp = findMin(Time[i]);
        min_cost[i - 1] = temp;
    }
}

2、对于决策点限定下界 key

    对于每一个决策的节点:

  •  cur_cost 记录当前已经安排的事情的耗时
  •  rest_cost 记录未安排的事情所需的最短时间:任务分配问题 | 分支限界法(限下界)
  •  下界 key = cur_cost + rest_costkey越小,该决策越可能找到最优解)
  •  数组 vis[ ] 记录哪些人已经被选取过了
  •  step 表示当前已经完成 1..step 任务,接下来考虑 steap + 1 的任务
typedef struct node {
    int key;
    int cur_cost;
    int rest_cost = 0;  //完成step + 1..n的最小消耗
    int step;   //此节点已经完成 1..step 任务

    bool vis[MAXN] = {false};
    /* 构造函数1 */
    node(int cc, int st) {
        cur_cost = cc;
        step = st;
        for (int i = 0; i < n; i++)
            if (!vis[i])
                rest_cost += min_cost[i];
        key = cur_cost + rest_cost;
    };
    /* 构造函数2 */
    node(int cc, int st, bool v[]) {
        cur_cost = cc;
        step = st;
        for (int i = step; i < n; i++)
            if (!vis[i])
                rest_cost += min_cost[i];
        key = cur_cost + rest_cost;
        for (int i = 1; i <= n; i++)
            vis[i] = v[i];
    };

    /* 重载<运算符,以便于优先队列的创建 */
    friend bool operator<(struct node x, struct node y) {
        return x.key > y.key;
    }
} Node;

3、广度优先搜索

       建立一个优先队列,起初从根节点开始。之后每次选取 key 最小的节点讨论,依次考虑下一个事情的决策,并依次将决策子节点加入优先队列。

      当取出节点 step = n - 1 时,说明此节点正在考虑最后一件事情,此时应该更新最小值

      当取出的节点 step = n 时,即节点(这是叶节点)已经分配完毕,最小值肯定已经取得!退出 bfs

void bfs() {
    priority_queue<Node> Q;
    Node head(0, 0);

    while (head.step < n) {
        int step = head.step;
        int cur_cost = head.cur_cost;

        /* 依次选取每一个人 */
        for (int i = 1; i <= n; i++) {
            int maybe = cur_cost + Time[step + 1][i];
            if (head.vis[i] || maybe >= ans)  //约束条件与限界条件
                continue;

            if (step == n - 1)   //正在决策第n件事
                ans = min(ans, maybe);   //更新最小值

            head.vis[i] = true;
            Node temp(maybe, step + 1, head.vis);
            Q.push(temp);
            head.vis[i] = false;
        }

        /* 出队key最小的 */
        head = Q.top();
        Q.pop();
    }
}

4、完整AC代码

         注意:处理输入的时候,我把它反过来了。因为我是针对每一件事情的分配来讨论,所以希望一件事情分配每个人的消耗能储存在一行~

#include <cstdio>
#include <algorithm>
#include <queue>
#include <climits>

using namespace std;
#define MAXN 13

int Time[MAXN][MAXN];  //time[i][j]:第i件事给第j人做
int n;

/* 找到数组a中的最小元素 */
int findMin(int a[]) {
    int ans = INT_MAX;
    for (int i = 1; i <= n; i++)
        ans = min(ans, a[i]);
    return ans;
}

int min_cost[MAXN];  //min_cost[i]:完成 i 的最小消耗
int ans;

void setMinCost() {
    for (int i = 1; i <= n; i++) {
        int temp = findMin(Time[i]);
        min_cost[i - 1] = temp;
    }
}

void init() {
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &Time[j][i]);

    setMinCost();
    ans = INT_MAX;
}

typedef struct node {
    int key;
    int cur_cost;
    int rest_cost = 0;  //完成step + 1..n的最小消耗
    int step;   //此节点已经完成 1..step 任务

    bool vis[MAXN] = {false};

    node(int cc, int st) {
        cur_cost = cc;
        step = st;
        for (int i = 0; i < n; i++)
            if (!vis[i])
                rest_cost += min_cost[i];
        key = cur_cost + rest_cost;
    };

    node(int cc, int st, bool v[]) {
        cur_cost = cc;
        step = st;
        for (int i = step; i < n; i++)
            if (!vis[i])
                rest_cost += min_cost[i];
        key = cur_cost + rest_cost;
        for (int i = 1; i <= n; i++)
            vis[i] = v[i];
    };

    friend bool operator<(struct node x, struct node y) {
        return x.key > y.key;
    }
} Node;

void bfs() {
    priority_queue<Node> Q;
    Node head(0, 0);

    while (head.step < n) {
        int step = head.step;
        int cur_cost = head.cur_cost;

        /* 依次选取每一个人 */
        for (int i = 1; i <= n; i++) {
            int maybe = cur_cost + Time[step + 1][i];
            if (head.vis[i] || maybe >= ans)
                continue;

            if (step == n - 1)
                ans = min(ans, maybe);

            head.vis[i] = true;
            Node temp(maybe, step + 1, head.vis);
            Q.push(temp);
            head.vis[i] = false;
        }

        /* 出队key最小的 */
        head = Q.top();
        Q.pop();
    }
}

int main() {
    init();
    bfs();
    printf("%d\n", ans);
}

任务分配问题 | 分支限界法(限下界)

相关标签: # ⑦分支界限