Algorithm

最近刚完成某 N 厂的 OA 题目，难度比想象中高了很多，不过里面的问题非常有意思。正好趁求职这段时间复盘一下题目，顺带挖掘一下隐含的一些问题。

要求：给定 $n, m, k$，其中 $n, m, k$ 都是正整数，模拟重排过程并返回调用moveRobot的次数，越少越好。SPJ 会检查重排后的结果。

在多目标优化问题中，基于帕累托支配关系的最优解集（即帕累托前沿，PF）很可能不是有限的集合；多数情况下可能是高维空间中某一区域。因此，优化算法的目标就是在有限时间里得到一个能够表现出 PF 的形状、且分布良好的解集。这也是为什么收敛性和多样性在演化多目标优化算法中是两大重要指标。经典的基于支配关系的算法框架（如 NSGA-II 等）依靠适应值来维护解集的多样性，避免边缘解的丢失以及解过于密集的现象。而 MOEA/D 的提出，将分解的思想重新…

在遗传算法中，如何从亲代中产生好的子代个体是至关重要的问题。本文将收录一些经典的、但理解起来略有难度的交叉和变异算子（Crossover and mutation operators），并简要叙述一下其背后的原理。

本文中各种算子的中文名称均为个人直译结果，不代表学术界公认译名（本来也基本没有……）。

最近在学习并尝试实现演化多目标优化的相关算法，希望我能通过这篇博客把算法了解得更加透彻 orz

在多目标优化领域，一般来说，决策变量和目标都是由多个元素组成的，而不同目标之间往往难以比较。如果将决策/目标视作一个向量 $\mathbf{x}$，我们用帕累托支配（Pareto dominance）来刻画向量间的关系。对于两个 $n$ 维向量 $\mathbf{x}^{(1)} = (x^{(1)}_1, \dots, x^{(1)}_n)^T, \mathbf{x}^{(2)} = (x^{(2)}_1, \dots, x^{(2)}_n)^T$，我们称 $\mathbf{x}^{(1)}$ 支配 $\mathbf{x}^{(2)}$（记作 $\mathbf{x}^{(1)} \prec \mathbf{x}^{(2)}$）当且仅当…

龟速补上欠下的账 ing……

写完发现读着好晦涩，但数学不就是这样的吗🌚

$G = (V, E)$ 是有向、无平行边的图，每条边边权为正，其中有一个源点（source）$s$ 和汇点（sink）$t$ 满足：没有一条边以 $t$ 为起点，或以 $s$ 为终点。

对某边 $e \in E$，记该边边权为 $c(e)$。

本文仅面向学习 FFT 算法的 CS 学生。文中关于傅里叶变换的阐述仅用于帮助快速简要地理解算法背后时域/频域变换的意义，逻辑性不会像「信号与系统」课那么强。本人没系统学过「信号与系统」这门课，能写出这篇文章也要感谢来自 FDU、SCUT 的两位同学的帮助。欢迎各位大佬对本文内容进行指正！

要系统学习「信号与系统」的内容，可参阅奥本海默著的《信号与系统》一书。

在我学习 FFT 时，第一个面对的问题背景是「给定两个多项式，如何快速求得二者的乘积？」老师或…

题目来自 Algorithm design / Jon Kleinberg, Eva Tardos.—1st ed. 的 4.3 节。

假设现在有一个容量为 $k$ 的缓存（cache）空间，和 $m$ 个内存 block 访问请求 $d_1, d_2, \dots, d_m$。对于第 $i$ 个请求 $d_i$，如果请求的 block 在缓存中，称其为一次命中（hit），否则称其为一次失效/缺页（miss）。若出现 miss，则需要从内存中读取该 block 并写入缓存（若缓存已满则会替换掉其中一个 block）。现给定请求序列，求一个最优缓存（caching）策略使得 miss 尽可能少。

想不到促使我学习插头 DP 的动机竟然是一道算法课的 Lab 题，还被网上的假教程演了半天……姑且把学到的东西写一写，纪念一下我对着一屏幕的表画了大半天图的自闭时光。

起这个标题的原因实在一篇博客里看到“转移过程十分码农”，敲完代码深以为然，就借用过来了。

以下内容仅为插头 DP 的一种应用情形。若要应用于其他题目，需要对过程略作修改。

前置知识：状态压缩 DP、BFS、哈希