导图社区 算法通识
这是一篇关于算法通识的思维导图。主要从认识算法、设计算法、算法策略、算法前沿这四个方面作了详细的阐述。
这是一篇关于图与概率的思维导图。从图论、术语、联合概率、链式法则、马氏相容、d分离、应用这几个方面作了介绍。
社区模板帮助中心，点此进入>>
论语孔子简单思维导图
《傅雷家书》思维导图
《童年》读书笔记
《茶馆》思维导图
《朝花夕拾》篇目思维导图
《昆虫记》思维导图
《安徒生童话》思维导图
《鲁滨逊漂流记》读书笔记
《这样读书就够了》读书笔记
妈妈必读：一张0-1岁孩子认知发展的精确时间表
算法通识
认识算法
本质
算法对明确性有极其严苛的要求
eg. 媒婆经验：住得近——多近算近？离家近？离工作地点近？多地间优先级……
算法通过确定性保证解决问题
模型化是算法优势的本质
eg. 网购一个保温壶，就一直推荐保温壶；搜索一个《风声》，就推荐各种谍战片
模型化：对不同的问题，用同样的方式看待，用同一套算法解决
算法没有好坏之分，背后都是人的思想
复杂度
评价算法效率的难题：用绝对时间评判效率不适用
硬件依赖
无穷大
时间复杂度
“基本操作的总数量”随着算法“输入规模”而增长的“函数关系”
eg. 盖一座10米高的金字塔，设计图纸决定了要垒10万块石头还是50万块石头： 垒石头=基本操作；10米=输入规模；图纸=垒石头总量；垒石头总量跟金字塔高度之间的函数关系就是时间复杂度
降低时间复杂度的方法
空间换时间
空间复杂度：算法占据的空间资源随着输入规模变大而增长的函数关系
牺牲一些存储空间（硬盘/内存），换来更快的搜索速度，是非常划算的
分治思想
eg. 从傅里叶变换到快速傅里叶变换，压缩音频耗时从1天到1秒
启发
效用选择模型：近似现实且保持可解性
效用：满足感
eg. 美国选民投不投票受性别、族裔、受教育程度、职业等多因素影响；影响效用的因素太多，甚至有些因素之间还有复杂的相关关系
模型太复杂就求不出解；这时必须简化模型；假设所有因素之间的关系只是线性叠加，没有复杂的交互；这叫线性效应模型
德州扑克：问题规模的减小
规模大到计算机也无法处理，就得想办法扔掉一些信息
eg. 德州扑克：把相似的状态合并
探索与利用：迭代得到结果
eg. 视频网站刚开始给你推荐各种内容，过一段时间开始推荐你最常看的内容
反思：算法只会执行，不能负责；算法出了问题，要回到人身上找答案
算法不能对问题负责
eg. 两家书店都以对方价格的倍数为自己定价，导致价格异常高
算法不能对数据负责
eg. 拿冰红茶做尿检，糖超标，怀疑糖尿病
算法不能对解释负责
eg. IBM打造沃森医疗诊断系统，算法无法提供解释
设计算法
算法蓝图
明确问题
明确目的
eg. 匹配到所有打车乘客 or 尽可能快地匹配到更多乘客
明确限制条件
eg. 市区乘客等待时间不能超过1分钟
明确评价标准
eg. 时间 or 成本 收益
建立模型
就是把现实问题转化成算法问题的过程，也是大量细节被抽象掉的过程
设计算法之前，一定要建立数学模型
模型迭代非常重要
算法选择
由达成目标水平的高低，时间复杂度决定
迭代
算法，硬件
确定假设
确定对预测结果的精度要求，舍弃不重要的细节，模糊问题明确化、量化
验证模型
用常识验证；用历史数据验证
权衡可行性
要贴近现实，也要容易求解
关系：模型与算法并非一一对应
eg. 背包问题
选择：质量与效率的权衡
eg. 投放在线广告的决定需要瞬间完成，用贪心算法；
eg. 规划保护野生动物，要尽可能找到最优解，用分支定界算法
进阶：算法工程师的更多考量
更加偏好数据敏感度低、限制条件少、对数据依赖小的算法
算法策略
迭代算法：通过循环重复某个固定操作，每一步以前一步的结果为出发点，逐步逼近答案的算法
迭代算法有效的条件：一，算法必须收敛，二，不动点必须唯一
迭代策略允许在找解的过程中有误差，而这个误差减小的速度很快，所以迭代算法的速度也很快
eg. 把芝加哥搜遍找车，很慢，这叫暴力算法
eg. 用迭代算法找车，第1步离车距离10公里，转第1次弯进入第2步迭代时距离变成1公里，再迭代一次变成100米，这个距离在迭代算法中叫“残差”
分治
分治算法：拆大为小的回溯算法；通过回溯，不断分解同样的问题，直到问题小到可以直接解决，然后再把小问题的解合并成原来问题解的算法策略
eg. 网球比赛总裁判层层分包裁判工作
回溯：嵌套循环调用自己的过程
分治算法有效的条件
能不能用：要确保问题可以分解成与原问题类似的子问题，且这些子问题之间相互独立
求解快不快
分治中的两个重要操作——分解和合并，不是免费的
eg. 碰撞检测：计算空间中100个运动的圆球哪些撞在了一起，要计算两两之间的距离，共计算4950次；把空间分成两部分独立检测，就降低到2450次。分割空间时找到适合的分割位置，需要额外的计算成本。合并时发现某些球被从中间割断，要判断有没有发生碰撞，还得额外计算，这是合并结果的成本。
如果分解问题&合并结果计算不复杂，分治策略能减小算法的复杂度
分治算法可以多CPU并行计算，而迭代算法要求每一步以前一步的结果为出发点，按步骤按顺序计算，因此不能多CPU并行计算
动态规划
解决思路：以终为始，以小建大
eg. 取糖果游戏：最后谁面对4颗糖，谁输
eg. 火箭垂直软着陆：最后位置必须离指定位置非常近，火箭与地面的角度必须非常接近90度，着陆的速度必须非常接近0
面对多步骤的决策问题时，某一步决策的最优，包含且依赖于对更小规模问题的最优策略，这就是最优子结构
eg. 取糖果游戏：最优策略应该是一开始拿两颗糖；但如果未来在面对更少糖果的时候，不遵守最优策略，那现在拿两颗糖也不会赢
动态规划的效率会受围度爆炸的影响。这时算法工程师不一定会精确求解所有的子问题，很可能只求解其中的一部分，而且是非精确求解，对另外的子问题的解，只进行一个估计
分支定界
组合优化
找到一个可行的解不难，但找到最优解，特别难
eg. 找到树上最大的苹果：剪掉苹果明显小的分枝，留下少量树枝再做比较
eg. 找一个中学里最高的学生
分支：初中/高中
定界：初中部春游山洞1.8米高，无人需弯腰——“1.8米”就是初中部这个分支的上界
剪枝：若高中部有一个1.8米以上，即可淘汰整个初中部
当某个子搜索空间能获得的目标上届，比不上某个已知的可行方案，就直接把这个子空间淘汰
如何让分支定界法高效
取决于能多有效地剪枝；如果只分支，不剪枝，就和全部算一遍没有区别
“提前停止”策略：若已求出的临时最优解离真正最优解已很近，提前停止可大大节省时间
启发式
遇到特别复杂的组合优化问题是，如果找不到最优解，可以转而使用启发式算法，找到不错的可行解
启发式算法：要么符合人类直觉认识，要么符合自然规律
蒙特卡罗
适用：可能性太多，计算不了
蒙特卡罗：对问题中的随机事件进行取样，为有限个样本进行独立计算，最后把样本结果进行统计
非常依赖于参数的正确性，对揭示问题本质没有太大帮助
算法前沿
机器学习
机器学习算法是一系列让计算机自主学习的算法，最适合用在人类无法用明确规则进行解决的问题上
机器学习学到很多人类没教过、自己也不懂的事物细节
机器学习学到的是事物之间的复杂关系
学习策略：机器学习算法是怎么学习的
K邻近算法，基于记忆，最后表达出一堆历史数据
eg. 英美法系中的判例法
决策树模型，通过数据归纳，总结出条件判断，最后表达出一些复杂的条件判断
神经网络模型，模拟神经信号的传递，以及神经对外界不同信息反应强弱不同的过程，最后表达出一系列参数的数值
