启发性搜索算法

算法 leetcode

编程算法

发布日期: 2021-05-11

作者: 锦泉

文章字数: 977

阅读时长: 3 分

阅读次数:

启发性搜索

在宽度优先和深度优先搜索里面，我们都是根据搜索的顺序依次进行搜索，可以称为盲目搜索，搜索效率非常低。

在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。

Leetcode 1723

1723. 完成所有工作的最短时间

给你一个整数数组 jobs ，其中 jobs[i] 是完成第 i 项工作要花费的时间。

请你将这些工作分配给 k 位工人。所有工作都应该分配给工人，且每项工作只能分配给一位工人。工人的工作时间是完成分配给他们的所有工作花费时间的总和。请你设计一套最佳的工作分配方案，使工人的最大工作时间得以最小化。

返回分配方案中尽可能最小的最大工作时间。

参考宫水三叶的解法，记录一下：

class Solution {
    int[] jobs;
    int n, k;
    int ans = 0x3f3f3f3f;//无穷大，并且不像Integer.MAX_VALUE加1直接溢出
    public int minimumTimeRequired(int[] _jobs, int _k) {
        jobs = _jobs;
        n = jobs.length;
        k = _k;
        int[] sum = new int[k];
        dfs(0, 0, sum, 0);
        return ans;
    }
    /**
     * u     : 当前处理到那个 job
     * used  : 当前分配给了多少个工人了
     * sum   : 工人的分配情况          例如：sum[0] = x 代表 0 号工人工作量为 x
     * max   : 当前的「最大工作时间」
     */
    void dfs(int u, int used, int[] sum, int max) {
        if (max >= ans) return;
        if (u == n) {
            ans = max;
            return;
        }
        // 优先分配给「空闲工人」
        if (used < k) {
            sum[used] = jobs[u];
            dfs(u + 1, used + 1, sum, Math.max(sum[used], max));
            sum[used] = 0;
        }
        //i < used是精华！
        for (int i = 0; i < used; i++) {
            sum[i] += jobs[u];
            dfs(u + 1, used, sum, Math.max(sum[i], max));
            sum[i] -= jobs[u];
        }
    }
}

为什么是 i < used

      if (used < k) {
            sum[used] = jobs[u];
            dfs(u + 1, used + 1, sum, Math.max(sum[used], max));
            sum[used] = 0;
        }
        for (int i = 0; i < used; i++) {
            sum[i] += jobs[u];
            dfs(u + 1, used, sum, Math.max(sum[i], max));
            sum[i] -= jobs[u];
        }

当if语句执行完时，意味着平均分配时的解已经找完了。

现在尝试寻找不平均分配时的解。也就是尝试有空余人不分配任务，也就是有部分人先执行两个 / 多个任务而有部分人空着。也就是搜索树的剩余部分。

例：1 2 4分配给甲乙，if执行完之后，已经尝试了平均分配的情况：即先分配1给甲，随后分配2给乙（剩余的空闲的人），再搜索4。或其他情况。

if完成之后，现在平均分配方案已经全部尝试完毕，所以我们应该：尝试先将1分配给甲，再将2分配给甲，再搜索4。

如果有多个人，会依次在 sum[used] = 0位置时回溯多次，依次在每一次回溯时回退多个空余的人，继续搜索树。

注意：例：有三个人甲乙丙，if执行完成。第一轮：退出dfs(used+1)语句， sum[used] = 0语句回退空余的丙。进入for(i < used),对下一个任务在甲乙之间分配（注意此时used为2，区间为甲乙，和dfs(used+1)的参数不同）。然后进入dfs，这时再进if,给空余的丙分配任务。

第二轮，退出dfs,回退空余的乙丙，进入for(i < used),对下一个任务在甲之间分配。然后进入dfs，这时再进if,给空余的乙丙分配任务。再次进入回溯步骤。