最优化方法综述

实际上最优化问题的本质就是求极值，求目标函数/评价函数的极值，这个点运用是十分广泛的。

实际求解工具

• matlab 不推荐，优化较少

• lingo 推荐，专门的优化软件，但是有的极端题算不完

• gurobi 推荐，算得很好，而且可以直接上python

如何建立最优化问题的数学模型

（1）决策变量和参数

决策变量是由数学模型的解确定的未知数。参数表示系统的控制变量，有确定性的也有随机性的。

用人话就是找哪些是定量，哪些是未知量，哪些是目标求解的量；哪些是自变量，哪些是因变量。

（2）约束或限制条件

由于现实系统的客观物质条件限制，模型必须包括把决策变量限制在它们可行值之内的约束条件，而这通常是用约束的数学函数形式来表示的。

换句话讲就是寻找约束条件，并且将其用数学语言描述出来。

（3）目标函数

这是作为系统决策变量的一个数学函数来衡量系统的效率，即系统追求的目标。

最优化数学模型分类

根据目标函数和约束条件的性质，最优化模型可以分为多种类型。不同的类型特征鲜明，求解的思路和难度也大相径庭。

1. 线性规划 (Linear Programming, LP)

• 特征： 这是最基础、最经典的一类优化模型。它的核心特征是“线性”，具体说就是：

  1. 目标函数是线性的：比如求 \(max Z = 2x + 3y\)。

  2. 所有约束条件也都是线性的：比如 \(x + y <= 10\)，\(x - y >= 0\) 等。

  3. 决策变量 x, y 是连续的，可以取小数。

• 思路：

  • 几何直观：所有线性约束在坐标系里画出来，会围成一个多边形（二维）或多面体（高维），这叫“可行域”。理论已经证明，最优解一定在这个多边形的某个顶点上取到。

  • 核心算法：单纯形法 (Simplex Method)。这个方法非常巧妙，它从可行域的一个顶点开始，沿着边走到一个更好的顶点，一步步迭代，直到找到最优的顶点，效率很高。现在大规模的线性规划问题通常用内点法 (Interior Point Method) 求解。

但是我怎么感觉这类的话，最多出个第一小问呢，感觉用处不大。

2. 整数规划 (Integer Programming, IP)

• 特征： 它是在线性规划的基础上，增加了一个或多个决策变量必须是整数的约束。

  • 如果所有决策变量都必须是整数，称为纯整数规划 (Pure IP)。

  • 如果部分决策变量需要是整数，另一部分可以是连续的，称为混合整数线性规划 (Mixed-Integer Linear Programming, MILP)。

  • 最特殊的一种是 0-1 整数规划，决策变量只能取 0 或 1，常用于表示“是/否”、“选/不选”这类决策。

• 思路：

  • 千万不要以为四舍五入就行！对线性规划的结果取整，很可能得到一个不可行或者很差的解。

  • 整数规划的求解难度比线性规划高得多，属于NP-hard问题。

  • 核心算法：分支定界法 (Branch and Bound) 和 割平面法 (Cutting Plane Method)。分支定界法可以理解为一种“聪明的穷举”，它不断地把问题分解成小问题（分支），并利用线性规划的解来判断哪些分支可以提前放弃（定界），从而避免了无谓的搜索。

3. 非线性规划 (Nonlinear Programming, NLP)

当目标函数或约束条件中，只要有一个不是线性的，就进入了非线性规划的范畴。它的世界比线性规划复杂得多。

3.1 无约束非线性规划

• 特征： 目标函数是非线性的，但没有任何约束条件。用人话讲，就是在整个定义域里自由地寻找函数的最高点或最低点。

• 思路：

  • 这就是微积分大显身手的地方。对于可导函数，我们寻找梯度 (Gradient) 为零的点，即 ∇f(x) = 0 的点，这些是可能的极值点（驻点）。

  • 核心算法：各种迭代下降算法。从一个初始点开始，每一步都朝着能让函数值减小（或增大）最快的方向走一小步，不断逼近最优点。经典算法包括：

    • 梯度下降法 (Gradient Descent)：最简单，就是沿着梯度的反方向走。

    • 牛顿法 (Newton's Method)：考虑了二阶导数（Hessian矩阵），收敛更快，但计算量更大。

    • 共轭梯度法 (Conjugate Gradient Method) 等。

3.2 约束非线性规划

• 特征： 目标函数和/或约束条件中至少有一个是非线性的，并且存在约束条件。这是现实世界中最常见也最复杂的一类问题。

• 思路：

  • 处理约束是关键。你提到的拉格朗日乘数法就是处理等式约束的经典理论基础，它的思想是把一个有约束的问题，转化为一个更大的无约束问题（构造拉格朗日函数）来求解。

  • 对于不等式约束，则需要用到更复杂的 KKT (Karush-Kuhn-Tucker) 条件，它是拉格朗日乘数法的推广。

  • 核心算法：求解方法非常多样，比如序列二次规划 (Sequential Quadratic Programming, SQP)、内点法 (Interior Point Method)、罚函数法 (Penalty Method) 等。这些算法通常都非常复杂，依赖于成熟的优化求解器。

4. 二次规划 (Quadratic Programming, QP)

• 特征： 这是非线性规划中一个特别且重要的小类。它的目标函数是二次函数，而所有约束条件依然是线性的。

• 思路： 因为它的结构比较“良善”（目标函数是二次的，约束是线性的），所以有比一般非线性规划更高效的特定算法，例如有效集法 (Active Set Method)。它在金融（如投资组合优化）、机器学习（如支持向量机SVM）等领域有广泛应用。

5. 动态规划 (Dynamic Programming, DP)

• 特征： 严格来说它是一种求解问题的思想，但常用于解决一类多阶段决策的最优化问题。这类问题的决策过程可以分解成一系列相互关联的阶段，前一个阶段的决策会影响后一个阶段的状态。

• 思路：

  • 核心思想：最优子结构 和 重叠子问题。它不是一次性做出所有决策，而是从后往前（或从前向后）分阶段求解。首先解决最后一个阶段的最优决策，然后带着这个信息，去求解倒数第二个阶段……直到回到起点。

  • 通过记录和复用子问题的解（通常用一个表格），避免了重复计算，大大提高了效率。背包问题、最短路径问题都是动态规划的经典应用。

6. 组合优化 (Combinatorial Optimization)

• 特征： 就是找各种组合的最优方案，比如分配土地使用策略（24年C题）。这不是一种具体的问题，而是一大类问题。它的核心特征是决策变量是离散的，并且可行解的数量是有限的（但通常是天文数字）。它要解决的问题不是在一条连续的曲线上找最低点，而是在众多可能性中“组合”出一个最佳方案。

  • 用人话讲，就是做“选择题”或“排序题”。比如：从100个项目中选出10个进行投资，怎么选才能收益最大？（选择）或者，安排一个生产车间里10个工序的加工顺序，怎么排才能总时间最短？（排序）

  • 上面讲到的整数规划，以及下面要讲的选址问题、TSP问题，都属于组合优化的范畴。

• 思路： 组合优化问题的求解思路五花八门，取决于问题的具体结构和难度。

  • 精确算法 (Exact Algorithms)：目标是找到绝对的最优解。

    • 对于一些“简单”的问题（比如求图的最小生成树），有多项式时间算法（见下文）可以快速求解。

    • 对于大部分“困难”的问题（即NP-hard问题），精确算法（如动态规划、分支定界法）的计算时间会随着问题规模的增长而爆炸，只适用于小规模情况。

  • 近似算法 (Approximation Algorithms)：退而求其次，不去寻找“最好”的解，而是寻找一个“足够好”的解。这类算法速度快，并且能从理论上保证它给出的解与最优解的差距不会超过一个特定的比例。

  • 启发式算法 (Heuristics/Metaheuristics)：当问题规模太大，精确算法跑不动，又没有好的近似算法时，就轮到启发式算法登场了。它们是一些基于直觉或经验的“聪明”搜索策略，比如模拟退火、遗传算法、蚁群算法等。它们通常能快速找到一个不错的解，但不能保证这个解有多好，有可能陷入局部最优。在工程实践中应用极为广泛。

6.1 选址问题 (Facility Location Problem)

• 特征： 这是组合优化中一类非常经典的问题。它的典型场景是：有一批潜在的设施点（比如仓库、基站、超市）和一批客户点，目标是决定在哪里建设施、建多少个，以及每个客户由哪个设施来服务，从而在满足所有客户需求的前提下，使得总成本（如建设成本+运输成本）最低。

• 思路：

  • 选址问题通常被建模为混合整数线性规划 (MILP)。

  • 其中，是否在某个地点建设施，可以用一个0-1整数变量来表示（1代表建，0代表不建）。

  • 而每个客户点由哪个设施来服务，可以用另外的变量来表示。

  • 模型建好后，就可以调用成熟的优化求解器（如 Gurobi, CPLEX）来求解。对于大规模问题，同样需要设计专门的近似算法或启发式算法。

6.2 TSP (旅行商问题, Traveling Salesperson Problem)

• 特征： 这是组合优化里最著名、最典型的“明星问题”。

  • 问题描述：一个旅行商人要拜访 n 个城市，他必须从一个城市出发，访问每一个城市恰好一次，最后再回到出发的城市。问题是：他应该按照什么样的顺序访问这些城市，才能使得总的旅行路程最短？

  • 用人话讲，就是“一笔画”走遍所有点，怎么走路线最短。TSP是NP-hard问题的杰出代表，意味着当城市数量稍微多一点（比如几十个），想要靠暴力枚举所有路径来找到最优解就已是天方夜谭。

• 思路：

  • 精确算法：对于城市数量较少（例如20个以内）的情况，可以使用动态规划（如Held-Karp算法） 或 分支定界法 求得最优解。

  • 近似与启发式算法：对于大规模的TSP问题，几乎总是使用这两类算法。

    • 近似算法：例如Christofides算法，可以保证找到的路径长度不会超过最优路径的1.5倍。

    • 启发式算法：比如“贪心”策略（每次都走向最近的未访问过的城市）、2-opt/3-opt（随机交换路径中的2条或3条边，看是否能改进路线），以及更高级的遗传算法、模拟退火等，都能在合理的时间内找到非常接近最优解的路径。

---

接下来这两个概念是串联起来的，它们更多地是关于“算法效率”的分类，而不是“优化模型”的分类，但对于理解一个优化问题能否“解决”至关重要。

7. 多项式时间算法 (Polynomial-Time Algorithm) & P问题

• 特征： 一个算法的运行时间（或计算步骤数）上界，可以表示为问题输入规模 n 的一个多项式函数，即 \(O(n^k)\)，其中 k 是一个常数。

  • 用人话讲，就是这个算法很高效。当问题规模 n 变大时，它的计算时间增长得比较“温和”，不会失控。比如 \(O(n^2)\), \(O(n^3)\) 都是多项式时间。相比之下，指数时间 \(O(2^n)\) 增长得就非常恐怖。

  • 所有可以由多项式时间算法解决的判定问题（回答是/否的问题），构成了一个集合，称为P类问题 (Polynomial time)。P问题通常被认为是“可以有效解决的”或“计算上易解的”问题。

  • 注意：线性规划就是一个P问题（虽然单纯形法在最坏情况下是指数时间，但内点法是多项式时间的）。

8. 非确定性多项式 (Nondeterministic Polynomial) & NP问题

• 特征： 这个名字听起来很玄乎，但核心思想不复杂。它描述的是这样一类判定问题：

  1. 直接找到它的解可能非常困难（目前不知道有没有多项式时间算法）。

  2. 但是，如果有人给了你一个声称是解的答案，你可以在多项式时间内验证这个答案对不对。

  • 用人话讲：“解答”难，但“验算”容易。

  • 这类问题的集合，就叫NP类问题 (Nondeterministic Polynomial time)。

• 举例： TSP的判定版本：“是否存在一条长度小于L的旅行路线？”

  • 解答难：让你直接找出这条路来，非常困难。

  • 验算容易：如果我给你画出一条具体的路线，你只需要把路径上的各段距离加起来，看看总和是不是小于L。这个加法运算是非常快的（多项式时间）。

  • 因此，TSP属于NP问题。

• 重要关系：

  • 所有P问题都是NP问题（因为如果我能快速解答，自然也能快速验算）。

  • 但NP问题是不是都是P问题？即，P = NP? 这就是计算机科学领域最核心的百万美元大奖难题。目前普遍认为 P ≠ NP，也就是说，存在一大批“只能快速验算，不能快速解答”的难题。

  • 在NP问题中，最难的一批问题被称为NP完全问题 (NP-Complete)。TSP就是一个NP完全问题。如果我们能为任何一个NP完全问题找到多项式时间解法，那么所有的NP问题都能迎刃而解。

  • 而那些比NP完全问题“至少一样难”的优化问题（不仅仅是判定问题），就被称为NP-hard问题。

最优化方法

微积分中的最优化方法

首先要讲的是一元二元三元函数导数为零取极值的东西，在这里就不细讲。

然后是拉格朗日数乘法求解附加有条件的极值，这个在写一遍：

要找函数 \(z= f(x,y)\) 在条件 \(\phi(x,y)=0\) 下的可能极值点，先构造函数 \(F(x,y)=f(x,y)+\lambda \phi(x,y)\) ，其中 \(\lambda\) 为某一常数;

可由

\[ \begin{cases} f_x(x, y) + \lambda \varphi_x(x, y) = 0, \\ f_y(x, y) + \lambda \varphi_y(x, y) = 0, \\ \varphi(x, y) = 0. \end{cases} \]

解出 \(x,y,\lambda\) ，其中 \(x,y\) 就是可能的极值点的坐标.

启发式算法 (Heuristics)

一个基于直观或经验构造的算法，在可接受的花费(指计算时间、占用空间等)下给出待解决组合优化问题每一个实例的一个可行解，该可行解与最优解的偏离程度不一定事先可以预计.

用人话讲，启发式算法就是一套“经验法则”或“捷径”。当一个问题太复杂，我们找不到完美的“最优解”，或者找最优解太花时间，启发式算法就能帮我们快速找到一个“还不错的”、“八九不离十”的解。它追求的是效率和实用性，牺牲了一定的最优性保证。

算法解释

1. 贪心算法 (Greedy Algorithm)

• 概念： 一种只顾眼前的算法。它在做决策时，总是做出当前看起来最好的选择，而不去考虑这个选择对未来的影响。它希望通过每一步的局部最优，最终能达到全局最优。 这个算法总是想要获取局部最优解。对于某些特定布局的情况，这个策略确实是最好的。但对于大多数复杂布局，这种“短视”会导致它错过全局最优的路线，甚至绕个大圈。

• 应用场景： 虽然贪心算法不总是对的，但在某些问题上（如求最小生成树的Prim和Kruskal算法、求单源最短路径的Dijkstra算法）它却能奇迹般地得到最优解。

2. 邻域搜索算法 (Neighborhood Search) 或 爬山算法 (Hill Climbing)

• 找局部最优->移动到局部最优->重新找局部最优。直到周围再也找不到更好的解为止。

• 思路比喻（来自gemini2.5pro）： 想象你在一个浓雾弥漫的山脉里，想找到最高的山峰。你被随机空投到一个位置，你唯一能做的就是环顾四周，朝着脚下能迈出的、坡度最陡峭的向上方向走一步。你不断地重复这个过程，一步步“爬山”。最终，你会到达一个山顶，因为你再往任何方向走都是下坡路了。

• 核心缺陷： 容易落入局部最优解就停止寻找全局最优解。

3. 模拟退火算法 (Simulated Annealing, SA)

• 为了克服爬山算法容易陷入局部最优的缺陷，模拟退火算法被设计了出来。它在邻域搜索的基础上，引入了“随机性”和“概率性”的跳出机制。

• 思路比喻： 这个过程模拟了金属冶炼中“退火”的过程：先高温融化，再缓慢冷却，让内部分子找到能量最低的稳定结构。还是那个浓雾里爬山的例子。这次你不是一个稳健的登山者，而是一个“喝了酒的登山者”。在刚开始（温度高）的时候，你处于微醺状态，精力旺盛，大部分时间会往高处走，但偶尔也会晃晃悠悠地往山下走几步。这种“犯糊涂”的行为，恰好给了你一个机会，能够走出那个小山丘的范围，去探索远处的其他山峰。随着时间推移（温度降低），你的酒劲儿慢慢过去，变得越来越清醒和稳健，最终只选择向上走，直到找到一个你认为最高的山峰。

4. 遗传算法 (Genetic Algorithm, GA)

• 一种模仿生物界“物竞天择，适者生存”进化规律的算法。它不是只维护一个解，而是一次性维护一大群解（称为“种群”），然后让这个种群通过一代代的“繁衍”和“淘汰”来进化，最终整个种群的质量都会越来越高，从而找到问题的优秀解。

• 把它想象成一个“育种农场”：

  1. 初始种群： 你随机培育出第一批各种各样的种子（初始解）。

  2. 适应度评估： 把这些种子种下去，看哪个长得最好（哪个解更优）。

  3. 选择： 优先选择那些长得好的种子作为下一代的“父母”。

  4. 交叉/繁殖： 让这些优秀的“父母”互相杂交，产生“后代”。后代会继承父母双方的优良基因（解的优秀特征）。

  5. 变异： 在繁殖过程中，允许有极小的概率发生基因突变，给种群带来新的多样性，防止所有种子都长得一样。 经过成千上万代的“优胜劣汰”和“繁衍进化”，你的农场里最终会培育出超级品种。

长处

简单易行；比较直观；易被使用者接受。

速度快，在实时管理中非常重要。

多数情况下，程序简单，因此易于修改。

短处

不能保证求得最优解。

表现不稳定。启发式算法在同一问题的不同实例计算中会有不同的效果，有些解好，而有些则很差，在实际应用中，这种不稳定性造成计算结果不可信。

算法的好坏依赖于实际问题、经验和设计者的技术，这一点很难总结规律，同时使不同算法之间难以比较。

现代优化算法 (Metaheuristics)

当问题变得极其复杂时，传统的启发式算法（如贪心、爬山）可能会显得力不从心。现代优化算法，通常也称为元启发式算法 (Metaheuristics)，提供了一套更高层次的、用于指导和改进底层启发式搜索过程的策略框架。它们通常受到自然现象的启发，更加强大和智能。

1. 禁忌搜索 (Tabu Search)

• 它是对“爬山算法”的一个极佳的改进。爬山算法最大的问题是容易被“小山丘”（局部最优解）困住，而禁忌搜索的核心思想就是要有“记忆力”，能帮助搜索过程跳出这个陷阱。

• 再次回到那个浓雾里爬山的例子。爬山算法让你停在第一个找到的山顶。而禁忌搜索的登山者会带一个“禁忌列表”（Tabu List），就像一本小黑本。

  1. 当你从一个位置 A 移动到更好的位置 B 时，你会在小黑本上记下：“刚刚从 A 走过来，短期内禁止再走回 A”。

  2. 这样一来，即使 B 所在的这个小山丘的周围都是下坡路，你因为被禁止走回头路，就被迫去探索其他的、以前没走过的下坡路。

  3. 这一个“被迫”的操作，就给了你一个机会，让你能够先下山，再从另一侧登上旁边那座可能更高的山峰。

  通过这种“记住走过的路，短期内不走回头路”的机制，禁忌搜索大大增强了跳出局部最优的能力。

2. 人工神经网络 (Artificial Neural Networks, ANN)

• 它本身不是一个直接求解优化问题的算法，而是一种模仿人脑神经元连接方式的计算模型。但在优化领域，它扮演着两个关键角色。

• 角色一：它本身就是一个巨大的优化问题。

  • 他本身就是一个巨大的优化问题，现在ai领域的各种涨点比赛就是为了进一步优化他。

• 角色二：它可以作为优化问题的辅助工具。

  • 当一个优化问题的目标函数或约束条件复杂到无法写出数学表达式时（比如预测一个化工过程的产率），我们可以先训练一个神经网络来学习输入（原料配比）和输出（产率）之间的关系。然后，这个训练好的神经网络就成了一个“代理模型”，我们转而去优化这个神经网络的输入，以获得最高的预测产率。

3. 蚁群优化算法 (Ant Colony Optimization, ACO)

• 这是什么： 一种模拟真实蚂蚁群体寻找食物过程的算法，特别擅长解决在图上寻找最优路径一类的问题（比如旅行商问题 TSP）。

• 思路比喻： 这个比喻非常直观，因为它就是算法的来源。

  1. 初始探索： 蚁巢和食物之间有多条路径，一开始，蚂蚁们会随机地向各个方向探索。

  2. 信息素释放： 蚂蚁在走过的路上会留下一种叫“信息素”的化学物质。

  3. 正反馈循环： 假设有A、B两条路，A路比B路短。走A路的蚂蚁，会更快地往返于蚁巢和食物之间。因此，在相同时间内，A路上的蚂蚁往返次数更多，留下的信息素浓度也就会越来越高。

  4. 路径选择： 后续出发的蚂蚁闻到信息素，更倾向于选择浓度高的路径。这就导致越来越多的蚂蚁被吸引到A路上去，A路的信息素进一步增强。

  5. 收敛： 经过这样一个正反馈过程，整个蚁群很快就能共同“发现”并锁定那条最短的路径。算法中的“虚拟蚂蚁”就是通过模拟这个过程来构造出问题的优良解。

图论 (Graph Theory)

在优化领域，很多问题都可以抽象成一个图。比如，城市交通网络、社交关系网、任务依赖关系等。图论就是研究这些“点”和“线”组成的结构的数学分支。

基础知识

首先，我们要明确，这里的“图”不是指柱状图、饼状图，而是指由顶点 (Vertex) 和连接顶点的边 (Edge) 组成的数学对象。

• 无向图 (Undirected Graph)

  • 定义： 图中的边是没有方向的。如果顶点 A 和顶点 B 之间有一条边，那么你可以从 A 到 B，也可以从 B 到 A。

  • 就是“双向关系”。比如微信好友关系，你是我的好友，我必然也是你的好友。连接你我的那条线不带箭头。

• 有向图 (Directed Graph)

  • 定义： 图中的边是有方向的，用箭头表示。如果有一条从 A 指向 B 的边，意味着你可以从 A 到 B，但不能从 B 到 A（除非还有一条反向的边）。

  • 就是“单向关系”。比如微博的“关注”，我关注了你，但你不一定关注我。连接我俩的线必须带个箭头，表明关系的方向。城市里的单行道网络也是一个典型的有向图。

• 无向赋权图 (Undirected Weighted Graph)

  • 定义： 在无向图的基础上，给每一条边都赋予一个数值，称为“权重”或“成本”。

  • 不仅关系是双向的，而且这个关系还有个“度量”。比如一张城市地图，城市是顶点，连接城市的道路是边。道路是双向通行的（无向），每条道路的长度（公里数）就是它的权重。

• 有向赋权图 (Directed Weighted Graph)

  • 定义： 在有向图的基础上，给每一条带方向的边赋予一个权重。

  • 关系是单向的，并且这个单向关系有度量。比如一张机票价格图，城市是顶点，从 A 飞往 B 的航班是一条有向边，这张机票的价格就是权重。注意，从 A 到 B 的票价和从 B 到 A 的票价通常是不同的。

• 邻接矩阵 (Adjacency Matrix)

  • 定义： 一种用矩阵来表示图的方法。对于一个有 n 个顶点的图，我们可以创建一个 n x n 的矩阵。矩阵的第 i 行第 j 列的元素 A[i][j] 表示顶点 i 和顶点 j 之间的连接关系。

  • 就是一张“连接关系表”。

    • 对于无权图：如果顶点 i 和 j 之间有边，那么 A[i][j] = 1，否则为 0。

    • 对于赋权图：如果顶点 i 和 j 之间有边，那么 A[i][j] 就等于这条边的权重，否则可以是一个特殊值（比如无穷大 ∞）。

  • 这个矩阵非常直观，但如果图很“稀疏”（边很少），用矩阵存储会浪费大量空间。

最短路径 (Shortest Path)

• 在一个赋权图（有向或无向）中，找到从一个起始顶点到一个目标顶点，所经过的边的权重之和最小的那条路径。这个“权重”可以是距离、时间、成本、或者任何可以累加的度量。就是导航。

• 核心算法与分类：

  • 单源最短路径 (Single-Source Shortest Path - SSSP): 计算从一个固定的起点（源点）到图中所有其他顶点的最短路径。

    • Dijkstra算法 (迪杰斯特拉算法): 最经典的SSSP算法。它的策略是贪心算法。

      • 思路： 想象你在起点，手上有一个“已确定最短路径”的区域，初始时只有你自己。算法每次都从这个区域的边缘向外“扩张”，选择一个离起点最近的、尚未被纳入区域的顶点，将它纳入，并更新它所有邻居到起点的距离。这个过程就像水波纹一样，从起点开始，一圈圈地蔓延，直到覆盖所有你想去的顶点。

      • 重要限制： Dijkstra算法非常高效，但它有一个致命弱点——不能处理带有负权重边的图。因为它的贪心策略一旦将一个点纳入“已确定”区域，就不会再回头看它，而负权边可能会让这个“确定”变得不确定。

    • Bellman-Ford算法 (贝尔曼-福特算法): 更强大的SSSP算法，可以处理带有负权重边的情况。

      • 思路： 它不搞贪心，而是采用一种“暴力”的迭代松弛策略。它对图中的每一条边，都反复进行“松弛”操作（检查并更新通过这条边能否让终点离源点更近），这个过程会重复 V-1 遍（V是顶点数量）。它的思想是，一条最短路径最多包含 V-1 条边，所以经过 V-1 轮迭代，一定能把最短路径的距离传递到终点。

      • 额外功能： Bellman-Ford算法还有一个独门绝技——可以检测图中是否存在负权环。如果在 V-1 轮迭代后，还能继续松弛某条边，那就说明图里存在一个“越走权重越小”的怪圈，这种情况下最短路径没有意义（可以无限刷分）。

  • 所有顶点对之间的最短路径 (All-Pairs Shortest Path - APSP): 计算图中任意两个顶点之间的最短路径。

    • Floyd-Warshall算法 (弗洛伊德算法): 解决APSP问题的经典算法，思想是动态规划。

      • 思路： 它的思考方式非常巧妙。它问自己一个问题：“从顶点 i 到顶点 j，如果只允许经过顶点1作为中转站，最短路径是多少？”，“如果允许经过顶点1和2作为中转站，最短路径又是多少？”……它通过迭代，不断地增加“允许被用作中转站”的顶点，来更新任意两点 i 和 j 之间的最短距离。当所有顶点都被考虑为中转站后，就得到了最终所有点对之间的最短路径。它的代码实现极其简洁优美。

行遍性问题 (Traversability Problem)

• 探讨如何不重复地走遍一个图的所有边或所有顶点。它不关心路径的“长短”，只关心“能不能走完”以及“怎么走”。就是“一笔画”

• 两个经典问题：

  • 欧拉路径/回路 (Eulerian Path/Circuit):

    • 问题： 能不能找到一条路径，恰好走过图中的每一条边一次？如果这条路径的起点和终点是同一个点，就称为欧拉回路；如果起点和终点不同，就称为欧拉路径。

    • 怎么判断： 这个问题有非常简单明确的判定方法，这要归功于大数学家欧拉。关键在于看每个顶点的度 (Degree)，也就是连接这个顶点的边的数量。

      • 对于无向图：

        • 如果所有顶点的度都是偶数，那么一定存在欧拉回路（可以从任意点出发，最终回到该点）。

        • 如果恰好有两个顶点的度是奇数，那么存在欧拉路径（必须从一个奇数度顶点出发，在另一个奇数度顶点结束）。

        • 其他情况（奇数度顶点超过2个），则不存在一笔画走完所有边的路径。

    • 现实应用： 城市扫雪车或邮递员的路线规划。目标是走遍每一条街道，且总路程最短（即不走重复路），这就是一个典型的欧拉回路问题。

  • 哈密顿路径/回路 (Hamiltonian Path/Circuit):

    • 问题： 能不能找到一条路径，恰好经过图中的每一个顶点一次？如果这条路径的起点和终点是同一个点，就称为哈密顿回路。

    • 怎么判断： 这个问题和欧拉问题看起来很像，但难度却是天壤之别。哈密顿问题是著名的NP完全问题，目前没有任何简单的、通用的判定法则。我们无法像检查顶点的度那样，快速判断一个图是否存在哈密顿路径。

    • 现实应用： 我们前面提过的旅行商问题 (TSP)，其实就是在一个赋权完全图中寻找权重最小的哈密顿回路。因为旅行商要求访问每个城市（顶点）恰好一次，并最终返回起点。