计算机基础算法与人工智能算法盘点

正是由于我在学习ai时发现一种和以往知识的割裂感才突发奇想写这篇博文计算机一般是对固定的、有限的、格式化的数据进行操作所以cs算法一般的问题就是搜索查找排序。处理这两种问题的方法复杂点的就是在某种数据结构上进行比如树、图以及更高级的树和图如B树之流而人工智能要处理是未知的甚至变动的、数据量不清楚的、类别不同的数据所以ai算法的基本问题是搜索、推理、学习。其中的学习用上了数学上的统计回归分类聚类拟合概率分布构建神经网络优化神经网络碎碎念算法本身是一个方法就是解决问题的可行操作步骤换句话说叫做“程序”但是当我学习人工智能后我有一种奇怪的感觉这里有很多我学过的计算机算法但是又不完全一样。于是几年后的今天偶然想起来写出一篇博文来总结一下。为注重可操作性每个以举例列出。数学内容不单独列出融在里面了从程序到人工智能程序的基本结构顺序执行、分支判断、循环重复。我称之为“继续”、“跳”和“次”。算法复杂度衡量空间、时间占用的指标现在你有了“加减乘除”和“三种执行结构”可以开始做这些了计算素数容易操作的数字算法排序包括了位置信息不是纯计算开始了二分查找就是搜索的方法可计算的数、无法计算的字符的串、堆栈、队列有了堆栈引入“层”的概念开始不好理解了递归然后可以开始树、图的搜索了拓扑排序图的排序深度、广度优先搜索树、图的顺序搜索方法以上常见算法策略分治、贪心、动态规划、回溯、分支限界。值函数的强化学习奖励和“训练”的引入贝叶斯网络概率模型的引入聚类距离的引入数据特征的提取张量的引入启发式算法生成式对抗式自博弈的想法开始根据这些基础建立模型了LSTMGPT……从确定到不确定的惊险一跃分支限界把搜索空间剪得干净利落动态规划把重叠子问题打包得整整齐齐——但所有这些算法都有一个前提你知道问题是什么并且答案确实存在。可现实往往是你面对一堆照片不知道哪张是猫你面对棋盘算不出十步后的胜负你面对用户的提问连正确答案的定义都不清楚。这时候继续、跳、次就不够用了。你需要引入猜和改。概率的引入从布尔值到置信度计算机算法原本是铁面无私的0就是01就是1if (x 0)绝不会模棱两可。但当数据自带噪声比如传感器误差、当观测不完整比如只能看到棋盘局部、当问题本身就有随机性比如掷骰子你必须放下非真即假的执念开始用概率说话。贝叶斯网络登场。它不是让你算出一个确定的结论而是让你在已知A发生B有多大可能发生的链条上传递信念。图结构还在节点和边但边上的权重从是/否变成了0到1之间的小数。这就像是以前的算法是法官判案有罪/无罪现在的算法是医生诊断70%概率是流感30%是感冒。距离的引入从精确匹配到相似度量排序算法比较的是大小a b字符串匹配比较的是相等strcmp 0。但相似怎么算聚类算法说把每个数据点看成空间里的一个向量算它们的距离欧几里得、曼哈顿、余弦相似度。距离近的归为一类远的分开。你突然发现分类不需要先验知识了——不需要预先知道类别标签只要知道长得像就行。这就是无监督学习的开始。从相等判断到距离度量计算机开始处理模糊性和语义比如这个词和那个词意思相近。奖励的引入从目标函数到价值反馈动态规划有最优子结构dp[i] max(dp[i-1], dp[i-2] value)。但这里的关键是value是已知的。强化学习说如果我不知道这步棋值多少分但我走完这局知道最后赢了还是输了能不能反推于是引入了值函数和奖励。不再是求解而是试错。这和贪心算法有点像都是一步一步选但贪心选眼前最大的RL选长期回报最大的 discounted future reward。为了算这个长期你迎来了时序差分学习——用现在的猜测更新过去的猜测像涟漪一样反向传播。训练的概念由此而来不再是写好算法直接跑而是要先让算法在环境里玩很多次调整参数直到行为稳定。张量的引入从标量到高维流形前面说的数、串、树、图都是结构化数据。但现实世界拍过来一张图是像素传过来一句话是声波或字符序列。你需要张量tensor标量是0阶张量向量是1阶矩阵是2阶然后还有3阶图像宽×高×通道、4阶视频批次...数据不再是一个记录而是一个多维空间中的点。特征提取feature extraction就是在这个空间里找哪些维度真正有用。CNN 看局部特征卷积核在滑窗RNN 看序列记忆隐藏状态在传递但本质上都是在张量上做可学习的变换矩阵乘法 非线性激活。生成式与启发式从搜索到创造以前的算法是找在搜索空间里找解现在的算法是生从概率分布里采样。启发式搜索比如A*用启发函数h(n)估计到目标的距离但依然是找路。生成式模型GAN、VAE、扩散模型则是造路学一个分布然后采样生成新的、不存在于训练集但看起来像的数据。自博弈Self-play把对抗嵌入训练两个网络互相对打棋力螺旋上升。这不再是人设计算法解决问题而是算法自己生成数据提高自己。AlphaZero 不依赖人类棋谱从零开始左右互搏——这是计算机算法博弈树搜索与AI深度学习的完美融合。模型即程序从写逻辑到调参数LSTM 带着门控机制遗忘门、输入门、输出门解决长程依赖本质上是可学习的记忆结构。Transformer 用自注意力Self-Attention替代循环把顺序处理变成全局关联——任意两个token的距离都是O(1)。然后 GPT 来了。它不再区分程序和数据参数就是程序推理就是执行。你Prompt它计算斐波那契数列它内部并没有执行递归或循环而是通过万亿参数间的注意力权重模拟出了计算的行为。这就像是以前你写代码教计算机怎么做现在你给例子让计算机猜该怎么做。回头再看那条脉络是连续的基础CS处理结构化、确定性、有限的问题排序、搜索、图遍历经典AI符号主义把知识编码成规则专家系统、知识图谱现代AI连接主义统计学习把知识编码成参数从数据里学出规则神经网络、强化学习你感觉到的割裂其实是从精确计算走向了近似估计从逻辑推导走向了统计推断。但底子还是那些底子递归变成了反向传播树搜索变成了策略网络队列变成了经验回放缓冲区贪心变成了带探索的epsilon-greedy。程序还是程序只是我们现在写的程序能自己改自己了。程序和人工智能的边界数学验证的必胜比如井字棋的方法算作人工智能方法吗?我感觉他更像一个计算机算法这取决于你采用哪种AI定义。这是一个经典的边界案例就像问计算器是不是计算机一样——技术上是的但直觉上好像缺少点什么。两种对立的观点观点A算这是符号主义AI的根基1960s-1980s在人工智能早期智能被定义为在符号空间中高效搜索的能力。井字棋穷举1962年实现搜索9!种状态找到不败策略深蓝Deep Blue1997年击败卡斯帕罗夫核心就是暴力搜索评估函数没有机器学习专家系统基于规则推理没有学习过程在这个定义下数学验证的必胜策略是AI的皇冠明珠——它证明了机器可以通过计算超越人类直觉。观点B不算这只是确定性算法现代主流观点当代AI尤其是深度学习时代更强调从经验中改善性能的能力Tom Mitchell的定义。井字棋穷举零经验开发者直接编码了数学真理排序算法确定性执行没有不确定性对比AlphaGo通过自我对弈学习策略网络这才是AI区分智能算法与确定性算法的四个维度维度井字棋穷举AlphaGo普通排序算法完备性数学上100%正确概率性近似100%正确可解释性透明逻辑完备黑箱神经网络透明学习能力无先验知识强从数据学习无计算资源可穷举低复杂度不可穷举启发式多项式时间关键洞察如果一个问题可以被数学穷举如井字棋、五子棋解决它的方法通常被称为完美玩法算法而非AI如果一个问题无法穷举围棋、星际争霸、兵棋必须依赖启发式/学习这就是现代AI的战场实用主义的结论井字棋必胜法 算法 AI理由无适应性它不会因为对手变强而变强不像RL agent无不确定性AI通常处理概率世界感知、决策而这是确定性数学证明无表示学习它没有理解井字棋只是遍历了状态空间但深蓝国际象棋算AI吗历史语境1997年大家叫它AI因为当时没有更好的词现代语境现在更倾向称为博弈树搜索算法以区别于AlphaZero的学习给你的兵棋项目的启示你现在的困境胜率0%恰好证明了现代AI的价值如果你能数学证明某个策略必胜比如抢占中心控制要道那就是算法不需要神经网络如果你无法证明地图太大、对手不确定必须让AI通过试错学习近似解这就是强化学习井字棋不需要神经网络因为状态空间只有9!你的兵棋需要因为状态空间是10^87。这就是为什么你的RL代码有意义——你在处理不可穷举的复杂性而这正是AI与算法的分野。经典算法罗列计算机算法 ├─ 基础算法通用核心算法 │ ├─ 排序算法 │ │ ├─ 冒泡排序重复交换相邻逆序元素简单低效 │ │ ├─ 选择排序每次选最值放到对应位置交换次数少 │ │ ├─ 插入排序将元素逐个插入已排序序列近乎有序时高效 │ │ ├─ 快速排序分治思想选基准分区递归排序实际常用 │ │ ├─ 归并排序分治合并稳定排序适合大数据 │ │ ├─ 堆排序利用二叉堆结构时间复杂度稳定 │ │ └─ 希尔排序分组插入排序优化插入排序效率 │ ├─ 查找算法 │ │ ├─ 顺序查找逐个遍历无需有序效率低 │ │ ├─ 二分查找有序数据折半查找效率高 │ │ ├─ 哈希查找通过哈希表直接定位接近O(1) │ │ └─ 二叉搜索树查找基于树结构动态查找 │ └─ 基础运算算法 │ ├─ 最大公约数GCD欧几里得算法 │ ├─ 最小公倍数LCM基于GCD计算 │ ├─ 素数判断试除法、埃氏筛法 │ └─ 进制转换二/八/十/十六进制互转 ├─ 高级算法算法设计思想 │ ├─ 递归算法 │ │ └─ 函数自身调用处理分治、树结构等问题 │ ├─ 分治算法 │ │ └─ 分解→解决→合并典型快排、归并、二分 │ ├─ 贪心算法 │ │ └─ 每步选局部最优希望得到全局最优 │ ├─ 动态规划DP │ │ └─ 拆分重叠子问题记录结果避免重复计算 │ ├─ 回溯算法 │ │ └─ 试错搜索不满足则回退典型八皇后、迷宫 │ └─ 分支限界 │ └─ 类似回溯用界限剪枝加速搜索最优解 ├─ 图算法图结构相关 │ ├─ 图遍历 │ │ ├─ 深度优先搜索DFS一路到底再回溯 │ │ └─ 广度优先搜索BFS逐层遍历找最短路径 │ ├─ 最短路径 │ │ ├─ Dijkstra单源最短路径非负权 │ │ ├─ Floyd-Warshall多源最短路径 │ │ └─ Bellman-Ford可处理负权边 │ ├─ 最小生成树 │ │ ├─ Kruskal按权选边避免环 │ │ └─ Prim从点出发逐步扩展 │ └─ 其他图算法 │ ├─ 拓扑排序有向无环图任务依赖排序 │ └─ 关键路径AOE网求工程最长耗时路径 ├─ 字符串算法 │ ├─ 朴素匹配暴力逐个匹配 │ ├─ KMP无回溯匹配效率高 │ ├─ BM从后往前匹配实际更快 │ ├─ 字典树Trie前缀树快速检索字符串 │ └─ 正则匹配模式匹配文本 ├─ 数值算法 │ ├─ 矩阵运算加、乘、求逆、行列式 │ ├─ 方程求解线性方程组、迭代法 │ ├─ 数值积分梯形法、辛普森法 │ └─ 傅里叶变换FFT信号处理核心 ├─ 机器学习/AI算法 │ ├─ 传统机器学习 │ │ ├─ 线性回归/逻辑回归 │ │ ├─ 决策树、随机森林 │ │ ├─ SVM、K近邻KNN │ │ └─ 聚类K-Means │ └─ 深度学习 │ ├─ 神经网络、CNN、RNN、Transformer │ └─ 梯度下降、反向传播 └─ 其他常用算法 ├─ 加密算法MD5、SHA、AES、RSA ├─ 压缩算法Huffman、LZ77、zip相关 ├─ 缓存算法LRU、LFU └─ 调度算法FCFS、时间片轮转、优先级调度机器学习十大算法可归纳如下1. 线性回归2. 逻辑回归3. 决策树4. 随机森林5. 支持向量机6. K均值聚类7. 朴素贝叶斯8. K近邻9. 神经网络10. 梯度提升树。这些算法涵盖了监督学习、无监督学习和深度学习的核心领域。16种优化算法梯度下降牛顿法拟牛顿法共轭梯度法遗传算法粒子群算法模拟退火支持向量机决策树随机森林蚁群算法贝叶斯优化禁忌搜索差分进化梯度提升拉格朗日乘数法。