1. 问题求解概述

1. 问题求解 (Problem Solving) 是人工智能 (Artificial Intelligence, AI) 的一个分支。

2. 提出这个分支的原因是：

   • 人类的能力是有限的。

   • 有许多复杂问题，人类难以甚至无法解决。

3. 解决这些问题的方法是：

   • 通过计算机来求解。

   • 求解问题的方法是设计算法。

核心总结： 问题求解是AI的一个领域，旨在利用计算机通过设计算法的方式，去解决人类能力有限而无法处理的复杂问题。

装箱问题

问题描述的总结：

• 已知条件：

  • 有 $N$ 个物品，每个物品有一个重量（重量小于箱子容量 $S$）。

  • 有一组箱子，每个箱子的容量都是 $S$。

• 目标：

  • 寻找一种方法，用最少数量的箱子，将所有 $N$ 个物品全部装完。

示例解析：

• 箱子容量 $S=10$。

• 10 个物品的重量： $2,3,5,3,6,8,9,2,1,5$。

• 目标： 求最少的箱子数。

图片给出的装箱示例（这不是唯一解，但它展示了一种装箱方式）：

• 箱子 1： 装 $2,3,5$ (总重 $2+3+5=10$)

• 箱子 2： 装 $3,6,1$ (总重 $3+6+1=10$)

• 箱子 3： 装 $8,2$ (总重 $8+2=10$)

• 箱子 4： 装 $9$ (总重 $9$)

• 箱子 5： 装 $5$ (总重 $5$)

在这个示例中，一共用了 5 个箱子。

这个装箱问题是一个著名的 NP-hard 问题，意味着在实际应用中，很难在合理的时间内找到绝对最优解（即最少的箱子数）。因此，通常会采用各种启发式算法 (Heuristic Algorithms) 来寻找接近最优解的装箱方案，例如：

• 首次适应法 (First Fit, FF)

• 首次适应递减法 (First Fit Decreasing, FFD)

• 最佳适应法 (Best Fit, BF)

• 等等。

倒水量水问题

问题描述的总结：

• 已知条件：

  • 两个没有刻度的水壶，容量分别为 $x$ 升和 $y$ 升。

  • 一个目标水量 $z$ 升。

• 目标：

  • 找到一系列倒水操作步骤，使得：

    • 最终其中一个水壶中的水量恰好为 $z$ 升；

    • 或者两个水壶中的水量之和为 $z$ 升。

示例解析：

• 已知： 水壶 A 容量 $x=3$ 升，水壶 B 容量 $y=5$ 升。

• 目标： 测量出 $z=4$ 升的水。

倒水操作的规则（允许的操作）：

1. 将任何一个水壶装满水。

2. 将任何一个水壶的水倒空。

3. 将一个水壶的水倒入另一个水壶，直到：

   • 倒出的水壶空了；

   • 或 接收的水壶满了。

求解 3 升和 5 升水壶测量出 4 升水的步骤（其中一种解法）：

步骤	A 壶 (3 升)	B 壶 (5 升)	操作说明
1	3	0	灌满 A 壶 (A $\leftarrow$ 3)
2	0	3	将 A 壶的水倒入 B 壶 (B $\leftarrow$ 3)
3	3	3	灌满 A 壶 (A $\leftarrow$ 3)
4	1	5	将 A 壶的水倒入 B 壶直到 B 壶满。B 壶接收 $5-3=2$ 升，A 壶剩下 $3-2=1$ 升。
5	1	0	倒空 B 壶 (B $\leftarrow$ 0)
6	0	1	将 A 壶的水倒入 B 壶 (B $\leftarrow$ 1)
7	3	1	灌满 A 壶 (A $\leftarrow$ 3)
8	0	4	将 A 壶的水倒入 B 壶直到 B 壶满。B 壶接收 $5-1=4$ 升，B 壶中的水量恰好为 4 升。

这个倒水问题是一个典型的状态空间搜索 (State-Space Search) 问题，可以用广度优先搜索 (BFS) 或深度优先搜索 (DFS) 等方法来求解。

一般问题及求解

1. 核心思想

问题求解的核心就是寻找解决方案并实现算法设计。

2. 获取（设计）算法的四种主要方法

图片列举了四种经典的算法设计策略，它们是解决许多复杂问题的通用思路：

1. 贪心法 (Greedy Method)

2. 分治法 (Divide and Conquer)

3. 回溯法 (Backtracking)

4. 动态规划 (Dynamic Programming)

3. 从问题到程序的过程（流程图）

流程图描述了将一个现实问题转化为可执行程序的完整步骤：

1. 问题 (Problem)： 待解决的原始任务。

2. 算法 (Algorithm)：

   • 作用： 解决“问题”。

   • 输入： 解决问题的思想方法，通常是步骤描述（即如何一步步解决）。

3. 程序 (Program)：

   • 作用： 实现“算法”。

   • 输入： 用某种语言表达的算法过程，通常是指令集合（即可执行代码）。

4. 反馈/循环：

   • 程序的执行结果和数据表示（例如：输入和输出数据）会反馈到对问题的理解和求解过程中。

总结来说，整个过程是：

问题 $\to$ (设计思想/步骤) $\to$ 算法 $\to$ (逻辑描述/指令集) $\to$ 程序

而设计算法的主要思想包括贪心、分治、回溯和动态规划。

1. 贪心法

1. 基本思想

• 从小方案推广到大的解决方案。

• 分阶段工作： 在每一步（或每一个阶段）都做出当前看来最好的选择，而不考虑该选择对之后结果的影响（即“鼠目寸光”）。

2. 核心特性

贪心法做出的每一个选择必须具备三个特性：

1. 可行性： 每一步的选择必须满足问题的约束条件。

2. 局部最优： 必须是当前所有可行方案中的最优解。

3. 不可撤销性： 选择一旦做出，在算法的其后步骤中不能被撤销或改变。

3. 应用

• 贪心法主要用于求解最优问题。

• 它已发展成一种通用的算法设计技术。

4. 优缺点

方面	优点 (Advantages)	缺点 (Disadvantages)
最优性	一旦被证明是正确的，具有很大的执行效率和速度优势。	不能确定最终解是最优的，也不能用于求解最大或最小问题。
效率	算法效率上，贪心法快速。	往往是不正确的（即不能得出全局最优解）。
资源	程序实现所需的内存开销较小。	-

总结：

贪心法是一种快速、节省资源的算法设计策略，它通过在每一步都做出局部最优且不可撤销的选择来尝试解决最优问题。然而，它的主要缺陷是它不保证能找到问题的全局最优解，只有在特定问题上被数学证明正确时，它才是一种高效的算法。

贪心法-举例-找零钱问题

1. 问题描述

• 硬币面额（假设）： 1 分、2 分、5 分、1 角、2 角、5 角、1 元（中国大陆的硬币面额）。

• 目标： 收银员希望用最少的硬币数量找零给顾客。

• 输入： 需要找的零钱数目（金额）。

• 输出： 构成该金额的硬币的最少数量。

2. 贪心法（Greedy Method）的求解思路

图片中明确指出了解决此问题的方法是贪心的策略：

1. 先用最大面值替换 (或使用)：从可用的最大面额硬币开始尝试。

2. 再次用大面值替换：重复使用当前能用的最大面额硬币，直到剩余金额不足以使用该面额。

3. ……

4. 最后用最小面值替换：一直重复，直到使用最小面额硬币完成找零。

具体步骤总结：

对于一个需要找零的金额 $A$：

1. 找到所有面额中小于或等于 $A$ 的最大面额硬币 $C_{\text{max}}$。

2. 尽可能多地使用该硬币 $C_{\text{max}}$（即使用 $\lfloor A/C_{\text{max}}\rfloor$ 个）。

3. 更新剩余的找零金额： $A\leftarrow A-(\text{使用的数量}\times C_{\text{max}})$。

4. 重复步骤 1-3，直到剩余金额 $A=0$。

3. 贪心法在这个问题上的有效性

值得注意的是，在大多数国家的标准货币体系（包括图示中的 1, 2, 5, 10, 20, 50, 100 等面额）下，贪心法可以保证找到最少硬币数的解。这是因为这些货币体系具有一个特性：任何一个面额都小于或等于紧接着的两个或三个较小面额之和。

但如果硬币面额是任意设定的（例如：1、3、4），贪心法可能就不能得到最优解。但在标准找零问题中，贪心法是正确的且高效的算法。

分治法

1. 基本思想 (Basic Idea)

分而治之 (Divide and Conquer) 是一种解决问题的策略，其核心步骤是：

1. 将一个较大规模的问题分解为若干个较小规模的子问题。

2. 找出这些子问题的解。

3. 将各个子问题的解合并成整个问题的解。

2. 构成要素的拆解

“分治法”这个名称本身就概括了它的两个主要阶段：

• 分 (Divide)：

  • 指划分较大的问题为若干个较小的问题。

  • 通过递归 (Recursion) 的方式求解这些子问题。

  • （潜台词：递归的终止条件是子问题足够小，可以直接求解。）

• 治 (Conquer)：

  • 指从这些小问题的解出发，构造出大问题的解。

总结：

分治法是一种高效的算法设计范式，它通过递归地“分” 解问题，并在子问题解决后** “合”并** 结果，最终得到原问题的解。许多著名的算法，如归并排序 (Merge Sort) 和 快速排序 (Quick Sort)，都是基于分治法设计的。

金块问题

1. 问题描述 (金块问题)

• 目标： 在给定的 $n$ 个物品（金块，等价于一个数值数组）中，找出最重（最大值 $\text{max}$）和最轻（最小值 $\text{min}$）的两个。

• 衡量指标： 比较次数 (Comparisons) 是衡量算法效率的主要指标。

2. 传统方法 (普通方法)

普通方法通常是指先找出最小值，再找出最大值。

• 找出最小值： 需要 $n-1$ 次比较。

• 找出最大值： 需要 $n-1$ 次比较。

• 总比较次数： $(n-1)+(n-1)=2n-2$ 次。

n 值	总比较次数 (2n−2)
$n=8$	$2\times 8-2=14$
$n=16$	$2\times 16-2=30$

注： 图片中 $n=8$ 时，普通方法写的是 $(n-1)+(n-2)=13$ 次。这可能是笔误，或采用了某种优化但未说明（例如，先找出 $\text{min}$ 之后，在剩下的 $n-1$ 个元素中找 $\text{max}$，但 $n-1$ 次比较通常仍是必需的）。标准双次遍历是 $2n-2$。

3. 分治法 (Divide and Conquer)

分治法的目标是通过递归地分解问题并优化合并过程，来减少总比较次数。

比较次数的分析 (以 $n=8$ 为例)：

• 分阶段： 将 $n=8$ 的序列分成两个 $n/2=4$ 的子序列。

• 递归求解 $n=4$：

  • 图片展示，$n=4$ 的子问题需要 $4$ 次比较。

  • $4$ 的子问题分成两个 $n/2=2$ 的子问题。

  • $n=2$ 的子问题只需要 $1$ 次比较来确定 $\text{min}$ 和 $\text{max}$ ($L$ 和 $H$)。

  • $\text{L}\leftarrow \text{min}$，$\text{H}\leftarrow \text{max}$。

• 合并 (Conquer) 阶段：

  • 将左半部分 ($\text{lmin},\text{lmax}$) 和右半部分 ($\text{rmin},\text{rmax}$) 的解合并起来。

  • 需要 2 次比较：

    1. 比较 $\text{lmin}$ 和 $\text{rmin}$，得到最终的 $\text{min}$。

    2. 比较 $\text{lmax}$ 和 $\text{rmax}$，得到最终的 $\text{max}$。

  • 图片中 $n=8$ 的图示：左半部分 $4$ 次，右半部分 $4$ 次，合并阶段 $2$ 次，总共是 $4+4+2=10$ 次。

分治法的总比较次数 $C(n)$ 的递推关系式：

当 n 是 2 的幂时，

$$C(n)=2C(n/2)+2(\text{当 }n>2\text{时})$$

边界条件：

$$C(2)=1$$

求解结果：

$$C(n)=\frac{3n}{2}-2$$

n 值	分治法的比较次数 (23n​−2)	传统方法的比较次数 (2n−2)
$n=8$	$\frac{3\times 8}{2}-2=12-2=10$	14 (或 13)
$n=16$	$\frac{3\times 16}{2}-2=24-2=22$	30 (或 29)

结论： 分治法 ($\frac{3n}{2}-2$) 相比于传统方法 ($2n-2$) 显著减少了比较次数，在 $n$ 较大时效率更高。

4. 程序代码 (Python 实现)

def min_max(a):
	 if len(a)==1: 
		 return (a[0],a[0]) 
	elif len(a)==2: 
		 return (min(a),max(a))
	else: 
		m=len(a)//2 
		lmin,lmax=min_max(a[:m]) 
		rmin,rmax=min_max(a[m:]) 
		return (min(lmin,rmin),max(lmax,rmax)) 
	
a,b=min_max([3,8,9,4,10,5,1,17])
print("最小值是",a,"，最大值是",b)

图片右侧提供了一个 Python 风格的 min_max(a) 递归函数，它实现了上述分治策略：

1. 基本情况 1 (Base Case 1): 如果数组长度为 1 (len(a)==1)，最小值和最大值都是这个元素。

2. 基本情况 2 (Base Case 2): 如果数组长度为 2 (len(a)==2)，通过 1 次比较直接返回 $\text{min}$ 和 $\text{max}$。

3. 递归情况 (Recursive Case):

   • 将数组从中间分成左右两半。

   • 递归调用 min_max 找出左右两半的 $\text{min}/\text{max}$ (lmin, lmax 和 rmin, rmax)。

   • 合并 (Merge)： 通过比较两个 $\text{min}$ 找到最终的 $\text{min}$ (min(lmin, rmin))，通过比较两个 $\text{max}$ 找到最终的 $\text{max}$ (max(lmax, rmax))，然后返回。

动态规划法

1. 动态规划的基本思想

动态规划是一种解决复杂问题的数学优化方法，其核心思想在于：

• 分解与重叠子问题： 如果一个较大的问题可以被分解为若干个子问题，并且这些子问题之间具有重叠性（即相同的子问题会被多次计算）。

• 查表解决 (Memoization)： 可以将每个子问题的解计算一次后，存放到一个表中（通常是数组或表格）。当需要再次用到该子问题解时，只需通过查表即可，避免了重复计算。

2. 核心思想

• 以空间换时间： 通过使用额外的存储空间（即那个“表”）来记录子问题的解，从而避免了重复计算，显著地提高了计算效率（减少了计算时间）。

3. 应用示例：多阶段决策最优路线问题

图片右侧展示了一个典型的动态规划应用场景：多阶段决策图中的最短/最优路径问题。

• 问题描述： 寻找从起点 $A$ 到终点 $B$ 的最优路径（例如：最短时间或最低成本）。

• 阶段划分： 路径被划分为 A $\to$ F 阶段 $\to$ G 阶段 $\to$ H 阶段 $\to$ B。

• 动态规划的优势：

  • 通过动态规划方法，可以从终点 $B$ 逆向或从起点 $A$ 正向推导，逐步计算出到达每个节点的最优路径长度。

  • 图中标注的数字（如 $F1$ 节点旁的 $830$）可能代表从 $F1$ 到终点 $B$ 的最优路径长度（或从 $A$ 到 $F1$ 的最优路径长度）。

  • 最终的结论是：“不仅仅求出了从 $A$ 到 $B$ 的最优路线，而且求出了任一点到 $A$ 的最优路线！”（如果是逆向推导，则是任一点到 $B$ 的最优路线）。这体现了动态规划通过求解所有子问题，从而自然获得全局最优解的特性。

回溯法

1. 别称

• 回溯法

• 穷尽搜索法 (Brute-Force Search)

2. 基本思想 (核心机制)

回溯法是一种系统地搜索问题解集的方法，它通过递归地构造解，并在发现当前路径无法得到有效解时退回到上一步：

• 尝试分步求解： 在分步解决问题的过程中，算法会一步一步地做出选择，构建一个候选解。

• 回溯机制 (Backtracking)： 当它通过尝试发现当前分步答案不能得到有效的、正确的解答时（即遇到死胡同或不满足约束条件）：

  • 取消/撤销上一步甚至前几步的计算（“回溯”）。

  • 重新尝试其他可能的选择或分步解，再次尝试寻找问题的答案。

3. 实现方式

• 通常使用递归 (Recursion) 实现。

4. 图示解析 (状态空间树)

图片下方的树状结构是回溯法搜索过程的状态空间树：

• 节点： 代表问题的某个状态或当前已经做出的选择序列。

• 分支： 代表在当前状态下可以做出的不同选择（例如：“选”或“不选”）。

• 搜索过程： 算法从根节点开始，沿着一个分支深入搜索（如：选 1 $\to$ 选 2 $\to$ 选 3）。

• 回溯的体现：

  • 如果走到一个叶子节点发现不满足要求，或者在中间某一步发现无论如何都无法得到最终解，算法就会回溯到上一个岔路口。

  • 例如，如果左侧的 “1 2 3” 这个路径不符合要求，它会回到上一步（在 “1 2” 状态），尝试另一个分支（不选 3），然后再继续搜索。

总结： 回溯法是一种“试错”的搜索策略，它通过定义明确的选择路径，并在失败时高效地撤销（回溯）并尝试其他路径，最终系统地找到所有可能的解或最优解。

2. 一般问题求解

人工智能经典问题求解

1. 求解问题的范围

人工智能解决的是：

• 复杂问题

• 人类难以解决的问题

• 需要借助计算机算法工具辅助解决的问题

2. 经典问题求解方法与案例对应表

图片将 AI 解决问题的五种主要方法与五个典型的案例进行了对应：

求解方法种类 (Solution Methods)	典型问题案例 (Classic Problem Cases)
状态搜索空间法 (State-Space Search)	八数码 (Eight Puzzle)
启发式搜索求解 (Heuristic Search)	走迷宫 (Maze Solving)
遗传算法求解 (Genetic Algorithm)	旅行推销员 (Traveling Salesperson Problem, TSP)
模拟退火求解 (Simulated Annealing)	拼图游戏 (Jigsaw Puzzle)
约束满足问题求解 (Constraint Satisfaction Problem, CSP)	数独游戏 (Sudoku)

简要说明：

• 状态空间搜索 (八数码)： 通过定义问题的初始状态、目标状态和操作（移动），在所有可能的状态中系统地搜索解。

• 启发式搜索 (走迷宫)： 在搜索过程中加入“启发信息”（如：离目标更近），从而更有效地找到路径，避免盲目搜索。

• 遗传算法 (旅行推销员)： 模仿生物进化过程，通过选择、交叉、变异等操作来逐步优化解，适用于复杂的优化问题。

• 模拟退火 (拼图游戏)： 模仿物理学中金属退火过程，以概率接受较差的解来跳出局部最优，适用于复杂的组合优化问题。

• 约束满足问题 (数独)： 通过定义变量、域和约束条件，找到满足所有约束的赋值。

这张图清晰地展示了人工智能在问题求解领域中，针对不同特性的问题所采用的不同算法策略。

八数码与状态搜索空间法

1. 八数码问题 (Eight Puzzle)

问题描述：

• 八数码是在一个 $3\times 3$ 的网格中随机放置了 $1$ 到 $8$ 这八个数字的滑块。

• 其中有一个网格是空着的（即空格）。

• 操作规则： 可以将空格与它上下左右四个方向的任何一个相邻的数码进行交换。

• 限制： 空格不能跟斜方向上的数码交换。

图示说明：

• (a) 初始状态： 随机的起始布局，例如：

  $$\left(\begin{array}{ccc}6& 2& 5\\ 3& 8& \text{空}\\ 4& 7& 1\end{array}\right)$$

• (b) 子状态： 通过一次操作（例如空格与 5 交换）得到的状态，例如：

  $$\left(\begin{array}{ccc}6& 2& \text{空}\\ 3& 8& 5\\ 4& 7& 1\end{array}\right)$$

• © 终止状态 (目标状态)： 期望达到的有序布局，例如：

  $$\left(\begin{array}{ccc}1& 2& 3\\ 8& \text{空}& 4\\ 7& 6& 5\end{array}\right)$$

问题目标：

• 研究如何用最少的次数移动空格，从而使得八数码最终呈现出所示的终止状态。

2. 八数码与状态搜索空间法 (State-Space Search)

八数码问题是一个典型的可以通过状态搜索空间法来求解的问题。

状态空间 (State Space) 的定义：

如果一个问题可以被定义为状态空间中的一个初始状态，通过一系列操作或动作转换直到达到目标状态，那么这个问题就是状态空间问题。

状态空间包含四个要素：

1. (1) 初始状态 (Initial State)： 问题开始时的状态（八数码中的 (a) 初始布局）。

2. (2) 目标状态 (Goal State)： 问题希望达到的状态（八数码中的 © 终止布局）。

3. (3) 操作 (Operators)： 从一个状态转换到另一个状态的规则或操作（八数码中的“空格与相邻数码交换”）。

4. (4) 路径 (Path)： 从初始状态到目标状态的一系列操作的集合（八数码中“最少”的移动次数序列）。

流程图：

流程图清晰地展示了状态空间搜索的基本过程：

$$\text{初始状态}\stackrel{\text{操作 1}}{\to }\cdots \stackrel{\text{操作 n}}{\to }\text{目标状态}$$

其中，一系列操作构成了路径。

走迷宫与启发式搜索

1. 启发式搜索的定义

• 技术： 启发式搜索是在搜索空间中查找问题解决方案的一种技术。

• 核心： 它使用一个启发式函数 (Heuristic Function) 来评估和选择哪个分支（路径）最有可能导向最优解。

2. 启发式函数的本质

• 启发式函数可以被看作是一种“直觉”或“猜想”。

• 作用： 帮助算法决定下一步最希望的路径。

3. 典型案例：走迷宫问题

走迷宫问题就是一种经典的启发式搜索问题。

• 问题： 从起点到达终点。

• 启发式函数示例： 可以使用距离终点的直线距离作为启发式函数。

• 搜索策略：

  • 算法在每一步都会选择那些看起来离终点更近的路径。

  • 尽管这种方法不保证每一步都朝着最终目标直行，但整个搜索过程会倾向于向终点方向前进，从而提高了搜索的效率。

总结： 启发式搜索是一种利用问题领域知识（即“直觉”或“经验”）来指导搜索方向的方法，它通过启发式函数来评估潜在路径的优劣，以期在复杂的搜索空间中高效地找到解，尤其适用于走迷宫这类需要快速定位目标的场景。

旅行推销员与遗传算法求解

1. 遗传算法的本质

• 定义： 遗传算法是一种模拟自然选择的优化技术。

• 概念基础： 它们使用生物进化的概念，如变异 (Mutation)、交叉 (Crossover) 和选择 (Selection) 来解决问题。

2. 典型案例：旅行推销员问题 (TSP)

• TSP 目标： 要求找到最短的路径，访问一系列城市后并返回原点。这是一个经典的 NP-hard 优化问题。

• 遗传算法的应用：

  • 种群 (Population)： 可以随机生成多个“种群”，其中每个“种群”（或“个体”）代表一种可能的路径。

  • 新路径生成： 通过交叉（将两条路径的部分组合）和变异（随机改变路径中的某个步骤）来产生新的路径。

  • 选择： 使用适应度函数 (Fitness Function) 来评估每条路径的优劣。

    • 在本例中，适应度函数是“总距离”。 距离越短，适应度越高。

    • 算法会选择适应度最高的路径进入下一代。

  • 结果： 随着时间的推移（代数的增加），这个进化过程可能会找到一个非常接近最短可能路径的解决方案。

图示说明：

图片右侧的图是一个简化的加权图，表示城市 ($A,B,C,D,E,F$) 及其之间的连接距离（权重）。TSP 算法的目标就是在这个图中找到一个闭合回路，使得总权重最小。

总结： 遗传算法通过模仿生物的优胜劣汰机制，不断优化一个种群中的解（路径），最终找到复杂优化问题的一个高质量的近似最优解。

拼图与模拟退火

1. 模拟退火算法的本质

• 定义： 模拟退火是一种概率性的优化技术。

• 灵感来源： 金属退火过程（通过加热和缓慢冷却来改变金属结构，使其达到低能量、稳定状态）。

2. 核心机制：引入随机性

• 目标： 避免算法陷入局部最优解（即找到的解不是全局最优的）。

• 方法： 在搜索过程中引入随机性，允许算法在早期阶段进行“坏”的移动（即接受那些看起来并非更优的解）。

• 目的： 探索更大的搜索空间。

3. 典型案例：拼图游戏

• 问题： 将一组零件放置在正确的位置，最终完成拼图。

• 模拟退火的应用：

  1. 初始状态： 从一个随机的拼图配置开始。

  2. 移动尝试： 在每一步尝试移动一块拼图。

  3. 接受“坏”解： 即使某些移动一开始看起来并不朝向解决方案（即让拼图状态变差），算法也可能会以一定概率接受它们。

  4. 退火过程（降温）： 随着时间的推移（模拟温度的下降），算法变得越来越不可能接受那些使拼图状态变差的移动。

  5. 结果： 最终算法会趋向于解决方案，达到一个稳定的、高质量的解（完成的拼图）。

总结：

模拟退火算法通过模仿物理降温过程，在初期阶段以较高的概率接受较差的解来跳出局部陷阱，随着搜索的深入，概率逐渐降低，从而确保算法能够找到全局最优或近似最优的解。

数独与约束满足问题求解

• 数独是一个典型的约束满足问题（CSP）。
• 规则要求：每个数字在3×3子网格、每行、每列中都必须唯一出现。
• CSP求解器的目标是找到满足所有约束条件的变量赋值。

一句话总结：
数独是一种约束满足问题，要求数字在行、列和子网格中唯一出现，CSP求解器用于找到满足这些约束的数字分配方案。

3. 机器学习求解

1. 机器学习的定义与地位

• 核心领域： 机器学习是 AI (人工智能) 的核心领域之一。

• 本质： 它是一种基于数据统计建模的问题求解方法。

2. 机器学习的求解过程（流程图）

流程图展示了机器学习如何利用数据进行学习和预测：

1. 输入 (历史数据)： 计算机程序利用历史数据进行训练。这个训练过程是用数据优化计算机程序的模型参数。

2. 核心 (模型)： 训练得到一个模型 (Model)。

3. 应用与输出 (预测)： 当有新的输入数据时，将数据输入到训练好的模型中，模型会输出预测结果（即未知属性）。

3. 采用 AI/机器学习解决任务的标准步骤

应用机器学习方法解决任何一个任务，通常都需要经过以下四个步骤：

1. 定义模型 (Define Model)： 确定使用哪种类型的算法（例如：线性回归、决策树、神经网络等）以及模型的结构。

2. 训练模型 (Train Model)： 将历史数据输入模型，通过优化算法调整模型参数，使模型能够从数据中学习规律。

3. 测试模型 (Test Model)： 使用从未见过的测试数据来检验训练好的模型在新数据上的表现能力。

4. 评估模型 (Evaluate Model)： 使用特定的评估指标（如准确率、召回率、F1 分数等）来量化模型的性能，判断其是否满足任务要求。

总结： 机器学习是 AI 的核心技术，它通过数据驱动的方式，经过定义、训练、测试和评估四个阶段，建立能够从历史数据中学习并对新数据进行预测的统计模型。

机器学习的定义

机器学习的形式化定义

1. 已知条件：

   • 存在一个数据集 $X$。

   • $Y$ 与 $X$ 存在某种对应关系。

   • $Y$ 被称为 $X$ 的标签 (Label)（在监督学习中）。

2. 目标：

   • 寻找一个函数或模型 $F$。

   • 使得 $F$ 作用在 $X$ 上的结果 $Y^{\prime }=F(X)$。

   • 这个结果 $Y^{\prime }$ 应该与真实的标签 $Y$ 尽可能地接近，即满足：$|Y-Y^{\prime }|$ 尽可能小。

   • 注： $|Y-Y^{\prime }|$ 是衡量预测值 $Y^{\prime }$ 和真实值 $Y$ 之间差异的误差或损失函数，目标是最小化这个误差。

3. 定义：

   • 把利用机器的算法寻找函数 $F$ 的过程，称为机器学习 (Machine Learning)。

总结：

机器学习的目标是从数据中学习，找到一个最优函数 $F$ 来模拟输入数据 $X$ 和真实标签 $Y$ 之间的潜在关系，从而使得模型的预测结果 $Y^{\prime }$ 与真实结果 $Y$ 之间的误差最小。

机器学习的类型

学习类型	形式化定义 (数据条件)	通俗比喻 (学习方式)
有监督学习 (Supervised Learning)	若所有的输入数据 $X$ 都有对应的标签 $Y$。	有老师带着你学习（即有标准答案指导）。
无监督学习 (Unsupervised Learning)	若没有标签 $Y$（只有输入数据 $X$），目标是学习 $X$ 内部的知识（如结构、模式）。	没有老师带着你，你自己学习（即自己摸索数据间的关系）。
半监督学习 (Semi-Supervised Learning)	若一部分输入数据 $X$ 有对应的标签 $Y$。	老师教了你部分的答案，其余不告诉你（即只有少量数据有标签）。

核心区分点：

• 标签 ($Y$) 的数量和存在性是区分这三种学习方式的关键。

  • 有监督： 100% 标签。

  • 无监督： 0% 标签。

  • 半监督： 介于 0% 和 100% 之间（少量标签）。

机器学习五个要素

机器学习求解方法的五个要素

1. 数据 (Data)

   • 定义： 机器学习的基础，是模型学习的依据。

   • 类型： 包括结构化的（如表格数据）和非结构化的（如文本、图像、音频）。

2. 模型 (Model)

   • 定义： 用于进行预测或分类的数学表示。

   • 功能： 模型通过从数据中学习并调整其参数来提高自身的性能。

3. 训练 (Training)

   • 定义： 训练过程是模型从数据中学习的过程。

   • 核心机制： 通常涉及最小化某个损失函数 (Loss Function) 以优化模型参数。

4. 预测 (Prediction)

   • 定义： 基于训练好的模型，对新数据进行预测或分类的动作。

5. 评估 (Evaluation)

   • 定义： 使用各种评估指标来衡量模型的性能。

   • 常见指标： 如准确率 (Accuracy)、精确率 (Precision)、召回率 (Recall)、F1 分数 (F1 Score) 等。

总结： 机器学习是一个流程，它以数据为基础，通过训练来优化模型，实现对新数据的预测，并通过评估来衡量其效果。

机器学习的工具和框架

1. 机器学习的实现方法

• 回归分类方法 (Regression and Classification Methods): 这是机器学习中最基础和常见的两大类任务和方法。

• 神经网络方法 (Neural Network Methods): 指以神经网络为基础的算法，包括传统的浅层神经网络和更复杂的深度学习模型。

2. 机器学习工具 (基础库)

• 机器学习库：scikit-learn：一个流行且功能丰富的 Python 库，用于传统的机器学习算法（如回归、分类、聚类等）。

3. 深度学习框架 (Deep Learning Frameworks)

• Pytorch：一个由 Facebook AI Research (FAIR) 开发的深度学习框架，以动态计算图和易用性著称。

• Mindspore：一个由华为开发的深度学习框架，支持云、边缘和设备端部署。

4. 高级工具

• keras：高级神经网络 API：一个高层 API，通常运行在 TensorFlow、Theano 或 CNTK 等后端之上，旨在提供快速的实验和原型设计能力。

• XGBoost：优化的分布式梯度提升库：一个高效、灵活且可移植的库，实现了梯度提升决策树 (Gradient Boosting Decision Tree) 算法，常用于赢得数据科学竞赛。

总结：

从基础的回归/分类到先进的神经网络方法，列举从传统的 scikit-learn 库，到 Pytorch/Mindspore 深度学习框架，再到 Keras/XGBoost 等高级工具，涵盖了机器学习技术栈的关键组成部分。

机器学习的挑战问题

机器学习面临的四个主要问题

1. (1) 数据质量问题 (Data Quality Issues)

   • 描述： 数据的准确性、完整性和一致性直接影响模型的性能。

   • 含义： 如果数据是错误的、缺失的或不统一的，那么即使是最好的模型也无法做出好的预测。

2. (2) 过拟合问题 (Overfitting)

   • 描述： 模型在训练数据上表现很好，但在新数据上表现不佳。

   • 原因： 通常是由于模型过于复杂导致的，模型学习到了训练数据中特有的噪声和细节，而不是普遍的规律。

3. (3) 计算资源问题 (Computational Resource Issues)

   • 描述： 训练复杂模型需要大量的计算资源和时间。

   • 含义： 特别是深度学习模型，往往需要高性能的 GPU/TPU 和充足的时间才能完成训练和优化。

4. (4) 模型解释性问题 (Model Interpretability Issues)

   • 描述： 一些复杂模型（如深度神经网络）难以解释其决策过程。

   • 含义： 这在某些应用场景中可能是一个问题，例如金融、医疗或法律等需要高透明度和可解释性的领域，用户需要知道模型“为什么”做出这个决定。

总结： 机器学习的挑战不仅在于选择和训练算法本身，还涉及到数据准备、避免过度优化，以及在实际应用中对资源和模型透明度的要求。

scikit-learn与MindSpore

介绍两个用于机器学习和深度学习的库/框架：Scikit-learn和MindSpore，并指出它们将一起用于实现机器学习算法。

总结如下：

1. Scikit-learn (Sklearn)：

   • Python中最受欢迎的机器学习库，提供从线性回归到深度学习的丰富算法。

   • 拥有丰富的实用工具（特征工程、数据预处理、模型选择等）和完善的文档。

   • 使用时需要熟悉数据加载、模型选择、训练与评估、参数调整等基本操作。

2. MindSpore：

   • 华为自主开发的开源深度学习框架，面向AI开发、训练与推理部署。

   • 优化了在华为昇腾（Ascend）芯片上的性能。

   • 于2020年正式开源，支持昇腾、CPU和GPU等多种硬件平台。

   • 支持自动并行、动态&静态图统一、差分隐私等特点。

3. 目的：接下来将结合使用MindSpore与Sklearn来实现机器学习算法。

scikit-learn算法组成

scikit-learn库中的机器学习算法主要分为以下四大类：

1. 分类 (classification)

2. 回归 (regression)

3. 聚类 (clustering)

4. 降维 (dimensionality reduction)

MindSpore生态工具和套件

清晰地展示了 MindSpore 框架所包含的各种套件，这些套件覆盖了广泛的应用领域，为不同领域的开发者提供了便利。

MindSpore 套件概览:

类别	套件名称 (中文翻译)
工具	MindSpore Insight (调试调优工具)
	MindSpore Armour (安全隐私保护工具)
	MindSpore Golden Stick (模型压缩算法工具)
领域套件	MindSpore CV (计算机视觉)
	MindSpore NLP (自然语言处理)
	MindSpore OCR (OCR 领域)
	MindSpore YOLO (YOLO 领域)
科学计算套件	MindSpore Elec (电磁仿真)
	MindSpore SPONGE (计算生物学)
	MindSpore Flow (流体仿真)
	MindSpore Earth (地球科学)
	MindSpore Chemistry (化学/材料)
	MindSpore Quantum (量子计算)
大模型套件	MindSpore Transformers (Transformers 大模型)
	MindSpore One (多模态)
	MindSpore RLHF (强化学习)
	vLLM MindSpore (对接 vLLM 插件)
核心框架	MindSpore (核心框架)
	MindSpore Lite (推理引擎)

总结：

MindSpore 的生态系统是模块化的，它不仅包含核心框架和轻量级推理引擎，还提供了专门针对：

• 特定AI领域 (如 CV、NLP、OCR) 的领域套件。

• 科学计算与仿真 (如电磁、生物、流体、量子) 的科学计算套件。

• 大型语言模型和多模态 的大模型套件。

• 开发辅助 (如调试、安全、压缩) 的工具。

scikit-learn

Sklearn 的下载安装步骤：

1. 准备环境： 确保已安装并配置好 Python 环境。

2. 安装命令（通用）：

   输入：python -m pip install scikit-learn

3. 安装命令（使用清华镜像源加速）：

   输入：python -m pip install scikit-learn -i https://pypi.tuna.tsinghua.edu.cn/simple

说明： 第二条命令使用了清华大学的 PyPI 镜像源 (https://pypi.tuna.tsinghua.edu.cn/simple) 来加速下载和安装过程，在中国大陆地区通常推荐使用。

scikit-learn使用的基本操作

进行机器学习项目或使用机器学习库（如 Scikit-learn 或 MindSpore）时，通常遵循的四个核心步骤：

1. 准备、加载数据和预处理（特征工程）：这是模型训练的基础，包括数据清洗、格式转换、缺失值处理以及将原始数据转化为模型可理解的特征（特征工程）。

2. 选择模型：根据要解决的问题类型（如分类、回归、聚类等）和数据的特点，选择合适的机器学习算法。

3. 训练和评估模型：使用准备好的数据对选定的模型进行训练，然后使用独立的测试集来评估模型的性能和泛化能力。

4. 调整模型的参数以获得更好的性能：通过调整模型的超参数（Hyperparameters），如学习率、正则化强度等，来优化模型，以达到更高的准确性或更好的性能指标。

数据集

内容主要介绍了如何使用 Scikit-learn 的 datasets 模块来加载常见数据集，并区分了加载小规模数据集和大规模数据集的方法。

内容总结如下：

1. Sklearn 常见数据集列表：

数据集类型	数据集名称	调用方式	适用算法	数据规模
小数据集	波士顿房价	load_boston()	回归	506×13
小数据集	鸢尾花数据集	load_iris()	分类	150×4
小数据集	糖尿病数据集	load_diabetes()	回归	442×10
大数据集	手写数字数据集	load_digits()	分类	5620×64
大数据集	Olivetti 脸部图像数据集	fetch_olivetti_faces()	降维	400×4096
大数据集	新闻分类数据集	fetch_20newsgroups()	分类	-
大数据集	带标签的人脸数据集	fetch_lfw_people()	分类、降维	-
大数据集	路透社新闻语料数据集	fetch_rcv1()	分类	804,414×47,236

2. 加载小规模数据集：

   • 使用 sklearn.datasets.load_*() 函数。

   • 数据通常已经包含在 datasets 模块安装包内。

3. 加载大规模数据集：

   • 使用 sklearn.datasets.fetch_*($data\_home=None$) 函数。

   • 需要从网络下载数据。

   • 第一个参数 data_home 表示数据集下载和存放的目录，默认是 /scikit_learn_data/。

4. 举例：获取鸢尾花数据集

    from sklearn.datasets import load_iris
    # 获取鸢尾花数据集
    iris = load_iris()
    print("鸢尾花数据集的返回值:", iris.keys())
    ```
    
- 示例代码展示了如何导入并调用 `load_iris()` 函数，并打印了返回对象的键（keys），以便查看数据集包含的内容（如数据、目标、特征名称等）。
## 数据预处理方法

```python
# 导入内置数据集的函数
from sklearn.datasets import load_iris

# 获取鸢尾花数据集
iris = load_iris()

# 获取 ndarray 格式的特征数据 X 和标签数据 y
X = iris.data
y = iris.target

# 获取数据集的维度 (样本数, 特征数)
n_samples, n_features = iris.data.shape

# 打印维度信息
print(n_samples, n_features)

数据预处理的解释和常用方法：

• 预处理：通过一些转换函数将特征数据转换成更适合算法模型的特征数据过程。

• 常见方法：数据标准化、数据二值化、标签编码、独热编码等。

数据标准化处理

数据预处理的概念和方法，以及加载鸢尾花数据集的Python代码。

一、数据预处理（标准化和归一化）

核心概念：

数据标准化和归一化是将数据映射到一个小的浮点数范围内，以便模型能快速收敛。

三种常见方法：

序号	方法名称	对应 Scikit-learn (sklearn) 对象	公式	效果
1	Min-max标准化	MinMaxScaler	$x^{\prime }=\frac{x-x_{\min }}{x_{\max }-x_{\min }}$	将数据缩放到 $[0,1]$ 区间。
2	Z-score标准化	StandardScaler	$x^{\prime }=\frac{x-\bar{x}}{S}$	使数据满足标准正态分布（均值为 0，方差为 1）。
3	归一化 (Normalization)	Normalizer	$x^{\prime }=\frac{x}{\sqrt{{\sum }_j^m{x}_j^2}}$	默认是 L2 归一化，将单个样本的特征向量的范数（长度）缩放到 1。

---

二、加载鸢尾花数据集的 Python 代码

这部分代码展示了如何使用 scikit-learn (sklearn) 加载和初步查看数据集：

代码行	注解	目的/说明
from sklearn.datasets import load_iris	# 导入内置数据集	导入用于加载鸢尾花数据集的函数。
iris = load_iris()	# 获取鸢尾花数据集	加载鸢尾花数据集到变量 iris。
X = iris.data	# 获得 ndarray 格式的变量 X	将特征数据（自变量）提取到 X 中。
y = iris.target	# 获得 ndarray 格式的标签 y	将标签数据（因变量/目标值）提取到 y 中。
n_samples, n_features = iris.data.shape	# 获得数据维度	获取数据集的样本数和特征数。
print(n_samples, n_features)		打印输出数据集的维度信息。

数据二值化

数据二值化 (Binarization) 的概念、实现方法和相关 Python 代码。

总结

1. 概念

• 数据二值化：使用阈值（Threshold）过滤器将数据转换为布尔值（即 0 或 1）。

• 目的：将数值特征转换为二元的离散特征。

2. 实现方式

• 使用 Scikit-learn (sklearn) 库中的 Binarizer 对象来实现数据的二值化。

3. 示例代码及注解

# 从 sklearn.preprocessing 模块中导入 Binarizer（二值化器）
from sklearn.preprocessing import Binarizer 

# 创建一个 Binarizer 实例，设置阈值 threshold=3
# 含义：如果特征值 > 3，则转为 1；否则转为 0
binarizer = Binarizer(threshold=3)

# 使用 fit_transform() 对数据 X 进行“拟合并转换”
# 注意：Binarizer 不需要真正的“训练”，fit_transform 等价于 transform
# 结果是一个与 X 形状相同的矩阵，但数值变成 0/1（布尔化处理）
results = binarizer.fit_transform(X)

# 打印第 1 行（索引为 1）的原始数据
print("处理前: ", X[1])

# 打印第 1 行（索引为 1）经过二值化后的结果
print("处理后: ", results[1])

标签编码和独热编码

两种重要的编码技术：标签编码 (Label Encoding) 和 独热编码 (One-Hot Encoding)。

总结

1. 标签编码 (Label Encoding)

• 概念：使用 LabelEncoder 将不连续的数值或文本变量转化为有序的数值型变量。

• 适用场景：主要用于目标标签 (y) 的编码，尤其当标签本身具有顺序关系时。

示例代码 (假设执行并打印结果):

from sklearn.preprocessing import LabelEncoder
# 实例化并对列表进行编码
encoded_labels = LabelEncoder().fit_transform(['apple', 'pear', 'orange', 'banana'])
# 结果示例: [0 2 1 3] (顺序取决于LabelEncoder的内部处理)
# print(encoded_labels)

---

2. 独热编码 (One-Hot Encoding)

• 概念：对于无序的离散型特征，其数值大小没有意义时，进行 one-hot 编码。

• 作用：将特征的 $m$ 个可能值转化为 $m$ 个二值化 (0, 1) 特征。这解决了模型将无序特征误认为是连续有序数值的问题。

• 实现：利用 OneHotEncoder 对象实现。

示例代码 (假设 y 是已加载的标签数组，且维度正确):

from sklearn.preprocessing import OneHotEncoder
import numpy as np

# 假设 y 是一个包含 3 种类别标签的 numpy 数组，例如：
# y = np.array([0, 1, 2, 1, 0]) 
# 确保 y 已在前面步骤中加载

# 独热编码过程
results = OneHotEncoder().fit_transform(y.reshape(-1, 1)).toarray()

# 假设 y[1] = 1，处理后 results[1] 的输出可能为 [0. 1. 0.] (如果共有 3 类别)
# print("处理前:", y) 
# print("处理后:", results[1]) 

Sklearn与Mindspore

Scikit-learn (Sklearn) 和 MindSpore 在机器学习流程中的分工，并展示了一个使用 MindSpore 实现简单线性回归的完整代码示例。

总结

1. 机器学习工具分工说明

• Sklearn：在后续课程中主要用于数据获取和数据预处理功能（如生成数据集、数据标准化、划分训练集/测试集）。

• MindSpore：用于手动实现相关机器学习算法的核心功能，包括模型构建、训练、评估和预测。

2. 简单线性回归示例代码 (MindSpore)

以下是使用 Sklearn 进行数据准备和 MindSpore 进行模型训练和预测的完整代码：

A. 导入必要的库

import numpy as np
from sklearn.datasets import make_regression
from sklearn.model_selection import train_test_split
from sklearn.preprocessing import StandardScaler
import mindspore.nn as nn
from mindspore import Tensor, Model
from mindspore.dataset import GeneratorDataset
from mindspore.train.callback import LossMonitor
import matplotlib.pyplot as plt

B. 数据准备（Sklearn 部分）

# 生成模拟回归数据集
X, y = make_regression(n_samples=100, n_features=1, noise=15.0, random_state=42)

# 数据标准化（特征X）
X = StandardScaler().fit_transform(X)

# 划分训练集和测试集
X_train, X_test, y_train, y_test = train_test_split(X, y, test_size=0.2, random_state=42)

# 转换数据类型并调整形状以适应MindSpore要求
X_train = X_train.astype(np.float32)
y_train = y_train.astype(np.float32).reshape(-1, 1) # 调整为 (n_samples, 1)
X_test = X_test.astype(np.float32)
y_test = y_test.astype(np.float32).reshape(-1, 1) # 调整为 (n_samples, 1)

# 创建MindSpore的生成器数据集
train_data = [(X[i], y[i]) for i in zip(X_train, y_train)]
train_dataset = GeneratorDataset(train_data, column_names=["X", "y"], shuffle=True).batch(16)

C. 模型构建、训练与预测（MindSpore 部分）

# 线性回归模型类定义
class LinearRegression(nn.Cell):
    def __init__(self, nn_Cell):
        super(LinearRegression, self).__init__()
        self.fc = nn.Dense(1, 1) # 定义全连接层，输入1特征，输出1结果

    def construct(self, x):
        return self.fc(x)

# 实例化模型、损失函数和优化器
net = LinearRegression(nn.Cell)
model = Model(net, nn.MSELoss(), nn.SGD(net.trainable_params(), 0.01)) # 均方误差损失，SGD优化器

# 模型训练
model.train(100, train_dataset, callbacks=[LossMonitor(10)], dataset_sink_mode=False)

# 模型预测
y_pred = model.predict(Tensor(X_test)).asnumpy()

# 结果可视化
plt.scatter(X_test, y_test, c='blue')
plt.plot(X_test, y_pred, c='red')
plt.title('MindSpore Linear Regression')
plt.show()