假设你是一个城市交通管理者，要在以下两个目标中做决策: 目标 A：最小化出行时间 目标 B：最小化建设成本 什么是 Pareto 前沿 我们同时想把时间和成本都压低。 在坐标图里，越靠左下越好（左=更快，下=更省钱）。 Pareto 前
题目:请比较下列两个优化问题，说明为什么“凸性"决定了它们的可解性差异: 1.最小化 f(x)=x^2+2x+1 (凸函数)。 2.最小化 g(x)=sin(x)+0.1x (非凸函数)。 图像就是一个单口大碗。只有一个谷底， x=−1
回溯法（Backtracking） 把问题的“决策过程”当成一棵状态空间树，按深度优先往下试探：做一个选择→继续→不行就撤销（回溯）。 核心是“剪枝”：一旦发现当前部分解违反约束（不可能继续得到可行解），立刻停止扩展这条路径。 目标：通常是找可行解（一个、多个或全部），也可带最优性但以可行性剪枝为主
问题描述 对每个顶点 v，求最短距离 \delta(v)（从 s 到 v 的最小路径长度）及其前驱。 算法思想 每次把“当前估计距离最小”的未确定顶点“封口”（settle），用它去松弛邻边；由于边非负，被封口的点已经“没法再更短”了。 输入：有向图
思想：从起点到终点，始终做当下“看起来最好”的选择（局部最优），不回溯，逐步构造解。 适用前提： 贪心选择性质：存在某个最优解，它的第一步与贪心选择一致； 最优子结构：选完这一步后，余下子问题的最优解与原问题的最优解可拼接。 正确性证明常用法： 交换论证：把任意最优解通过交换步骤改造成以贪心选择开头
问题建模 把子问题定义为： c[i][j] 表示 X[1..i]与 Y[1..j] 的 LCS 长度。 再用一个标记表 b[i][j] 记录转移方向，便于回溯得到具体序列。
矩阵连乘问题 问题建模 设维度数组 P=\langle p_0,p_1,\dots,p_n\rangle ，其中A_i的尺寸为
动态规划（Dynamic Programming，DP）是一种把大问题拆成小问题、记住小问题答案、用表格或记忆化避免重复计算的方法，常用于最优值与计数类题目。 何时用 DP 存在最优子结构：整体最优由若干子问题的最优组成。 存在重叠子问题：相同子问题会被多次用到。 无后效性：状态一旦确定，不再依赖未
递归 是什么：函数（或过程）直接或间接地调用自己。 三件套： 基例（最小规模的直接答案）； 缩小规模（每次更接近基例）； 组合返回（把子结果做成父结果）。 作用：一种实现技巧/控制流，很多思路都能用递归写（DFS、树遍历、回溯、分治、带记忆化的 DP 等）。 优缺点：代码简洁、贴合问题结构；但有函数
什么是算法 算法：简单来说，算法就是通过一系列的计算步骤，用来将输入数据转换成输出结果。 算法的性质 有穷性：算法必须在有限步骤内结束，且每个步骤在合理时间内完成，避免无限循环。
发布于 2025-11-03
