DoraemonJack的博客 | DoraemonJack Blog

网格化简算法 —— 三角网格简化技术详解

从边折叠到二次误差度量，深入理解网格化简的经典方法

网格化简（Mesh Simplification）是三维几何处理中的核心问题之一，旨在减少三角网格的顶点和面片数量，同时尽可能保持原始网格的几何特征和视觉质量。该技术在实时渲染、3D打印、游戏开发、虚拟现实等领域有着广泛应用。本文深入探讨网格化简的基本原理、经典算法及其实现细节。一、问题描述与应用背景 1.1 问题定义给定一个原始三角网格 $M_0 = (V_0, F_0)$，其中...

Posted by zxh on September 17, 2025

最优化理论——拉格朗日乘子法与增广拉格朗日乘子法

从经典约束优化到现代算法的完整解析

本文深入探讨拉格朗日乘子法和增广拉格朗日乘子法的理论基础、算法推导和实际应用。从经典的等式约束优化出发，逐步介绍不等式约束、KKT条件、罚函数法、增广拉格朗日法，最终延伸到现代的ADMM算法。前置阅读： KKT条件详解（建议先掌握约束优化的基础理论）一、拉格朗日乘子法的理论基础 1.1 约束优化问题的数学表述考虑一般的约束优化问题： \[\begin{ali...

Posted by DoraemonJack on September 15, 2025

最优化理论——牛顿法和拟牛顿法

从理论推导到算法实现的完整解析

本文深入探讨牛顿法和拟牛顿法的理论基础、算法推导和实际应用。从经典的牛顿法出发，逐步介绍BFGS、DFP等拟牛顿算法，并通过详细的例题演示这些方法的计算过程和收敛特性。前置阅读：最优化方法——最速下降法与共轭梯度法（建议先掌握基本优化方法）一、牛顿法的理论基础与核心原理 1.1 基本思想与几何直观牛顿法是求解无约束优化问题的经典方法，其核心思想是利用目标函数...

Posted by DoraemonJack on September 13, 2025

最优化方法——最速下降法与共轭梯度法

迭代公式、几何直观与中等难度例题

最速下降法（Steepest Descent, SD）和共轭梯度法（Conjugate Gradient, CG）是经典的一阶迭代优化方法。SD以“最陡方向”作为下降方向，配合（一维）线搜索求步长；CG在二次型与对称正定（SPD）情形下能在至多 n 步内精确收敛，且在大规模稀疏问题中极为高效。本文给出两法的迭代公式、收敛要点与中等难度例题推导，并在末尾做对比。推荐阅读：共轭梯...

Posted by DoraemonJack on September 11, 2025

最优化基础——KKT条件

约束优化问题的核心最优性条件

KKT条件（Karush-Kuhn-Tucker条件）是约束优化理论中最重要的最优性条件之一。它提供了在约束条件下判断局部最优解的必要条件，是拉格朗日乘数法的推广。本文将从几何直观出发，深入讲解KKT条件的理论基础、几何意义和实际应用。一、KKT条件的背景 1.1 从拉格朗日乘数法到KKT条件在无约束优化问题中，我们通过梯度为零来寻找最优解： \(\nabla f(x^*) = 0...

Posted by DoraemonJack on September 10, 2025

最优化理论——基础(凸集，凸函数，共轭函数等)

从凸分析到对偶理论的数学基础

最优化理论是现代数学和工程学的重要分支，其核心建立在凸分析和对偶理论的基础之上。本文将从最基础的凸集和凸函数概念出发，逐步深入到共轭函数、拉格朗日对偶等高级理论，为读者构建完整的最优化理论基础。一、凸集理论 1.1 凸集的定义定义1.1 设 $C \subseteq \mathbb{R}^n$，如果对于任意 $x_1, x_2 \in C$ 和任意 $\lambda \in [0,...

Posted by DoraemonJack on September 8, 2025

最优化理论 —— 内点法

在可行域内部寻找最优解的经典方法

内点法（Interior Point Method）是求解约束优化问题的重要方法之一，与惩罚函数外点法不同，内点法要求搜索点始终保持在可行域内部。其基本思想是通过构造障碍函数（Barrier Function）来替代约束条件，将约束优化问题转化为无约束优化问题，同时确保迭代点始终在可行域内部。一、非线性规划模型 \[\begin{cases} \min & f(\boldsym...

Posted by DoraemonJack on September 7, 2025

数据结构——树结构

深入理解树结构的基本概念、遍历算法和实际应用

树结构：二叉树、树、二叉排序树等数据结构表示、遍历与实现树结构是计算机科学中最重要的数据结构之一，广泛应用于文件系统、数据库索引、编译器语法分析等领域。本文将深入探讨树的基本概念、二叉树的表示与遍历、二叉排序树的实现，以及相关的算法应用。 1. 树的基本概念和术语 1.1 树和森林的定义树（Tree）是由n个节点组成的有限集合，其中：有且仅有一个根节点其余节点可分...

Posted by DoraemonJack on September 6, 2025

数据结构——算法设计方法

用动态图表理解五大算法设计方法

本文通过可视化图表深入讲解五种经典算法设计技术的核心思路和执行流程。 1. 分治法 (Divide and Conquer) 核心思想将大问题分解为小问题，递归解决小问题，然后合并结果。分治法流程图流程图示例 graph LR A --- B B --> C[Happy] B --> D(Sad) graph TD A["大问...

Posted by zxh on September 5, 2025

数据结构——经典排序算法归类总结

从原理到实现，对比九种排序算法

排序算法是计算机科学中最基础也是最重要的算法之一。本文基于实际代码实现，深入分析九种经典排序算法的原理、时间复杂度、空间复杂度和稳定性，并提供详细的对比表格。一、基础排序算法 1.1 插入排序 (Insertion Sort) 算法原理：将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。 1 2 3 4 5 6 7 8 9 10 11 12 ...