Week 1 Intro & Randomised Algorithms
Intro
什么是进化计算？
受自然界启发的计算系统研究，例如自然进化（适者生存原则） 是解决搜索问题的一种通用算法
例子
- NASA用进化计算来计算天线最佳形状
- 利用进化计算设计机器人
- Blondie24——进化出的国际跳棋大师
- 通过遗传编程发明/重新发明电子电路。
- Evolutionary art
- Evolv Technologies 完成了1000万美元的A轮融资，用于扩展其基于进化AI的优化平台Ascend。
Randomised Algorithms
动机问题1：单独的螺母与螺栓问题
日常问题：给定一个螺栓和一组n个不同尺寸的螺母，找到一个与螺栓匹配的螺母。
数学形式：给定一个包含n个元素的数组，找到第一个值等于x的元素。
问题：如何用算法解决？如何高效地解决？
动机问题2：真正的螺母与螺栓问题
一位杂乱无章的木匠有一组n个不同尺寸的螺母和n个螺栓，他希望找到每对匹配的螺母和螺栓。每个螺母恰好匹配一个螺栓（反之亦然），但他只能将螺母与螺栓进行比较，即无法将螺母与螺母或螺栓与螺栓进行比较。
你能帮助木匠快速匹配螺母和螺栓吗？
这个问题被称为螺母与螺栓问题或锁与钥匙问题。
问题：如何将问题形式化？如何用算法解决？如何高效地解决？
动机问题3：如何帮助丹·布朗？
丹·布朗正在火星度假。他在笔记本电脑中发现了一份《达·芬奇密码》的数字手稿（一个长字符串）。他想将这份手稿与家中地球上的PC中保存的最终版本（也是一个长字符串）进行比较，看看它们是否相同。他可以访问家中PC中的手稿，但通信成本非常高昂。
问题：如何通过这条昂贵的通信渠道比较这两个版本？
引入随机算法
对于许多问题，随机化算法是最简单、最快速，或两者兼具的解决方案
如果按照算法所属种类分类的话，有以下几种：
- 分治算法，例如快速排序算法
- 动态规划算法
- 数学规划算法，例如线性规划
- 搜索与枚举算法
- 暴力算法：枚举所有可能的候选解并检查
- 改进的暴力算法，例如分支限界算法
- 启发式算法
- 局部搜索，例如贪心搜索
- 随机化算法，包括进化计算等
进化计算属于启发式算法
启发式算法定义：一种（通常简单的）算法，能够在合理的时间内为问题提供足够好的解决方案。 解决方案通常是非最优但令人满意的：
- 更快：作为暴力（穷举）搜索的替代方案
- 在速度与最优性、完整性、准确性或精确性之间进行权衡
通常用于解决其他算法（例如暴力算法）难以处理的问题。
包括确定性算法（例如局部搜索）和随机化算法。
随机化算法
随机化算法：一种在执行过程中通过随机选择来生成结果的启发式算法。 它利用随机数源来做出随机选择。 特点（缺点）：即使在固定输入下，输出或运行时间也可能变化（缺点）。
注意：随机选择或决策是常见的，有时甚至是有用的：例如《随机化决策的战略优势》。
目标：设计一种算法并进行分析，以证明其在每个输入上的行为很可能是良好的。
随机算法有两类：
- 利用随机数来找到问题的解决方案
- 利用随机数来改进问题的解决方案
对于第一类，我们有拉斯维加斯算法和蒙特卡洛算法。
Las Vegas Algorithm
一直试，直到正确，总是给出正确的结果，唯一的变化是不同运行之间的运行时间。 
Monte Carlo Algorithm
试一试，直到正确或者试够次数了。运行时间是确定性的，但结果可能以一定（通常较小）的概率出错。 
动机问题1的随机化
如果使用线形搜索算法，那么最坏O(n), 平均O((n+1)/2) ≈ O(n) 如果使用Las Vegas算法，平均O取决于输入，但最坏时间复杂度无界。 如果使用Monte Carlo算法，那么最坏O(1), 但是有一定概率出错。
动机问题2的随机化
Brute Force: O(n2) 如果螺栓可以和螺栓比较，螺母可以和螺母比较，那么可以quick sort之后对应。如果你总选第一个数，中间的数，最后一个数为pivot，那就是确定快排，平均Onlogn, 最坏On2, 如果你总随机选一个当pivot，那就是随机快排，平均Onlogn, 最坏2Onlogn。 
算法步骤：
- 随机选择一个螺栓作为基准（pivot）。
- 用这个螺栓划分所有螺母：
- 小于基准的螺母
- 等于基准的螺母（找到匹配的那一个）
- 大于基准的螺母
- 找到匹配的螺母后，用它划分所有螺栓：
- 小于匹配螺母的螺栓
- 匹配的螺栓
- 大于匹配螺母的螺栓
- 对左右两个子问题递归执行相同操作，直到所有的螺母和螺栓都匹配完毕。
动机问题3的随机化
- 两个超长字符串比对问题
- 数据传输昂贵（必须最小化通信量）
- 目标：在最小的通信成本下，判断两个字符串是否相同
随机化算法：火星和地球都进行多次哈希，从而降低哈希碰撞的概率，使用通信对比哈希结果。那么如果两个哈希值相等，但原文不等的概率就无限接近于0，虽然不能证明一定是不一样的，但是正确率99还高，所以属于有效的随机算法。
随机化算法的应用
数学领域：
- 数论：例如素性测试（Primality Test），用于判断一个数是否为质数（如 Miller-Rabin 算法）。
- 计算几何：例如图算法（Graph Algorithms），用于求解**最小割（Minimum Cut）**等问题。
- 线性代数：在**矩阵计算（Matrix Computations）**中使用随机化方法来加速计算，如随机投影方法。
计算机科学领域：
- 数据分析：例如 PageRank 算法（用于搜索引擎排名），其中使用了随机游走（Random Walks）。
- 并行计算：用于死锁规避（Deadlock Avoidance），例如随机化调度算法可以减少死锁风险。
- 优化：例如自然启发式优化（Nature-Inspired Optimization）和搜索算法（Search Algorithms），如遗传算法（Genetic Algorithm）和模拟退火（Simulated Annealing）。
- 计算生物学：例如DNA 读取比对（DNA Read Alignment），随机化方法用于高效匹配 DNA 序列。
随机化算法的优缺点
优点：
- 简单性（Simplicity）：通常实现非常简单，代码较为直观。
- 性能（Performance）：通常能够以高概率产生（接近）最优解，适用于大规模问题。
缺点：
- 存在一定概率得到错误答案（Finite Probability of Error）。
- 解决方案：多次运行算法并取多数结果，以降低错误概率。
- 运行时间和错误概率的分析较难（Difficult Analysis）。
- 难以严格分析其执行时间的期望值和错误概率，通常需要复杂的概率推导。
- 无法获得真正的随机数（Truly Random Numbers Are Impossible）。
- 计算机只能生成伪随机数（Pseudo-random Numbers），可能影响某些算法的效果（如密码学应用）。
Larry Shi