小菜鸟

K 最近邻算法（KNN）：原理、应用与实现

K 最近邻算法（K-Nearest Neighbours，KNN）是一种简单直观的监督学习算法，核心思想是 “物以类聚”—— 通过样本周围最近的 K 个邻居的信息来预测其类别或数值。它无需训练过程，属于 “惰性学习”（Lazy Learning），适用于分类和回归任务。

KNN 的核心原理

基本思想

对于未知样本，KNN 通过以下步骤进行预测：

1. 计算距离：计算未知样本与训练集中所有已知样本的距离（如欧氏距离、曼哈顿距离）。
2. 找邻居：选取距离最近的K 个样本（K 为超参数，通常为奇数，如 3、5、7）。
3. 投票 / 平均：
   • 分类任务：K 个邻居中出现次数最多的类别即为未知样本的预测类别（多数投票）。
   • 回归任务：K 个邻居的数值的平均值即为未知样本的预测值。

关键概念

• K 值选择：
  • K 过小：易受噪声影响，模型过拟合（决策边界复杂）。
  • K 过大：邻居中可能包含其他类别的样本，模型欠拟合（决策边界模糊）。
  • 通常通过交叉验证选择最优 K 值（如 3、5）。
• 距离度量：
  • 欧氏距离（最常用）：适用于连续特征，公式为 (d(x,y) = \sqrt{\sum_{i=1}^{n}(x_i - y_i)^2})。
  • 曼哈顿距离：适用于高维数据，公式为 (d(x,y) = \sum_{i=1}^{n}|x_i - y_i|)。

KNN 的分类与回归应用

分类任务（离散结果）

示例：预测鸢尾花类别（Setosa、Versicolor、Virginica）。

动态规划：从子问题到全局最优 —— 以背包问题为例

动态规划（Dynamic Programming，DP）是一种通过分解问题为重叠子问题，利用子问题的最优解逐步构建全局最优解的算法思想。它特别适合解决具有 “最优子结构” 和 “重叠子问题” 的问题，如背包问题、最长公共子序列、最短路径等。本文以经典的 0-1 背包问题为例，解析动态规划的核心原理、实现逻辑及优势。

动态规划的核心思想

核心特性

• 最优子结构：问题的最优解包含子问题的最优解。例如，“背包容量为 4 时的最大价值” 依赖于 “容量为 3 时的最大价值” 等子问题。
• 重叠子问题：不同的大问题可能包含相同的子问题，可通过存储子问题的解（“备忘录”）避免重复计算。
• 自底向上：从最小的子问题开始求解，逐步累积到原问题（与递归的 “自顶向下” 不同）。

与贪心算法的本质区别

• 贪心算法：每步选择局部最优，无回溯，可能得到近似解（如背包问题中仅选价值最高的物品）。
• 动态规划：通过枚举所有可能的子问题组合，确保得到全局最优解（如背包问题中考虑 “选或不选” 每个物品的所有情况）。

0-1 背包问题：动态规划的经典应用

问题重述

有 3 件物品和一个容量为 4 磅的背包，每件物品只能选一次（0-1 特性），求装入背包的最大价值：

动态规划解题步骤

定义状态（网格）

创建二维数组 v[i][j]，其中：

• i 表示 “前 i 件物品”（i=0 表示无物品，i=1 表示吉他，i=2 表示吉他 + 笔记本电脑，i=3 表示所有物品）。
• j 表示 “背包容量”（j=0 表示容量为 0，j=1 表示容量 1 磅，…，j=4 表示容量 4 磅）。
• v[i][j] 的值表示 “前 i 件物品在容量 j 下的最大价值”。

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

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

贪心算法的核心思想

核心原则

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

与其他算法的区别

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

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

问题描述

小偷的背包最大承重为 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）