小菜鸟

贪心算法：局部最优到全局近似的智慧

贪心算法是一种通过每步选择局部最优解来寻求全局最优解的启发式算法。它不追求完美，而是在有限步骤内快速找到近似最优解，广泛应用于资源分配、路径规划等场景。本文通过经典案例解析其原理、特性及适用边界。

贪心算法的核心思想

核心原则

• 局部最优：每一步都选择当前状态下最优的选项（如价值最高、成本最低）。
• 无回溯：一旦做出选择，不再修改，直接进入下一步。
• 全局近似：通过累积局部最优解，最终得到接近全局最优的结果（未必是真正最优）。

与其他算法的区别

• 与动态规划：动态规划会保存中间结果并回溯调整，确保全局最优；贪心算法无回溯，效率更高但可能非最优。
• 与穷举法：穷举法遍历所有可能，结果最优但效率极低；贪心算法通过启发式选择减少计算量。

经典案例：背包问题中的贪心策略

问题描述

小偷的背包最大承重为 35 磅，可偷取的物品如下：

迪杰斯特拉算法（Dijkstra’s Algorithm）：带权图中的最短路径求解

迪杰斯特拉算法是一种用于带权有向图（边权重为非负数） 的最短路径算法，核心是从起点出发，逐步找到到所有其他节点的总权重最小的路径。与广度优先算法（仅适用于边权重相同的场景，如 “最少换乘”）不同，它能处理边权重不同的情况（如 “最短时间”“最少成本”），广泛应用于导航系统、网络路由等领域。

迪杰斯特拉算法的核心思想

基本原理

算法基于贪心策略：每次选择 “当前已知最短路径可达的节点”，通过该节点更新其邻居的最短路径，直到所有节点都被处理。

• 核心目标：找到从起点到其他所有节点的最短路径（总权重最小）。
• 适用条件：图中边的权重必须为非负数（若存在负权重，算法会失效，需用贝尔曼 - 福特算法）。

关键概念

• 起点：路径的起始节点（如 “出发地 A”）。
• 权重：边的 “代价”（如时间、距离、成本等，必须≥0）。
• 最短路径：从起点到某节点的所有路径中，总权重最小的路径。
• 已处理节点：已确定最短路径的节点（一旦处理，不再更新其路径）。

迪杰斯特拉算法的步骤

以 “从 A 到 G 的最短路径” 为例（图中边权重为时间，单位：分钟），算法步骤如下：

拓扑排序：处理依赖关系的有序排列算法

拓扑排序（Topological Sort）是针对有向无环图（DAG） 的一种排序算法，其核心是根据节点间的依赖关系，生成一个满足所有前置条件的线性序列。例如在任务调度中，若任务 A 依赖于任务 B，则 A 必须在 B 之后执行，拓扑排序就是生成这样的合法执行顺序。

拓扑排序的核心概念

适用场景

拓扑排序仅适用于有向无环图（DAG），因为若图中存在环（如 A 依赖 B，B 依赖 C，C 依赖 A），则无法确定执行顺序，不存在拓扑排序。

核心目标

对于图中任意一条有向边<u, v>（u 指向 v），在拓扑排序结果中，u 必须排在 v 之前。

• 例：课程安排中，“数据结构” 是 “算法” 的前置课程，则 “数据结构” 必须排在 “算法” 之前。

拓扑排序的实现算法

拓扑排序的经典实现基于广度优先搜索（BFS），核心思路是反复寻找并移除入度为 0 的节点（无前置依赖的节点），具体步骤如下：

1. 计算入度：统计每个节点的入度（指向该节点的边数）。
2. 初始化队列：将所有入度为 0 的节点加入队列（这些节点可直接执行）。
3. 处理队列：
   • 出队一个节点u，加入拓扑排序结果。
   • 遍历u的所有邻接节点v，将v的入度减 1（移除u对v的依赖）。
   • 若v的入度变为 0，将其入队。
4. 检查结果：若拓扑排序结果包含所有节点，则成功；否则图中存在环，排序失败。

代码实现（Java）

图（Graph）：复杂关系的数学模型与遍历算法

图是一种用于描述多对多关系的数据结构，由节点（顶点） 和边组成，广泛应用于地图导航、社交网络、电路设计等场景。与树的 “层次化” 结构不同，图的节点可以任意连接，能更灵活地表达现实世界中的复杂关系。

图的基本概念与分类

核心定义

• 顶点（Vertex）：图中的基本元素（如城市、用户）。
• 边（Edge）：连接两个顶点的关系（如道路、好友关系）。
• 邻接：若两个顶点之间有边相连，则互为邻接点。

图的分类

（1）按边的方向性

• 无向图：边没有方向，顶点u与v的边可表示为(u, v)，且(u, v) = (v, u)（如双向道路）。
• 有向图：边有方向，顶点u到v的边表示为<u, v>，与<v, u>不同（如单向街道、微博关注）。

（2）按边的完整性

• 完全图：
  • 无向完全图：每个顶点与其他所有顶点都有边，含n个顶点的无向完全图有n(n-1)/2条边。
  • 有向完全图：每对顶点之间有两条方向相反的边，含n个顶点的有向完全图有n(n-1)条边。

（3）其他常见类型

• 稀疏图：边数远少于完全图的图（如社交网络中用户的好友关系）。
• 稠密图：边数接近完全图的图（如电路中的节点连接）。

图的存储结构

图的存储需高效表达顶点与边的关系，常用方式有邻接矩阵和邻接表。

Spring SpEL 表达式全解析：从基础语法到实战场景

Spring 表达式语言（Spring Expression Language，简称 SpEL）是 Spring 框架提供的一种强大的表达式语言，支持在运行时解析和计算表达式，功能覆盖 “变量引用、方法调用、属性访问、逻辑运算” 等场景。它不仅可用于 XML / 注解配置中的占位符解析（如 ${user.name}），还能在代码中动态处理复杂表达式（如解析注解中的动态逻辑）。从 “核心概念→基础语法→实战场景→高级特性” 四个维度，系统讲解 SpEL 的使用方法与最佳实践。

SpEL 核心价值与应用场景

SpEL 的核心是 “在运行时动态解析表达式”，解决传统硬编码无法应对的动态逻辑问题，典型应用场景包括：

SpEL 基础：核心组件与执行流程

在使用 SpEL 前，需先理解其核心组件与执行流程，这是后续实战的基础。

核心组件

SpEL 的执行依赖三个核心组件：

执行流程