XiaoMaColtAI/math-modeling-skill
math-modeling
Verified当用户要求数学建模、建模竞赛、建模分析、代码求解、结果可视化或生成数学建模论文时使用。支持完整三阶段流程、单独执行任一角色,以及在关键节点使用独立 Subagent 进行阶段内质检;默认只启用质检 Subagent,用户可明确选择额外协作。
| File | Kind | Size |
|---|---|---|
| SKILL.md | skill md | 10.5 KB |
| assets/01-优化算法说明.md | markdown | 79.1 KB |
| assets/02-预测类算法说明.md | markdown | 67.4 KB |
| assets/03-评价类算法说明.md | markdown | 81.6 KB |
| assets/04-图论与网络分析算法说明.md | markdown | 38.8 KB |
| assets/05-统计分析与数据处理算法说明.md | markdown | 60.7 KB |
| assets/06-综合类算法说明.md | markdown | 35.6 KB |
| assets/07-机器学习算法说明.md | markdown | 51.9 KB |
| assets/README.md | markdown | 9.1 KB |
| references/README.md | markdown | 2.1 KB |
| references/Subagent调度.md | markdown | 7.4 KB |
| references/交付与截止时间协议.md | markdown | 4.4 KB |
| references/算法索引.md | markdown | 1021 B |
| scripts/sync_dsh_plugin.py | script | 7.3 KB |
assets/06-综合类算法说明.md
View on GitHub# 综合类算法说明文档
## 概述
综合类算法涵盖数学建模中多种跨领域的算法方法,包括模拟仿真、博弈论、排队论、元胞自动机、马尔科夫链等。这些算法在系统仿真、决策分析、随机过程建模等方面有广泛应用。
---
## 1. 蒙特卡洛模拟 (Monte Carlo Simulation)
### 算法介绍
蒙特卡洛模拟是一种通过随机采样来估算数值结果的计算方法,基于概率统计理论。
#### 1.1 基本原理
**大数定律**:当试验次数$n \to \infty$时,样本均值收敛于期望值。
$$
\bar{X}_n = \frac{1}{n} \sum_{i=1}^{n} X_i \xrightarrow{P} E[X]
$$
**中心极限定理**:
$$
\frac{\bar{X}_n - \mu}{\sigma/\sqrt{n}} \xrightarrow{d} N(0, 1)
$$
#### 1.2 随机数生成
**均匀分布U(0,1)**:基本随机数
**逆变换法**:设$X$的CDF为$F(x)$,则$X = F^{-1}(U)$,其中$U \sim U(0,1)$
**正态分布**:
- Box-Muller方法
- 极坐标方法
- 拒绝采样
**指数分布**:$X = -\frac{1}{\lambda} \ln(U)$
#### 1.3 积分计算
**定积分估计**:
$$
I = \int_a^b f(x) dx \approx \frac{b-a}{n} \sum_{i=1}^{n} f(X_i)
$$
其中$X_i \sim U(a, b)$
**高维积分**:特别适合高维积分问题。
#### 1.4 误差分析
**标准误差**:
$$
SE = \frac{\sigma}{\sqrt{n}}
$$
**置信区间**(95%):
$$
\bar{X} \pm 1.96 \times \frac{\sigma}{\sqrt{n}}
$$
#### 1.5 方差缩减技术
**重要性采样**:对重要区域增加采样
$$
I = \int f(x) dx = \int \frac{f(x)}{g(x)} g(x) dx
$$
**分层采样**:将样本空间分层
**对偶变量**:利用负相关性减少方差
**控制变量**:使用已知期望的变量
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 概率计算 | 复杂系统概率 | 难以解析求解 |
| 积分计算 | 高维积分 | 数值积分困难 |
| 风险分析 | 项目风险评估 | 不确定性分析 |
| 金融定价 | 期权定价 | 路径依赖 |
| 可靠性分析 | 系统可靠性 | 复杂系统 |
| 物理模拟 | 粒子输运 | 随机过程 |
### 可视化图表类型
- **收敛曲线**:估计值随采样次数变化
- **直方图**:随机变量分布
- **散点图**:随机采样点分布
- **置信区间图**:不确定性可视化
- **路径图**:随机过程轨迹
- **热力图**:高维采样分布
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Monte Carlo Methods | Hammersley & Handscomb | 1964 | Methuen |
| Simulation and the Monte Carlo Method | Rubinstein & Kroese | 2016 | Wiley |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
def monte_carlo_integral(f, a, b, n=100000):
"""
蒙特卡洛积分计算
:param f: 被积函数
:param a: 积分下限
:param b: 积分上限
:param n: 采样次数
:return: 积分估计值, 标准误差
"""
samples = np.random.uniform(a, b, n)
values = f(samples)
estimate = (b - a) * np.mean(values)
std_error = (b - a) * np.std(values) / np.sqrt(n)
# 95%置信区间
ci = (estimate - 1.96 * std_error, estimate + 1.96 * std_error)
return estimate, std_error, ci
def monte_carlo_pi(n=100000):
"""
蒙特卡洛方法计算π
:param n: 采样次数
:return: π的估计值
"""
points = np.random.uniform(-1, 1, (n, 2))
inside = np.sum(points[:, 0]**2 + points[:, 1]**2 <= 1)
return 4 * inside / n
def monte_carlo_option_pricing(S, K, T, r, sigma, option_type='call', n=100000):
"""
蒙特卡洛期权定价
:param S: 标的资产当前价格
:param K: 行权价格
:param T: 到期时间(年)
:param r: 无风险利率
:param sigma: 波动率
:param option_type: 期权类型 ('call' 或 'put')
:param n: 模拟路径数
:return: 期权价格
"""
# 生成随机价格路径(几何布朗运动)
Z = np.random.standard_normal(n)
ST = S * np.exp((r - 0.5 * sigma**2) * T + sigma * np.sqrt(T) * Z)
# 计算期权收益
if option_type == 'call':
payoffs = np.maximum(ST - K, 0)
else:
payoffs = np.maximum(K - ST, 0)
# 贴现到现值
option_price = np.exp(-r * T) * np.mean(payoffs)
std_error = np.exp(-r * T) * np.std(payoffs) / np.sqrt(n)
return option_price, std_error
def importance_sampling_integration(f, p, p_sampler, n=100000):
"""
重要性采样积分
:param f: 被积函数
:param p: 重要性概率密度函数
:param p_sampler: 从p采样的函数
:param n: 采样次数
:return: 积分估计值
"""
samples = p_sampler(n)
values = f(samples) / p(samples)
return np.mean(values)
def plot_convergence(estimates, true_value=None):
"""
绘制蒙特卡洛收敛曲线
:param estimates: 各次估计值序列
:param true_value: 真实值(如果有)
"""
cumulative_mean = np.cumsum(estimates) / np.arange(1, len(estimates) + 1)
plt.figure(figsize=(10, 6))
plt.plot(cumulative_mean, label='Monte Carlo Estimate')
if true_value is not None:
plt.axhline(y=true_value, color='r', linestyle='--', label='True Value')
plt.xlabel('Number of Samples')
plt.ylabel('Estimate')
plt.title('Monte Carlo Convergence')
plt.legend()
plt.show()
```
---
## 2. 排队论 (Queuing Theory)
### 算法介绍
排队论研究服务系统中随机到达、等待和服务的规律。
#### 2.1 基本概念
**排队系统组成**:
- 到达过程:顾客到达的规律
- 服务过程:服务时间的分布
- 服务台数量:并联或串联
- 队列容量:有限或无限
- 排队规则:FCFS、LCFS、优先权等
**Kendall符号**:A/B/c/K/m/Z
- A:到达时间分布(M=指数分布,D=定长,E_k=Erlang,G=一般)
- B:服务时间分布
- c:服务台数量
- K:系统容量(默认∞)
- m:顾客源数量(默认∞)
- Z:服务规则(默认FCFS)
例如:M/M/1表示泊松到达、指数服务、1个服务台。
#### 2.2 M/M/1模型
**参数**:
- $\lambda$:到达率
- $\mu$:服务率
- $\rho = \lambda/\mu$:服务强度($\rho < 1$系统稳定)
**稳态指标**:
- 系统中有n个顾客的概率:$p_n = (1-\rho)\rho^n$
- 平均队长:$L = \frac{\rho}{1-\rho}$
- 平均等待队长:$L_q = \frac{\rho^2}{1-\rho}$
- 平均逗留时间:$W = \frac{1}{\mu - \lambda}$
- 平均等待时间:$W_q = \frac{\lambda}{\mu(\mu - \lambda)}$
#### 2.3 M/M/c模型
c个服务台的并行系统。
**服务强度**:$\rho = \frac{\lambda}{c\mu}$($\rho < 1$)
**稳态概率**:
$$
p_0 = \left[\sum_{k=0}^{c-1} \frac{(c\rho)^k}{k!} + \frac{(c\rho)^c}{c!(1-\rho)}\right]^{-1}
$$
#### 2.4 M/G/1模型
一般服务时间的单服务台系统。
**Pollaczek-Khinchine公式**:
$$
L_q = \frac{\lambda^2 \sigma_s^2 + \rho^2}{2(1-\rho)}
$$
其中$\sigma_s^2$是服务时间的方差。
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 服务系统 | 银行、医院排队 | 随机到达 |
| 通信网络 | 数据包排队 | 缓冲区设计 |
| 交通系统 | 道路交通流 | 容量分析 |
| 生产系统 | 加工中心调度 | 机器配置 |
| 呼叫中心 | 客服配置 | 人员安排 |
### 可视化图表类型
- **状态转移图**:系统状态转移
- **队列长度分布**:队列长度概率
- **等待时间分布**:等待时间概率
- **利用率曲线**:服务台利用率
- **仿真动画**:排队过程动态演示
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Queues | Kleinrock | 1975 | Wiley |
| Fundamentals of Queueing Theory | Gross & Harris | 1998 | Wiley |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
from collections import deque
def mm1_queue_metrics(lambda_rate, mu_rate):
"""
M/M/1排队系统指标计算
:param lambda_rate: 到达率
:param mu_rate: 服务率
:return: 系统性能指标字典
"""
rho = lambda_rate / mu_rate
if rho >= 1:
raise ValueError("系统不稳定,需要lambda < mu")
L = rho / (1 - rho) # 平均队长
Lq = rho**2 / (1 - rho) # 平均等待队长
W = 1 / (mu_rate - lambda_rate) # 平均逗留时间
Wq = lambda_rate / (mu_rate * (mu_rate - lambda_rate)) # 平均等待时间
p0 = 1 - rho # 系统空闲概率
return {
'utilization': rho,
'avg_customers_in_system': L,
'avg_customers_in_queue': Lq,
'avg_time_in_system': W,
'avg_waiting_time': Wq,
'probability_idle': p0
}
def simulate_mm1_queue(lambda_rate, mu_rate, simulation_time=1000, seed=42):
"""
M/M/1排队系统仿真
:param lambda_rate: 到达率
:param mu_rate: 服务率
:param simulation_time: 仿真时间
:param seed: 随机种子
:return: 仿真结果字典
"""
np.random.seed(seed)
# 事件列表:(时间, 类型) 类型:0=到达,1=离开
events = []
customers_served = 0
total_waiting_time = 0
total_service_time = 0
queue_length_history = []
time_history = []
# 初始化
t = 0
queue = deque()
server_busy = False
next_arrival = np.random.exponential(1 / lambda_rate)
next_departure = float('inf')
events.append((next_arrival, 'arrival'))
while t < simulation_time:
if next_arrival < next_departure:
t = next_arrival
# 到达事件
if not server_busy:
server_busy = True
service_time = np.random.exponential(1 / mu_rate)
next_departure = t + service_time
total_service_time += service_time
else:
queue.append(t)
next_arrival = t + np.random.exponential(1 / lambda_rate)
queue_length_history.append(len(queue) + (1 if server_busy else 0))
time_history.append(t)
else:
t = next_departure
# 离开事件
customers_served += 1
if queue:
arrival_time = queue.popleft()
waiting_time = t - arrival_time
total_waiting_time += waiting_time
service_time = np.random.exponential(1 / mu_rate)
next_departure = t + service_time
total_service_time += service_time
else:
server_busy = False
next_departure = float('inf')
queue_length_history.append(len(queue) + (1 if server_busy else 0))
time_history.append(t)
return {
'time': time_history,
'queue_length': queue_length_history,
'avg_waiting_time': total_waiting_time / customers_served if customers_served > 0 else 0,
'avg_service_time': total_service_time / customers_served if customers_served > 0 else 0,
'customers_served': customers_served,
'utilization': total_service_time / t
}
def plot_queue_simulation(simulation_result):
"""绘制排队系统仿真结果"""
plt.figure(figsize=(12, 6))
plt.plot(simulation_result['time'], simulation_result['queue_length'])
plt.xlabel('Time')
plt.ylabel('Number of Customers in System')
plt.title('Queue Length Over Time')
plt.show()
```
---
## 3. 博弈论 (Game Theory)
### 算法介绍
博弈论研究决策主体的行为发生直接相互作用时的决策以及这种决策的均衡问题。
#### 3.1 基本概念
**博弈要素**:
- 局中人(Players)
- 策略(Strategies)
- 收益(Payoffs)
**纳什均衡**:在给定其他玩家策略的情况下,每个玩家的策略都是最优响应。
$$
u_i(s_i^*, s_{-i}^*) \geq u_i(s_i, s_{-i}^*), \quad \forall s_i
$$
#### 3.2 矩阵博弈(两人有限博弈)
**收益矩阵**:
| | 策略B1 | 策略B2 |
|---|-------|-------|
| 策略A1 | $(a_{11}, b_{11})$ | $(a_{12}, b_{12})$ |
| 策略A2 | $(a_{21}, b_{21})$ | $(a_{22}, b_{22})$ |
**纯策略纳什均衡**:寻找互为最优响应的策略组合。
**混合策略**:以一定概率随机选择策略。
玩家A的混合策略:$p = (p, 1-p)$
玩家B的混合策略:$q = (q, 1-q)$
**期望收益**:
$$
E_A(p, q) = p \cdot q \cdot a_{11} + p \cdot (1-q) \cdot a_{12} + (1-p) \cdot q \cdot a_{21} + (1-p) \cdot (1-q) \cdot a_{22}
$$
#### 3.3 囚徒困境
经典博弈论例子。
| | 沉默 | 坦白 |
|---|-----|-----|
| 沉默 | (-1, -1) | (-10, 0) |
| 坦白 | (0, -10) | (-5, -5) |
纳什均衡:(坦白, 坦白),帕累托最优:(沉默, 沉默)
#### 3.4 零和博弈
一方收益等于另一方损失。
**最小最大定理**:
$$
\max_{x} \min_{y} u(x, y) = \min_{y} \max_{x} u(x, y)
$$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 经济分析 | 寡头竞争 | 策略互动 |
| 拍卖设计 | 拍卖机制设计 | 信息不对称 |
| 谈判分析 | 谈判策略 | 利益分配 |
| 军事对抗 | 战略决策 | 对抗性 |
| 资源分配 | 资源竞争 | 多主体决策 |
### 可视化图表类型
- **收益矩阵图**:策略收益可视化
- **反应函数图**:最优响应曲线
- **混合策略图**:混合策略空间
- **博弈树图**:扩展型博弈
- **均衡点图**:纳什均衡位置
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Theory of Games and Economic Behavior | von Neumann & Morgenstern | 1944 | Princeton University Press |
| Game Theory | Fudenberg & Tirole | 1991 | MIT Press |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
from itertools import product
def find_pure_nash_equilibrium(payoff_matrix_a, payoff_matrix_b):
"""
寻找纯策略纳什均衡
:param payoff_matrix_a: 玩家A的收益矩阵
:param payoff_matrix_b: 玩家B的收益矩阵
:return: 纳什均衡列表
"""
n_actions_a = payoff_matrix_a.shape[0]
n_actions_b = payoff_matrix_a.shape[1]
best_responses_a = np.zeros_like(payoff_matrix_a, dtype=bool)
best_responses_b = np.zeros_like(payoff_matrix_b, dtype=bool)
# 计算A的最优响应
for j in range(n_actions_b):
max_payoff = payoff_matrix_a[:, j].max()
best_responses_a[:, j] = (payoff_matrix_a[:, j] == max_payoff)
# 计算B的最优响应
for i in range(n_actions_a):
max_payoff = payoff_matrix_b[i, :].max()
best_responses_b[i, :] = (payoff_matrix_b[i, :] == max_payoff)
# 找出纳什均衡(互为最优响应)
nash_equilibria = []
for i, j in product(range(n_actions_a), range(n_actions_b)):
if best_responses_a[i, j] and best_responses_b[i, j]:
nash_equilibria.append(((i, j), (payoff_matrix_a[i, j], payoff_matrix_b[i, j])))
return nash_equilibria
def solve_zero_sum_game(payoff_matrix):
"""
求解零和博弈(线性规划方法)
:param payoff_matrix: 行玩家的收益矩阵
:return: 混合策略纳什均衡, 博弈值
"""
from scipy.optimize import linprog
m, n = payoff_matrix.shape
# 将最大化问题转换为最小化问题
c = np.ones(m + 1)
c[-1] = 0 # v的系数
# 约束条件矩阵
A_ub = np.zeros((n, m + 1))
A_ub[:, :m] = -payoff_matrix.T # 约束:Σ p_ij * x_i >= v
A_ub[:, -1] = 1
b_ub = np.zeros(n)
# 等式约束:概率和为1
A_eq = np.zeros((1, m + 1))
A_eq[0, :m] = 1
b_eq = np.array([1])
# 非负约束
bounds = [(0, None)] * (m + 1)
bounds[-1] = (None, None) # v可以是任意值
result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, bounds=bounds)
if result.success:
strategy = result.x[:m]
value = result.x[-1]
return strategy, value
else:
return None, None
def plot_reaction_functions(payoff_matrix_a, payoff_matrix_b):
"""
绘制反应函数图(适用于2×2博弈)
:param payoff_matrix_a: 玩家A的收益矩阵 shape (2,2),行=A的纯策略,列=B的纯策略
:param payoff_matrix_b: 玩家B的收益矩阵 shape (2,2)
"""
# 计算玩家A的最优响应 BR_A(q):给定B选择策略1的概率 q,A选策略1/2的期望收益
q = np.linspace(0, 1, 200)
# A选策略1的期望收益 = q*A11 + (1-q)*A12;选策略2 = q*A21 + (1-q)*A22
E_A1 = q * payoff_matrix_a[0, 0] + (1 - q) * payoff_matrix_a[0, 1]
E_A2 = q * payoff_matrix_a[1, 0] + (1 - q) * payoff_matrix_a[1, 1]
# A的最优响应:E_A1 >= E_A2 时选策略1(概率1),否则选策略2(概率0)
BR_A = (E_A1 >= E_A2).astype(float)
# 玩家B的最优响应 BR_B(p):给定A选策略1的概率 p
p = np.linspace(0, 1, 200)
E_B1 = p * payoff_matrix_b[0, 0] + (1 - p) * payoff_matrix_b[1, 0] # B选策略1
E_B2 = p * payoff_matrix_b[0, 1] + (1 - p) * payoff_matrix_b[1, 1] # B选策略2
BR_B = (E_B1 >= E_B2).astype(float)
plt.figure(figsize=(8, 8))
plt.plot(q, BR_A, 'r-', linewidth=2, label='Player A Best Response')
plt.plot(BR_B, p, 'b-', linewidth=2, label='Player B Best Response')
plt.xlabel('Probability of Player A choosing Strategy 1')
plt.ylabel('Probability of Player B choosing Strategy 1')
plt.title('Reaction Functions')
plt.legend()
plt.xlim(0, 1)
plt.ylim(0, 1)
plt.grid(alpha=0.3)
plt.show()
# 返回纯策略纳什均衡(反应函数交点,即双方同时最优响应的策略组合)
nash = []
for i in range(2):
for j in range(2):
# 检查 (i,j) 是否双方最优响应
if (payoff_matrix_a[i, j] >= payoff_matrix_a[1 - i, j] and
payoff_matrix_b[i, j] >= payoff_matrix_b[i, 1 - j]):
nash.append((i, j))
return nash
```
---
## 4. 元胞自动机 (Cellular Automata, CA)
### 算法介绍
元胞自动机是离散动力系统,由元胞空间、状态集、邻域和演化规则组成。
#### 4.1 基本要素
**元胞空间**:规则的网格(一维、二维)
**状态集**:有限状态集,如$\{0, 1\}$
**邻域**:
- Von Neumann邻域:上下左右4个邻居
- Moore邻域:周围8个邻居
**演化规则**:$S_i^{t+1} = f(S_{N(i)}^t)$
其中$S_i^t$是元胞$i$在时刻$t$的状态,$N(i)$是元胞$i$的邻域。
#### 4.2 初等元胞自动机(一维)
256种规则,由规则号8位二进制决定。
**Wolfram分类**:
- Class I:演化到均匀状态
- Class II:演化到周期结构
- Class III:混沌行为
- Class IV:复杂结构(如Rule 110)
#### 4.3 生命游戏(Game of Life)
Conway的经典二维CA。
**规则**:
1. 活细胞周围有2-3个活邻居则存活
2. 死细胞周围恰好有3个活邻居则复活
3. 其他情况细胞死亡
#### 4.4 交通流元胞自动机
**Nagel-Schreckenberg模型**:
步骤:
1. 加速:$v_i \to \min(v_i + 1, v_{max})$
2. 减速:$v_i \to \min(v_i, gap_i)$
3. 随机慢化:以概率$p$,$v_i \to \max(v_i - 1, 0)$
4. 移动:$x_i \to x_i + v_i$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 复杂系统 | 种群演化 | 局部交互 |
| 交通流 | 交通拥堵模拟 | 离散空间 |
| 流行病 | 疾病传播 | 接触传播 |
| 森林火灾 | 火灾蔓延 | 邻域传播 |
| 社会动态 | 舆论传播 | 局部影响 |
### 可视化图表类型
- **时空图**:一维CA演化(时间向下)
- **状态图**:二维CA各时刻状态
- **统计图**:活细胞数随时间变化
- **相图**:参数空间中的行为
- **动画**:演化过程动画
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| A New Kind of Science | Wolfram | 2002 | Wolfram Media |
| University Physics with Modern Physics | Young & Freedman | 2016 | Pearson |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.animation as animation
def elementary_ca(rule_number, n_cells=100, n_steps=100, initial_state=None):
"""
初等元胞自动机
:param rule_number: 规则号 (0-255)
:param n_cells: 元胞数量
:param n_steps: 演化步数
:param initial_state: 初始状态,None则中间为1
:return: 演化历史矩阵
"""
# 解析规则
rule = np.array([int(b) for b in f'{rule_number:08b}'])
# 初始化
if initial_state is None:
state = np.zeros(n_cells, dtype=int)
state[n_cells // 2] = 1
else:
state = np.array(initial_state, dtype=int)
history = [state.copy()]
for _ in range(n_steps - 1):
new_state = np.zeros_like(state)
for i in range(n_cells):
# 获取邻居状态(周期边界)
left = state[(i - 1) % n_cells]
center = state[i]
right = state[(i + 1) % n_cells]
# 将3位二进制转为索引
pattern = left * 4 + center * 2 + right
new_state[i] = rule[7 - pattern]
state = new_state
history.append(state.copy())
return np.array(history)
def game_of_life(n_rows=50, n_cols=50, n_steps=100, initial_density=0.2):
"""
生命游戏
:param n_rows: 行数
:param n_cols: 列数
:param n_steps: 演化步数
:param initial_density: 初始活细胞密度
:return: 演化历史
"""
# 随机初始化
state = (np.random.random((n_rows, n_cols)) < initial_density).astype(int)
history = [state.copy()]
for _ in range(n_steps - 1):
new_state = state.copy()
# 计算邻居(8个方向)
for i in range(n_rows):
for j in range(n_cols):
# 统计周围活邻居数
neighbors = 0
for di in [-1, 0, 1]:
for dj in [-1, 0, 1]:
if di == 0 and dj == 0:
continue
ni, nj = (i + di) % n_rows, (j + dj) % n_cols
neighbors += state[ni, nj]
# 应用规则
if state[i, j] == 1:
if neighbors < 2 or neighbors > 3:
new_state[i, j] = 0
else:
if neighbors == 3:
new_state[i, j] = 1
state = new_state
history.append(state.copy())
return np.array(history)
def traffic_ca(n_cells=100, n_steps=200, density=0.3, v_max=5, p_slow=0.1):
"""
Nagel-Schreckenberg交通流模型
:param n_cells: 道路长度
:param n_steps: 演化步数
:param density: 车辆密度
:param v_max: 最大速度
:param p_slow: 随机慢化概率
:return: 车辆位置历史
"""
# 初始化车辆位置
n_cars = int(n_cells * density)
positions = np.random.choice(n_cells, n_cars, replace=False)
positions.sort()
velocities = np.zeros(n_cars, dtype=int)
history = [positions.copy()]
for _ in range(n_steps):
# 计算车间距
gaps = np.diff(np.concatenate([positions, [positions[0] + n_cells]])) - 1
gaps[-1] = (positions[0] + n_cells - positions[-1] - 1)
# 1. 加速
velocities = np.minimum(velocities + 1, v_max)
# 2. 减速
velocities = np.minimum(velocities, gaps)
# 3. 随机慢化
random_slow = np.random.random(n_cars) < p_slow
velocities[random_slow] = np.maximum(velocities[random_slow] - 1, 0)
# 4. 移动
positions = (positions + velocities) % n_cells
history.append(positions.copy())
return np.array(history)
def plot_ca_history(history, title="Cellular Automaton"):
"""绘制CA演化历史"""
plt.figure(figsize=(10, 6))
plt.imshow(history, cmap='binary', aspect='auto')
plt.xlabel('Cell')
plt.ylabel('Time Step')
plt.title(title)
plt.colorbar()
plt.tight_layout()
plt.show()
def animate_game_of_life(history, interval=100):
"""生命游戏动画"""
fig, ax = plt.subplots(figsize=(8, 8))
im = ax.imshow(history[0], cmap='binary')
ax.set_title('Game of Life')
ax.axis('off')
def update(frame):
im.set_array(history[frame])
ax.set_title(f'Game of Life - Step {frame}')
return [im]
ani = animation.FuncAnimation(fig, update, frames=len(history),
interval=interval, blit=True)
plt.show()
return ani
```
---
## 5. 马尔科夫链 (Markov Chain)
### 算法介绍
马尔科夫链是状态空间中从一个状态转移到另一个状态的随机过程。
#### 5.1 基本概念
**马尔科夫性质**:
$$
P(X_{t+1} = x_{t+1} | X_t = x_t, X_{t-1} = x_{t-1}, \ldots) = P(X_{t+1} = x_{t+1} | X_t = x_t)
$$
**转移概率矩阵**:
$$
P = \begin{bmatrix}
p_{11} & p_{12} & \cdots & p_{1n} \\
p_{21} & p_{22} & \cdots & p_{2n} \\
\vdots & \vdots & \ddots & \vdots \\
p_{n1} & p_{n2} & \cdots & p_{nn}
\end{bmatrix}
$$
其中$p_{ij} = P(X_{t+1} = j | X_t = i)$,满足$\sum_{j} p_{ij} = 1$。
#### 5.2 状态演化
**初始分布**:$\pi_0$(行向量)
**n步后分布**:
$$
\pi_n = \pi_0 P^n
$$
#### 5.3 稳态分布
若马尔科夫链是不可约、非周期的,则存在稳态分布$\pi$满足:
$$
\pi P = \pi, \quad \sum_i \pi_i = 1
$$
等价于求解特征值1的左特征向量。
#### 5.4 分类
**不可约**:任意状态可达任意状态
**周期性**:状态只在某些时间步返回
**常返性**:状态以概率1返回
**吸收态**:一旦到达则永不离开($p_{ii} = 1$)
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 随机过程 | 系统状态演化 | 状态转移 |
| 金融建模 | 信用评级转移 | 状态预测 |
| 供应链 | 库存状态 | 库存管理 |
| 推荐系统 | 用户兴趣 | 兴趣演化 |
| NLP | 文本生成 | 词序列 |
| 遗传算法 | 种群演化 | 状态搜索 |
### 可视化图表类型
- **状态转移图**:状态及转移
- **时间序列图**:状态随时间变化
- **稳态热力图**:稳态概率分布
- **演化树图**:可能的状态路径
- **首次到达分布**:首次到达时间分布
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Markov Chains | Norris | 1997 | Cambridge University Press |
| Introduction to Probability Models | Ross | 2014 | Academic Press |
### 代码实现要点
```python
import numpy as np
import matplotlib.pyplot as plt
def markov_chain_evolution(initial_dist, transition_matrix, n_steps):
"""
马尔科夫链演化
:param initial_dist: 初始分布 (行向量)
:param transition_matrix: 转移概率矩阵
:param n_steps: 演化步数
:return: 各时刻分布历史
"""
dist = initial_dist.copy()
history = [dist.copy()]
for _ in range(n_steps):
dist = dist @ transition_matrix
history.append(dist.copy())
return np.array(history)
def find_steady_state(transition_matrix):
"""
求解稳态分布
:param transition_matrix: 转移概率矩阵
:return: 稳态分布
"""
# 求解特征值问题
eigenvalues, eigenvectors = np.linalg.eig(transition_matrix.T)
# 找特征值为1的特征向量
idx = np.argmax(eigenvalues.real)
steady_state = eigenvectors[:, idx].real
steady_state = steady_state / steady_state.sum()
return steady_state
def simulate_markov_chain(initial_state, transition_matrix, n_steps, seed=42):
"""
模拟马尔科夫链路径
:param initial_state: 初始状态
:param transition_matrix: 转移概率矩阵
:param n_steps: 模拟步数
:param seed: 随机种子
:return: 状态序列
"""
np.random.seed(seed)
n_states = transition_matrix.shape[0]
states = [initial_state]
for _ in range(n_steps):
current = states[-1]
next_state = np.random.choice(n_states, p=transition_matrix[current])
states.append(next_state)
return np.array(states)
def classify_states(transition_matrix):
"""
状态分类
:param transition_matrix: 转移概率矩阵
:return: 状态类型字典
"""
n_states = transition_matrix.shape[0]
classification = {}
for i in range(n_states):
# 检查吸收态
if np.isclose(transition_matrix[i, i], 1.0):
classification[i] = 'absorbing'
else:
# 进一步分类需要可达性分析
classification[i] = 'transient'
return classification
def calculate_absorption_time(transition_matrix):
"""
计算吸收时间(对于吸收链)
:param transition_matrix: 转移概率矩阵
:return: 吸收时间的期望矩阵
"""
# 重排矩阵,使吸收态在前
# P = [[I, 0], [R, Q]]
# 吸收时间期望矩阵:N = (I - Q)^(-1)
# 期望吸收时间:t = N * 1
n_states = transition_matrix.shape[0]
absorbing = [i for i in range(n_states) if np.isclose(transition_matrix[i, i], 1.0)]
if not absorbing:
return None
# 分离Q和R
non_absorbing = [i for i in range(n_states) if i not in absorbing]
Q = transition_matrix[np.ix_(non_absorbing, non_absorbing)]
# 计算期望吸收时间
I = np.eye(len(non_absorbing))
N = np.linalg.inv(I - Q)
t = N.sum(axis=1)
return t, N
def plot_markov_chain_evolution(history, state_names=None):
"""绘制马尔科夫链演化"""
plt.figure(figsize=(12, 6))
n_steps, n_states = history.shape
for i in range(n_states):
label = state_names[i] if state_names else f'State {i}'
plt.plot(history[:, i], label=label, marker='o')
plt.xlabel('Time Step')
plt.ylabel('Probability')
plt.title('Markov Chain Evolution')
plt.legend()
plt.show()
```
---
## 6. 微分方程建模 (Differential Equation Modeling)
### 算法介绍
微分方程用于描述连续系统的动态变化规律。
#### 6.1 常微分方程
**一阶ODE**:
$$
\frac{dy}{dt} = f(t, y)
$$
**高阶ODE**:转化为一阶方程组。
**数值解法**:
**Euler方法**:
$$
y_{n+1} = y_n + h f(t_n, y_n)
$$
**Runge-Kutta方法(RK4)**:
$$
\begin{aligned}
k_1 &= h f(t_n, y_n) \\
k_2 &= h f(t_n + h/2, y_n + k_1/2) \\
k_3 &= h f(t_n + h/2, y_n + k_2/2) \\
k_4 &= h f(t_n + h, y_n + k_3) \\
y_{n+1} &= y_n + \frac{1}{6}(k_1 + 2k_2 + 2k_3 + k_4)
\end{aligned}
$$
#### 6.2 典型模型
**Malthus模型(指数增长)**:
$$
\frac{dN}{dt} = rN
$$
**Logistic模型**:
$$
\frac{dN}{dt} = rN(1 - \frac{N}{K})
$$
**Lotka-Volterra模型(捕食者-猎物)**:
$$
\begin{aligned}
\frac{dx}{dt} &= \alpha x - \beta xy \\
\frac{dy}{dt} &= \delta xy - \gamma y
\end{aligned}
$$
**SIR模型(传染病)**:
$$
\begin{aligned}
\frac{dS}{dt} &= -\beta SI \\
\frac{dI}{dt} &= \beta SI - \gamma I \\
\frac{dR}{dt} &= \gamma I
\end{aligned}
$$
### 适用范围
| 题型类型 | 典型问题 | 特征 |
|---------|---------|------|
| 种群动态 | 物种数量变化 | 连续变化 |
| 传染病传播 | 疫情发展 | 状态转移 |
| 化学反应 | 反应动力学 | 浓度变化 |
| 物理系统 | 运动、热传导 | 连续系统 |
| 经济模型 | 经济增长 | 连续变量 |
### 可视化图表类型
- **时间序列图**:变量随时间变化
- **相图**:变量间关系
- **向量场图**:方向场
- **解曲线图**:多条解曲线
- **参数敏感度图**:参数影响
### 关键文献
| 论文名称 | 作者 | 年份 | 来源 |
|---------|------|------|------|
| Elementary Differential Equations | Boyce & DiPrima | 2012 | Wiley |
| Nonlinear Dynamics and Chaos | Strogatz | 2015 | CRC Press |
### 代码实现要点
```python
import numpy as np
from scipy.integrate import odeint, solve_ivp
import matplotlib.pyplot as plt
def solve_ode_euler(f, y0, t_span, h=0.01):
"""
Euler方法求解ODE
:param f: 微分方程函数 dy/dt = f(t, y)
:param y0: 初始值
:param t_span: 时间跨度 (t_start, t_end)
:param h: 步长
:return: 解 (t, y)
"""
t_start, t_end = t_span
t = np.arange(t_start, t_end + h, h)
y = np.zeros((len(t), len(y0)))
y[0] = y0
for i in range(1, len(t)):
y[i] = y[i-1] + h * f(t[i-1], y[i-1])
return t, y
def solve_ode_rk4(f, y0, t_span, h=0.01):
"""
Runge-Kutta 4阶方法
:param f: 微分方程函数 dy/dt = f(t, y)
:param y0: 初始值
:param t_span: 时间跨度
:param h: 步长
:return: 解 (t, y)
"""
t_start, t_end = t_span
t = np.arange(t_start, t_end + h, h)
y = np.zeros((len(t), len(y0)))
y[0] = y0
for i in range(1, len(t)):
k1 = h * f(t[i-1], y[i-1])
k2 = h * f(t[i-1] + h/2, y[i-1] + k1/2)
k3 = h * f(t[i-1] + h/2, y[i-1] + k2/2)
k4 = h * f(t[i-1] + h, y[i-1] + k3)
y[i] = y[i-1] + (k1 + 2*k2 + 2*k3 + k4) / 6
return t, y
def sir_model(t, y, beta, gamma):
"""SIR传染病模型"""
S, I, R = y
N = S + I + R
dSdt = -beta * S * I / N
dIdt = beta * S * I / N - gamma * I
dRdt = gamma * I
return [dSdt, dIdt, dRdt]
def solve_sir_model(S0, I0, R0, beta, gamma, t_span, t_eval=None):
"""
求解SIR模型
:param S0, I0, R0: 初始值
:param beta: 传染率
:param gamma: 恢复率
:param t_span: 时间跨度
:param t_eval: 评估时间点
:return: 解
"""
y0 = [S0, I0, R0]
sol = solve_ivp(lambda t, y: sir_model(t, y, beta, gamma),
t_span, y0, t_eval=t_eval)
return sol.t, sol.y
def lotka_volterra(t, y, alpha, beta, delta, gamma):
"""Lotka-Volterra捕食者-猎物模型"""
x, y = y # x: 猎物, y: 捕食者
dxdt = alpha * x - beta * x * y
dydt = delta * x * y - gamma * y
return [dxdt, dydt]
def solve_lotka_volterra(x0, y0, alpha, beta, delta, gamma, t_span, t_eval=None):
"""求解Lotka-Volterra模型"""
y0 = [x0, y0]
sol = solve_ivp(lambda t, y: lotka_volterra(t, y, alpha, beta, delta, gamma),
t_span, y0, t_eval=t_eval)
return sol.t, sol.y
def plot_phase_portrait(sol_y, labels=None, title="Phase Portrait"):
"""绘制相图"""
plt.figure(figsize=(8, 8))
plt.plot(sol_y[0], sol_y[1])
plt.xlabel(labels[0] if labels else 'x')
plt.ylabel(labels[1] if labels else 'y')
plt.title(title)
plt.show()
def plot_ode_solution(t, y, labels=None, title="ODE Solution"):
"""绘制ODE解"""
plt.figure(figsize=(12, 6))
for i in range(y.shape[0]):
label = labels[i] if labels else f'Variable {i}'
plt.plot(t, y[i], label=label)
plt.xlabel('Time')
plt.ylabel('Value')
plt.title(title)
plt.legend()
plt.show()
```
---
## 综合类算法选择指南
### 按问题类型选择
| 问题类型 | 推荐算法 | 说明 |
|---------|---------|------|
| 随机模拟 | 蒙特卡洛 | 随机采样 |
| 等待服务 | 排队论 | 到离过程 |
| 策略互动 | 博弈论 | 决策分析 |
| 局部交互 | 元胞自动机 | 复杂系统 |
| 状态演化 | 马尔科夫链 | 随机过程 |
| 连续变化 | 微分方程 | 动态系统 |
### 按系统特征选择
| 系统特征 | 推荐算法 |
|---------|---------|
| 离散状态 | CA、马尔科夫链 |
| 连续状态 | 微分方程 |
| 随机性 | 蒙特卡洛、马尔科夫链 |
| 确定性 | 微分方程、CA |
| 空间局部 | CA |
| 时间记忆 | 非马尔科夫过程 |
### 按数据需求选择
| 数据情况 | 推荐算法 |
|---------|---------|
| 仅有参数 | 微分方程、博弈论 |
| 需要模拟 | 蒙特卡洛、CA |
| 历史序列 | 马尔科夫链 |
| 实际观测 | 排队论参数估计 |
---
## 参考文献
1. Hammersley, J. M., & Handscomb, D. C. (1964). *Monte Carlo Methods*. Methuen.
2. Kleinrock, L. (1975). *Queueing Systems, Volume 1: Theory*. Wiley.
3. von Neumann, J., & Morgenstern, O. (1944). *Theory of Games and Economic Behavior*. Princeton University Press.
4. Wolfram, S. (2002). *A New Kind of Science*. Wolfram Media.
5. Norris, J. R. (1997). *Markov Chains*. Cambridge University Press.
6. Boyce, W. E., & DiPrima, R. C. (2012). *Elementary Differential Equations and Boundary Value Problems* (10th ed.). Wiley.
7. Strogatz, S. H. (2015). *Nonlinear Dynamics and Chaos: With Applications to Physics, Biology, Chemistry, and Engineering* (2nd ed.). CRC Press.
8. Ross, S. M. (2014). *Introduction to Probability Models* (11th ed.). Academic Press.
Related skills
| Skill | Stars | Updated | Works with | Status | Install |
|---|---|---|---|---|---|
| reverse-engineer-anythingmorluto/reaReverse engineer native, managed, Electron/JavaScript, packaged, firmware, and browser targets with REA, and build agent environments (AgentEnv bundles) of web applications from a live instance or a capture, and of Linux desktop apps with a task from a request. Use shipped-artifact or requested runtime evidence to explain features, compare versions, decompile code, or guide a reconstruction. Skip REA for ordinary source-repository architecture analysis. | Stars: 472k | Updated | Claude CodeCodex | Verified | Install |
| diagnosing-superpowersobra/superpowersUse when a superpowers session went wrong and your human partner wants to know why — repeated work, ignored plans, stumbles, poor results, a skill that didn't fire, "it took too long", "why is it so expensive", "what is it doing" — or wants to build a bug report for the superpowers maintainers, for the current session or a past one identified by id or path, on any harness. | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |
| dispatching-parallel-agentsobra/superpowersUse when facing 2+ independent tasks that can be worked on without shared state or sequential dependencies | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |
| executing-plansobra/superpowersUse when executing an implementation plan in the current session as the implementer yourself — your human partner chose inline execution, or no subagent tool is available | Stars: 323k | Updated | Claude CodeCodex | Verified | Install |