模拟退火模板和 "我问你答"。
题目描述
这是 LeetCode 上的「1723. 完成所有工作的最短时间」,难度为「困难」。
Tag : 「DFS」、「模拟退火」、「启发式搜索」、「随机化」
给你一个整数数组 jobs
,其中
是完成第
项工作要花费的时间。
请你将这些工作分配给
位工人。所有工作都应该分配给工人,且每项工作只能分配给一位工人。
工人的 工作时间 是完成分配给他们的所有工作花费时间的总和。
请你设计一套最佳的工作分配方案,使工人的 最大工作时间 得以 最小化 。
返回分配方案中尽可能「最小」的 最大工作时间 。
示例 1:
输入:jobs = [3,2,3], k = 3
输出:3
解释:给每位工人分配一项工作,最大工作时间是 3 。
示例 2:
输入:jobs = [1,2,4,7,8], k = 2
输出:11
解释:按下述方式分配工作:
1 号工人:1、2、8(工作时间 = 1 + 2 + 8 = 11)
2 号工人:4、7(工作时间 = 4 + 7 = 11)
最大工作时间是 11 。
提示:
DFS(TLE)
一看数据范围只有
,我猜不少同学上来就想 DFS
,但是注意 n
和 k
同等规模的,爆搜(DFS
)的复杂度是
的。
那么极限数据下的计算量为
,远超运算量
。
抱着侥幸的心理一运行,很顺利的卡在了
个数据:
[254,256,256,254,251,256,254,253,255,251,251,255] // n = 12
10 // k = 10
代码:
class Solution {
int[] jobs;
int n, k;
int ans = 0x3f3f3f3f;
public int minimumTimeRequired(int[] _jobs, int _k) {
jobs = _jobs;
n = jobs.length;
k = _k;
int[] sum = new int[k];
dfs(0, sum, 0);
return ans;
}
/**
* u : 当前处理到那个 job
* sum : 工人的分配情况 例如:sum[0] = x 代表 0 号工人工作量为 x
* max : 当前的「最大工作时间」
*/
void dfs(int u, int[] sum, int max) {
if (max >= ans) return;
if (u == n) {
ans = max;
return;
}
for (int i = 0; i < k; i++) {
sum[i] += jobs[u];
dfs(u + 1, sum, Math.max(sum[i], max));
sum[i] -= jobs[u];
}
}
}
- 时间复杂度:
- 空间复杂度:
优先分配「空闲工人」的 DFS
那么 DFS
就没法过了吗?
除了 max >= ans
以外,我们还要做些别的剪枝吗?
我们可以重新审视一下这道题。
题目其实是让我们将
个数分为
份,并且尽可能让
份平均。这样的「最大工作时间」才是最小的。
但在朴素的 DFS
中,我们是将每个任务依次分给每个工人,并递归此过程。
对应的递归树其实是一颗高度为
的
阶树。
所以其实我们第一次更新的 ans
其实是「最差」的答案(所有的任务都会分配给
号工人),最差的 ans
为所有的 job
的总和(带编号的方块代表工人):
因此我们朴素版的 DFS
其实是弱化了 max >= ans
剪枝效果的。
那么想要最大化剪枝效果,并且尽量让
份平均的话,我们应当调整我们对于「递归树」的搜索方向:将任务优先分配给「空闲工人」(带编号的方块代表工人):
树还是那棵树,但是搜索调整分配优先级后,我们可以在首次取得一个「较好」的答案,来增强我们的 max >= ans
剪枝效益。
事实上,当做完这个调整,我们能实现从 TLE 到 99% 的提升 ???? ????
代码:
class Solution {
int[] jobs;
int n, k;
int ans = 0x3f3f3f3f;
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;
}
/**
* 【补充说明】不理解可以看看下面的「我猜你问」的 Q5 哦 ~
*
* 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;
}
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];
}
}
}
- 时间复杂度:
- 空间复杂度:
模拟退火
事实上,这道题还能使用「模拟退火」进行求解。
因为将
个数划分为
份,等效于用
个数构造出一个「特定排列」,然后对「特定排列」进行固定模式的任务分配逻辑,就能实现「答案」与「最优排列」的对应关系。
基于此,我们可以使用「模拟退火」进行求解。
单次迭代的基本流程:
- 随机选择两个下标,计算「交换下标元素前对应序列的得分」&「交换下标元素后对应序列的得分」
- 如果温度下降(交换后的序列更优),进入下一次迭代
- 如果温度上升(交换前的序列更优),以「一定的概率」恢复现场(再交换回来)
❝对于一个能够运用模拟退火求解的问题,最核心的是如何实现
calc
方法(即如何定义一个具体方案的得分),其余均为模板内容。 ❞
代码:
class Solution {
int[] jobs;
int[] works = new int[20];
int n, k;
int ans = 0x3f3f3f3f;
Random random = new Random(20210508);
// 最高温/最低温/变化速率(以什么速度进行退火,系数越低退火越快,迭代次数越少,落入「局部最优」(WA)的概率越高;系数越高 TLE 风险越大)
double hi = 1e8, lo = 1e-4, fa = 0.90;
// 迭代次数,与变化速率同理
int N = 400;
// 计算当前 jobs 序列对应的最小「最大工作时间」是多少
int calc() {
Arrays.fill(works, 0);
for (int i = 0; i < n; i++) {
// [固定模式分配逻辑] : 每次都找最小的 worker 去分配
int idx = 0, cur = works[idx];
for (int j = 0; j < k; j++) {
if (works[j] < cur) {
cur = works[j];
idx = j;
}
}
works[idx] += jobs[i];
}
int cur = 0;
for (int i = 0; i < k; i++) cur = Math.max(cur, works[i]);
ans = Math.min(ans, cur);
return cur;
}
void shuffle(int[] nums) {
for (int i = n; i > 0; i--) {
int idx = random.nextInt(i);
swap(nums, idx, i - 1);
}
}
void swap(int[] arr, int i, int j) {
int c = arr[i];
arr[i] = arr[j];
arr[j] = c;
}
void sa() {
shuffle(jobs);
for (double t = hi; t > lo; t *= fa) {
int a = random.nextInt(n), b = random.nextInt(n);
int prev = calc(); // 退火前
swap(jobs, a, b);
int cur = calc(); // 退火后
int diff = cur - prev;
// 退火为负收益(温度上升),以一定概率回退现场
if (Math.log(diff / t) > random.nextDouble()) swap(jobs, a, b);
}
}
public int minimumTimeRequired(int[] _jobs, int _k) {
jobs = _jobs;
n = jobs.length;
k = _k;
while (N-- > 0) sa();
return ans;
}
}
- 时间复杂度:启发式搜索不讨论时空复杂度
- 空间复杂度:启发式搜索不讨论时空复杂度
我猜你问
Q0. 模拟退火有何风险?
随机算法,会面临 WA
和 TLE
风险。
Q1. 模拟退火中的参数如何敲定的?
根据经验猜的,然后提交。根据结果是 WA
还是 TLE
来决定之后的调参方向。如果是 WA
说明部分数据落到了「局部最优」或者尚未达到「全局最优」。
Q2. 参数如何调整?
如果是 WA
了,一般我是优先调大 fa 参数,使降温变慢,来变相增加迭代次数;如果是 TLE
了,一般是优先调小 fa 参数,使降温变快,减小迭代次数。总迭代参数 N
也是同理。
可以简单理解调大 fa 代表将「大步」改为「baby step」,防止越过全局最优,同时增加总执行步数。
可以结合我不同的 fa 参数的提交结果来感受下:
Q3. 关于「模拟退火」正确性?
随机种子不变,测试数据不变,迭代参数不变,那么退火的过程就是恒定的,必然都能找到这些测试样例的「全局最优」。
Q4. 需要掌握「模拟退火」吗?
还是那句话,特别特别特别有兴趣的可以去了解一下。
但绝对是在你已经彻底理解「剪枝 DFS」和我没写的「状态压缩 DP」之后再去了解。
Q5. 在「剪枝 DFS」中为什么「优先分配空闲工人」的做法是对的?
首先要明确,递归树还是那棵递归树。
所谓的「优先分配空闲工人」它并不是「贪心模拟」思路,而只是一个「调整搜索顺序」的做法。
「优先分配空闲工人」不代表不会将任务分配给有工作的工人,仅仅代表我们先去搜索那些「优先分配空闲工人」的方案。
然后将得到的「合法解」配合 max >= ans
去剪枝掉那些「必然不是最优解」的方案。
本质上,我们并没有主动的否决某些方案(也就是我们并没有改动递归树),我们只是调整了搜索顺序来剪枝掉了一些「必然不是最优」的搜索路径。
最后
这是我们「刷穿 LeetCode」系列文章的第 No.1723
篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。
在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。
在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
推荐阅读
-
模拟退火模板和 "我问你答"。
-
计算机视觉中,究竟有哪些好用的目标跟踪算法(下)-快速变形主要因为CF是模板类方法。容易跟丢这个比较好理解,前面分析了相关滤波是模板类方法,如果目标快速变形,那基于HOG的梯度模板肯定就跟不上了,如果快速变色,那基于CN的颜色模板肯定也就跟不上了。这个还和模型更新策略与更新速度有关,固定学习率的线性加权更新,如果学习率太大,部分或短暂遮挡和任何检测不准确,模型就会学习到背景信息,积累到一定程度模型跟着背景私奔了,一去不复返。如果学习率太小,目标已经变形了而模板还是那个模板,就会变得不认识目标。(举个例子,多年不见的同学,你很可能就认不出了,而经常见面的同学,即使变化很大你也认识,因为常见的同学在你大脑里面的模型在持续更新,而多年不见就是很久不更新) 快速运动主要是边界效应(Boundary Effets),而且边界效应产生的错误样本会造成分类器判别力不够强,下面分训练阶段和检测阶段分别讨论。 训练阶段,合成样本降低了判别能力。如果不加余弦窗,那么移位样本是长这样的: 除了那个最原始样本,其他样本都是“合成”的,100*100的图像块,只有1/10000的样本是真实的,这样的样本集根本不能拿来训练。如果加了余弦窗,由于图像边缘像素值都是0,循环移位过程中只要目标保持完整那这个样本就是合理的,只有目标中心接近边缘时,目标跨越边界的那些样本是错误的,这样虽不真实但合理的样本数量增加到了大约2/3(padding= 1),即使这样仍然有1/3(3000/10000)的样本是不合理的,这些样本会降低分类器的判别能力。再者,加余弦窗也不是“免费的”,余弦窗将图像块的边缘区域像素全部变成0,大量过滤掉分类器本来非常需要学习的背景信息,原本训练时判别器能看到的背景信息就非常有限,我们还加了个余弦窗挡住了背景,这样进一步降低了分类器的判别力(是不是上帝在我前遮住了帘。不是上帝,是余弦窗)。 检测阶段,相关滤波对快速运动的目标检测比较乏力。相关滤波训练的图像块和检测的图像块大小必须是一样的,这就是说你训练了一个100*100的滤波器,那你也只能检测100*100的区域,如果打算通过加更大的padding来扩展检测区域,那样除了扩展了复杂度,并不会有什么好处。目标运动可能是目标自身移动,或摄像机移动,按照目标在检测区域的位置分四种情况来看: 如果目标在中心附近,检测准确且成功。 如果目标移动到了边界附近但还没有出边界,加了余弦窗以后,部分目标像素会被过滤掉,这时候就没法保证这里的响应是全局最大的,而且,这时候的检测样本和训练过程中的那些不合理样本很像,所以很可能会失败。 如果目标的一部分已经移出了这个区域,而我们还要加余弦窗,很可能就过滤掉了仅存的目标像素,检测失败。 如果整个目标已经位移出了这个区域,那肯定就检测失败了。 以上就是边界效应(Boundary Effets),推荐两个主流的解决边界效应的方法,但速度比较慢,并不推荐用于实时场合。