不那么直观,但好像还是有点直观
两个同学,打水时间分别是
四个同学,打水时间分别是
还记得冒泡排序吗?
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++)
if (a[i] > a[j]) {
swap(a[i], a[j]);
}
和它的另一个版本
while (!is_sorted(a)) {
auto [i, j] = find_unordered(); // 返回任意 i < j, a[i] > a[j]
swap(a[i], a[j]);
}
第二个版本很有趣
交换论证:反过来假设存在一个不按照从小到大排序的最优解
依然是偷走桌上的物品
似乎就有点 “难以决定” 了
还按照价值从大到小放?
先求背包放满的最大价值,再从大到小拿?
并不适合贪心
贪心:排好顺序,不后悔
有时,排序的条件很有趣
给定
“局部搜索”
do {
b = have_some_try(a);
if (cost(b) < cost(a)) {
a = b;
}
} while (!should_terminate());
GPT-4-turbo回复:想象你在一个山上,目标是要到达山谷的最低点。但是,山上雾很大,你看不清远处的路。你只能感觉到脚下地面的倾斜方向,然后决定下一步往哪个方向走。在这个比喻中,山谷的最低点就像是我们训练深度神经网络时想要找到的最佳模型(即错误最小的模型),而你脚下地面的倾斜方向就像是梯度(Gradient),它告诉我们参数应该如何调整才能让模型的错误减少。
梯度下降的原理就是:通过计算当前位置(当前模型参数)的梯度(即错误变化的方向和大小),然后向梯度的反方向(因为我们是要下山,而梯度指向的是上升最快的方向)调整一小步,重复这个过程,直到找到山谷的最低点,也就是模型的错误最小的地方。
do {
bool fixedpoint = true;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
b = a;
swap(b[i], b[j]);
if (cost(b) < cost(a)) { // 交换使代价变小
a = b;
fixedpoint = false;
}
}
} while (!fixedpoint);
bool swap_is_useful(const string &i, const string &j) {
string mid;
for (int k = i + 1; k < j; k++) {
mid += a[k];
}
return BigInteger(a[i] + mid + a[j])
< BigInteger(a[j] + mid + a[i]);
// 长度相同,因此等价于
// a[i] + mid + a[j] < a[j] + mid + a[i]
}
如果只考虑相邻的 (mid 为空)?
a[i] + a[i+1] < a[i+1] + a[i]
最优解一定没有
局部最优解是否是全局最优解?
局部搜索:向更好的方向调整
计算机为什么叫电脑
有若干场比赛,每场比赛是连续进行的,覆盖时间段
(先假设所有区间端点都不同,容易处理)
到底应该选什么好呢?
我们是在解决问题
- 不是 “套公式套模板”
- 而是 “理解问题的结构”
观察法
什么是 “不会后悔” 的选择?
选最先结束的!
一定存在一个最优解,包含最先结束的区间
所以,如果区间有代价,贪心就不对了
以下算法也是正确的
国王邀请
国王不希望某个大臣获得特别多的奖赏,所以他想请你帮他安排一下队伍的顺序,使得获得奖赏最多的大臣所获奖赏尽可能的少
就算你猜是贪心,按什么排序呢?
怎么办?
特别提示:准确性训练
不要怕公式
用好草稿纸
贪心的两种表达方式
学习贪心算法
End. (Notebook)