127 lines
4.1 KiB
Markdown
127 lines
4.1 KiB
Markdown
|
以下是针对实验内容的详细指导和实现建议：
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
### 一、实验目的
|
|||
|
|
1. **最长公共子序列问题（LCS）**
|
|||
|
|
理解如何通过动态规划求解两个序列的最长公共子序列，熟悉其算法原理及应用场景。
|
|||
|
|
2. **最小编辑距离（Levenshtein Distance）**
|
|||
|
|
掌握最小编辑距离的定义及动态规划实现，理解其在字符串相似度计算中的实际应用。
|
|||
|
|
3. **动态规划思想**
|
|||
|
|
学习将复杂问题分解为子问题并通过递推关系逐步求解。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
### 二、实验环境
|
|||
|
|
- **操作系统**：Windows 或 Linux
|
|||
|
|
- **编程语言**：Python 3.x
|
|||
|
|
- **开发工具**：推荐使用 PyCharm、Jupyter Notebook 或 Sublime Text。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
### 三、实验内容
|
|||
|
|
#### **1. 最长公共子序列问题（LCS）**
|
|||
|
|
**基本原理：**
|
|||
|
|
给定两个字符串 \( X \) 和 \( Y \)，找到它们的最长公共子序列。动态规划的核心是构建一个二维表 \( dp \)，其中 \( dp[i][j] \) 表示 \( X[0:i] \) 和 \( Y[0:j] \) 的最长公共子序列长度。
|
|||
|
|
|
|||
|
|
**算法步骤：**
|
|||
|
|
1. 初始化二维表 \( dp \)。
|
|||
|
|
2. 遍历 \( X \) 和 \( Y \)，按以下规则更新 \( dp[i][j] \)：
|
|||
|
|
- 若 \( X[i-1] == Y[j-1] \)：\( dp[i][j] = dp[i-1][j-1] + 1 \)。
|
|||
|
|
- 否则 \( dp[i][j] = \max(dp[i-1][j], dp[i][j-1]) \)。
|
|||
|
|
3. 最后，\( dp[m][n] \) 为结果，其中 \( m, n \) 分别为 \( X \) 和 \( Y \) 的长度。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
#### **2. 最小编辑距离**
|
|||
|
|
**基本原理：**
|
|||
|
|
计算将字符串 \( A \) 转换为 \( B \) 的最小操作次数。允许的操作包括插入、删除和替换。
|
|||
|
|
|
|||
|
|
**算法步骤：**
|
|||
|
|
1. 构建一个二维表 \( dp \)，\( dp[i][j] \) 表示将 \( A[0:i] \) 转换为 \( B[0:j] \) 的最小操作数。
|
|||
|
|
2. 初始化边界条件：
|
|||
|
|
- \( dp[i][0] = i \)（全删）。
|
|||
|
|
- \( dp[0][j] = j \)（全插）。
|
|||
|
|
3. 遍历 \( A \) 和 \( B \)，按以下规则更新 \( dp[i][j] \)：
|
|||
|
|
- 若 \( A[i-1] == B[j-1] \)：\( dp[i][j] = dp[i-1][j-1] \)。
|
|||
|
|
- 否则 \( dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) \)。
|
|||
|
|
4. \( dp[m][n] \) 即为结果，其中 \( m, n \) 分别为 \( A \) 和 \( B \) 的长度。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
### 四、实验报告要求
|
|||
|
|
1. **基本思想说明**
|
|||
|
|
详细描述 LCS 和最小编辑距离的动态规划思想，包括状态定义和状态转移方程。
|
|||
|
|
2. **源码**
|
|||
|
|
提供清晰、注释详尽的 Python 实现。
|
|||
|
|
3. **算法分析**
|
|||
|
|
- 时间复杂度：分析循环嵌套次数。
|
|||
|
|
- 空间复杂度：分析二维表的空间占用及优化可能。
|
|||
|
|
4. **实验结果截图**
|
|||
|
|
展示控制台输出结果及二维表状态。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
### 五、文件提交说明
|
|||
|
|
1. **文件夹格式：**
|
|||
|
|
学号+姓名（如 "2024123456张三"）。
|
|||
|
|
2. **文件内容：**
|
|||
|
|
- 实验报告（Word 或 PDF 格式，命名为 `实验报告_学号_姓名`）。
|
|||
|
|
- 可运行的 Python 源代码文件（如 `lcs_and_edit_distance.py`）。
|
|||
|
|
3. **上传路径：**
|
|||
|
|
**上电云盘** -> **课程目录** -> **20241202 文件夹**。
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
以下为代码示例：
|
|||
|
|
|
|||
|
|
#### **最长公共子序列**
|
|||
|
|
```python
|
|||
|
|
def longest_common_subsequence(X, Y):
|
|||
|
|
m, n = len(X), len(Y)
|
|||
|
|
dp = [[0] * (n + 1) for _ in range(m + 1)]
|
|||
|
|
|
|||
|
|
for i in range(1, m + 1):
|
|||
|
|
for j in range(1, n + 1):
|
|||
|
|
if X[i - 1] == Y[j - 1]:
|
|||
|
|
dp[i][j] = dp[i - 1][j - 1] + 1
|
|||
|
|
else:
|
|||
|
|
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
|
|||
|
|
|
|||
|
|
return dp[m][n]
|
|||
|
|
|
|||
|
|
# Example
|
|||
|
|
X = "ABCBDAB"
|
|||
|
|
Y = "BDCAB"
|
|||
|
|
print("LCS Length:", longest_common_subsequence(X, Y))
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
#### **最小编辑距离**
|
|||
|
|
```python
|
|||
|
|
def min_edit_distance(A, B):
|
|||
|
|
m, n = len(A), len(B)
|
|||
|
|
dp = [[0] * (n + 1) for _ in range(m + 1)]
|
|||
|
|
|
|||
|
|
for i in range(m + 1):
|
|||
|
|
dp[i][0] = i
|
|||
|
|
for j in range(n + 1):
|
|||
|
|
dp[0][j] = j
|
|||
|
|
|
|||
|
|
for i in range(1, m + 1):
|
|||
|
|
for j in range(1, n + 1):
|
|||
|
|
if A[i - 1] == B[j - 1]:
|
|||
|
|
dp[i][j] = dp[i - 1][j - 1]
|
|||
|
|
else:
|
|||
|
|
dp[i][j] = 1 + min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1])
|
|||
|
|
|
|||
|
|
return dp[m][n]
|
|||
|
|
|
|||
|
|
# Example
|
|||
|
|
A = "kitten"
|
|||
|
|
B = "sitting"
|
|||
|
|
print("Minimum Edit Distance:", min_edit_distance(A, B))
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
祝你实验顺利完成！如果有疑问，可以随时联系我。
|