任务分配问题 | 分支限界法（限下界）

旧城等待， 2023-02-10 05:19 109阅读 0赞

> ## 任务分配问题 ##
> 
> <table> 
>  <tbody> 
>   <tr> 
>    <td>成绩</td> 
>    <td>10</td> 
>    <td>开启时间</td> 
>    <td>2020年04月14日 星期二 10:10</td> 
>   </tr> 
>   <tr> 
>    <td>折扣</td> 
>    <td>0.8</td> 
>    <td>折扣时间</td> 
>    <td>2020年05月30日 星期六 23:55</td> 
>   </tr> 
>   <tr> 
>    <td>允许迟交</td> 
>    <td>否</td> 
>    <td>关闭时间</td> 
>    <td>2020年05月30日 星期六 23:55</td> 
>   </tr> 
>  </tbody> 
> </table>
> 
> 只有一组测试用例。  
> 输入：第一行是操作员的人数n(4=<n<=11)，接下来的n行里每行有n个数，分别表示第i名操作员完成第i项任务的时间。  
> 输出：完成所有任务的最短时间。
> 
> <table> 
>  <thead> 
>   <tr> 
>    <th>&nbsp;</th> 
>    <th>测试输入</th> 
>    <th>期待的输出</th> 
>    <th>时间限制</th> 
>    <th>内存限制</th> 
>    <th>额外进程</th> 
>   </tr> 
>  </thead> 
>  <tbody> 
>   <tr> 
>    <td>测试用例 1</td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=100275&amp;test=121521&amp;type=in&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>4↵</li> 
>      <li>3&nbsp;8&nbsp;4&nbsp;12↵</li> 
>      <li>9&nbsp;12&nbsp;13&nbsp;5↵</li> 
>      <li>8&nbsp;7&nbsp;9&nbsp;3↵</li> 
>      <li>12&nbsp;7&nbsp;6&nbsp;8↵</li> 
>     </ol></td> 
>    <td><a href="http://lexue.bit.edu.cn/mod/programming/testcase/download_io.php?id=100275&amp;test=121521&amp;type=out&amp;download=0" rel="nofollow">以文本方式显示</a> 
>     <ol> 
>      <li>21↵</li> 
>     </ol></td> 
>    <td>1秒</td> 
>    <td>64M</td> 
>    <td>0</td> 
>   </tr> 
>  </tbody> 
> </table>

--------------------

此题当然可以使用回溯法解决，但是这里也可以用分支限界。不管怎样，都是遍历所有的决策树，只是分支限界这里是 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** 记录未安排的事情所需的最短时间：![\\sum\_\{step\} ^\{n\}rest\[ i \]][sum_step_ _n_rest_ i]
 *   下界 **key = cur\_cost + rest\_cost（**key越小，该决策越可能找到最优解）
 *   **数组 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);
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70][]

[sum_step_ _n_rest_ i]: https://private.codecogs.com/gif.latex?%5Csum_%7Bstep%7D%20%5E%7Bn%7Drest%5B%20i%20%5D
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200520141948673.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw==,size_16,color_FFFFFF,t_70