题目形容
这是 LeetCode 上的 473. 火柴拼正方形 ，难度为 中等。
Tag : 「剪枝」、「DFS」、「爆搜」、「模拟退火」、「启发式搜寻」
你将失去一个整数数组 matchsticks，其中 $matchsticks[i]$ 是第 i 个火柴棒的长度。你要用 所有的火柴棍 拼成一个正方形。
你 不能折断 任何一根火柴棒，但你能够把它们连在一起，而且每根火柴棒必须 应用一次 。
如果你能使这个正方形，则返回 true，否则返回 false。
示例 1:
输出: matchsticks = [1,1,2,2,2]输入: true解释: 能拼成一个边长为2的正方形，每边两根火柴。示例 2:
输出: matchsticks = [3,3,3,3,4]输入: false解释: 不能用所有火柴拼成一个正方形。提醒:
- $1 <= matchsticks.length <= 15$
- $1 <= matchsticks[i] <= 10^8$
祝大家儿童节高兴，永葆童心，始终凶恶 ~
DFS 剪枝
为了不便，咱们称 matchsticks 为 ms。
数据范畴为 $n = 15$，奢侈的 DFS 爆搜（搜寻过程中保护一个大小为 $4$ 的数组 cur，数组中的每一位代表正方形一条边长所应用到的火柴总长度，若最终数组中每一位均等于 $t = \frac{\sum_{i = 0}^{n - 1}ms[i]}{4}$，代表存在非法计划）复杂度为 $4^n$，会 TLE。
咱们思考如何进行「剪枝」。
首先一个较为显著的剪枝操作是进行「可行性剪枝」：咱们在决策 $ms[idx]$ 时，如果将其累加到某个 $cur[i]$ 之后，会导致 $cur[i] > t$，则阐明必然不会是非法计划，该分支不再往后搜寻。
另外一个较为 trick 的剪枝是通过调整搜寻程序来进行「重复性剪枝」：咱们能够先对 ms 排倒序，进行「从大到小」的爆搜。实质上，咱们是将一些小火柴反复放到某几个桶的搜寻门路（其实对应的是雷同的调配计划），放到了最初解决。
代码：
class Solution { int[] ms; int t; public boolean makesquare(int[] _ms) { ms = _ms; int sum = 0; for (int i : ms) sum += i; t = sum / 4; if (t * 4 != sum) return false; Arrays.sort(ms); return dfs(ms.length - 1, new int[4]); } boolean dfs(int idx, int[] cur) { if (idx == -1) { boolean ok = true; for (int i : cur) { if (i != t) ok = false; } return ok; } for (int i = 0; i < 4; i++) { int u = ms[idx]; if (cur[i] + u > t) continue; cur[i] += u; if (dfs(idx - 1, cur)) return true; cur[i] -= u; } return false; }}- 工夫复杂度：$O(4^n)$
- 空间复杂度：排序的复杂度为 $O(\log{n})$，疏忽递归带来的额定空间开销，复杂度为 $O(\log{n})$
模拟退火
事实上，这道题还能应用「模拟退火」进行求解。
因为将 $n$ 个数划分为 $4$ 份，等效于用 $n$ 个数结构出一个「特定排列」，而后对「特定排列」进行固定模式的结构逻辑，就能实现「答案」与「最优排列」的对应关系。
基于此，咱们能够应用「模拟退火」进行求解。
单次迭代的根本流程：
- 随机抉择两个下标，计算「替换下标元素前对应序列的得分」&「替换下标元素后对应序列的得分」
- 如果温度降落（替换后的序列更优），进入下一次迭代
- 如果温度回升（替换前的序列更优），以「肯定的概率」复原现场（再替换回来）
值得一提的是，这道题造数据的人非常有程度，在最初一个样例中放了个卡 SA 的数据：
[403,636,824,973,815,318,881,506,863,21,834,211,316,772,803]但我不晓得为什么 LC 的提交后果会这么奇怪，已通过 184/183 样例？是总样例数哪个中央更新漏了，还是缓存没刷新：
这个数据点优良在于起始排序能够导致咱们固定的 calc 逻辑最终落入部分最优。针对这种状况，也很好解决，只须要在执行 SA 之前，先对原数组进行一次随机化打乱即可。
代码（2022/06/01 可通过）：
class Solution { int ms[]; int n, k; Random random = new Random(20220601); boolean ans = false; double hi = 1e4, lo = 1e-4, fa = 0.98; int N = 400; int calc() { int diff = 0; for (int i = 0, j = 0; i < 4; i++) { int cnt = 0; while (j < n && cnt < k) cnt += ms[j++]; diff += Math.abs(cnt - k); } if (diff == 0) ans = true; return diff; } void sa() { for (double t = hi; t > lo && !ans; t *= fa) { int a = random.nextInt(n), b = random.nextInt(n); int prev = calc(); swap(ms, a, b); int cur = calc(); int diff = prev - cur; if (Math.log(diff / t) > random.nextDouble()) swap(ms, a, b); } } public boolean makesquare(int[] _ms) { ms = _ms; n = ms.length; int sum = 0; for (int i : ms) sum += i; k = sum / 4; if (k * 4 != sum) return false; shuffle(ms); while (N-- > 0) sa(); return ans; } void shuffle(int[] arr) { int n = arr.length; for (int i = n; i > 0; i--) { int idx = random.nextInt(i); swap(arr, idx, i - 1); } } void swap(int[] arr, int i, int j) { int c = arr[i]; arr[i] = arr[j]; arr[j] = c; }}我猜你问
Q0. 模拟退火有何危险？
随机算法，会面临 WA 和 TLE 危险。
Q1. 模拟退火中的参数如何敲定的？
依据教训猜的，而后提交。依据后果是 WA 还是 TLE 来决定之后的调参方向。如果是 WA 阐明局部数据落到了「部分最优」或者尚未达到「全局最优」。
Q2. 参数如何调整？
如果是 WA 了，个别我是优先调大 fa 参数，使降温变慢，来变相减少迭代次数；如果是 TLE 了，个别是优先调小 fa 参数，使降温变快，减小迭代次数。总迭代参数 N 也是同理。
能够简略了解调大 fa 代表将「大步」改为「baby step」，避免越过全局最优，同时减少总执行步数。
Q3. 对于「模拟退火」正确性？
随机种子不变，测试数据不变，迭代参数不变，那么退火的过程就是恒定的，必然都能找到这些测试样例的「全局最优」。
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.472 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou... 。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
本文由mdnice多平台公布