logo
  • write-homewrite-home-active首页
  • icon-chaticon-chat-activeAI 智能助手
  • icon-pluginicon-plugin-active浏览器插件
  • icon-subjecticon-subject-active学科题目
  • icon-uploadicon-upload-active上传题库
  • 更多功能
  • icon-appicon-app-active手机APP
首页
/
计算机
题目

2.[简答题]若序列X=(B,C,A,D,B,C,D),Y=(A,C,B,A,B,D,C,D),利用动态规划算法找出X和Y 的最长公共子序列。利用c[i][j]和b[i][j]记录问题最优值和构造问题最优解。

2.[简答题]若序列X={B,C,A,D,B,C,D},Y={A,C,B,A,B,D,C,D},利用动态规划算法找出X和Y 的最长公共子序列。利用c[i][j]和b[i][j]记录问题最优值和构造问题最优解。

题目解答

答案

根据动态规划,构建 $ c[i][j] $ 表如下: ``` A C B A B D C D 0 0 0 0 0 0 0 0 0 B 0 0 0 1 1 1 1 1 1 C 0 0 1 1 1 1 1 2 2 A 0 1 1 1 2 2 2 2 2 D 0 1 1 1 2 2 3 3 3 B 0 1 1 2 2 3 3 3 3 C 0 1 2 2 2 3 3 4 4 D 0 1 2 2 2 3 4 4 5 ``` 回溯路径: 1. $ c[7][8] = 5 $,$ X[7] = Y[8] = D $。 2. $ c[6][7] = 4 $,$ X[6] = Y[7] = C $。 3. $ c[5][6] = 3 $,$ X[5] = Y[6] = D $。 4. $ c[4][5] = 2 $,$ X[4] = Y[5] = B $。 5. $ c[3][4] = 2 $,$ X[3] = Y[4] = A $。 6. $ c[2][3] = 1 $,$ X[2] = Y[3] = C $。 7. $ c[1][2] = 1 $,$ X[1] = Y[2] = B $。 最终,LCS为:$ B, C, A, B, D $。 答案:$ B, C, A, B, D $(或 $ B, C, A, D, C $ 等,长度均为5)。

解析

本题考查动态规划算法在求解最长公共子序列(LCS)问题中的应用。解题思路是通过构建一个二维数组 $c[i][j]$ 来记录序列 $X$ 的前 $i$ 个元素和序列 $Y$ 的前 $j$ 个元素的最长公共子序列的长度,同时构建另一个二维数组 $b[i][j]$ 来记录在构建 $c[i][j]$ 时的决策信息,以便后续回溯构造最长公共子序列。

1. 初始化

设序列 $X = \{x_1, x_2, \cdots, x_m\}$,序列 $Y = \{y_1, y_2, \cdots, y_n\}$,这里 $m = 7$,$n = 8$。
初始化 $c[i][0] = 0$($0 \leq i \leq m$)和 $c[0][j] = 0$($0 \leq j \leq n$),这表示当其中一个序列为空时,最长公共子序列的长度为 0。

2. 填充 $c[i][j]$ 表

根据以下递推公式填充 $c[i][j]$ 表:
$c[i][j] = \begin{cases}c[i - 1][j - 1] + 1, & \text{if } x_i = y_j \\\max(c[i - 1][j], c[i][j - 1]), & \text{if } x_i \neq y_j\end{cases}$
具体计算过程如下:

  • 当 $i = 1$,$x_1 = B$:
    • 对于 $j = 1$,$y_1 = A$,$x_1 \neq y_1$,$c[1][1] = \max(c[0][1], c[1][0]) = 0$。
    • 对于 $j = 2$,$y_2 = C$,$x_1 \neq y_2$,$c[1][2] = \max(c[0][2], c[1][1]) = 0$。
    • 以此类推,得到 $c[1][j]$($1 \leq j \leq 8$)的值。
  • 当 $i = 2$,$x_2 = C$:
    • 对于 $j = 1$,$y_1 = A$,$x_2 \neq y_1$,$c[2][1] = \max(c[1][1], c[2][0]) = 0$。
    • 对于 $j = 2$,$y_2 = C$,$x_2 = y_2$,$c[2][2] = c[1][1] + 1 = 1$。
    • 以此类推,得到 $c[2][j]$($1 \leq j \leq 8$)的值。
  • 按照这样的方式,逐步计算出整个 $c[i][j]$ 表,如下所示:
    A C B A B D C D
    0  0 0 0 0 0 0 0 0
    B  0 0 0 1 1 1 1 1 1
    C  0 0 1 1 1 1 1 2 2
    A  0 1 1 1 2 2 2 2 2
    D  0 1 1 1 2 2 3 3 3
    B  0 1 1 2 2 3 3 3 3
    C  0 1 2 2 2 3 3 4 4
    D  0 1 2 2 2 3 4 4 5

3. 回溯构造最长公共子序列

从 $c[m][n]$ 开始回溯,根据 $b[i][j]$ 记录的信息(这里虽然题目未给出 $b[i][j]$ 表,但可以根据 $c[i][j]$ 的值判断)来构造最长公共子序列。

  • 当 $c[i][j] = c[i - 1][j - 1] + 1$ 且 $x_i = y_j$ 时,说明 $x_i$(或 $y_j$)是最长公共子序列的一个元素,将其加入结果序列,并回溯到 $c[i - 1][j - 1]$。
  • 当 $c[i][j] = c[i - 1][j]$ 时,回溯到 $c[i - 1][j]$。
  • 当 $c[i][j] = c[i][j - 1]$ 时,回溯到 $c[i][j - 1]$。

回溯路径如下:

  1. $c[7][8] = 5$,$X[7] = Y[8] = D$,将 $D$ 加入结果序列,回溯到 $c[6][7]$。
  2. $c[6][7] = 4$,$X[6] = Y[7] = C$,将 $C$ 加入结果序列,回溯到 $c[5][6]$。
  3. $c[5][6] = 3$,$X[5] = Y[6] = D$,将 $D$ 加入结果序列,回溯到 $c[4][5]$。
  4. $c[4][5] = 2$,$X[4] = Y[5] = B$,将 $B$ 加入结果序列,回溯到 $c[3][4]$。
  5. $c[3][4] = 2$,$X[3] = Y[4] = A$,将 $A$ 加入结果序列,回溯到 $c[2][3]$。
  6. $c[2][3] = 1$,$X[2] = Y[3] = C$,将 $C$ 加入结果序列,回溯到 $c[1][2]$。
  7. $c[1][2] = 1$,$X[1] = Y[2] = B$,将 $B$ 加入结果序列,回溯到 $c[0][1]$,结束回溯。

最终得到的最长公共子序列为 $B, C, A, B, D$。

相关问题

  • 9、不在网络安全的基本属性范围内的()。A. 机密性B. 可用性C. 完整性D. 多样性

  • 下列哪项不是求解对抗搜索问题的基本算法( ) A.反向传播算法 B.广度优先排序算法 C.Alpha-Beta剪枝算法D.最小最大搜索算法

  • AdaBoosting采用多个单一分类器组成一个强分类器()A. 错误B. 正确

  • 网络安全包括物理安全[1]、逻辑安全、操作系统安全及联网安全,其中逻辑安全包括访问控制[2]、加密、安全管理及用户身份认证。A. 正确B. 错误

  • Windows中“复制”操作的快捷键是Ctrl+V。

  • 2、网络安全工作的目标包括:()。A. 信息机密性B. 信息完整性C. 服务可用性D. 以上都是

  • 8、信息安全“三个不发生”不包括( )。单选题Box 确保不发生大面积信息系统故障停运事故Box 确保不发生恶性信息泄密事故Box 确保不发生信息外网网站被恶意篡改事故Box 确保不发生信息内网非法外联事故

  • 网络安全包括物理安全[1]、逻辑安全、操作系统安全及联网安全,其中逻辑安全包括访问控制[2]、加密、安全管理及用户身份认证。A. 正确B. 错误

  • 7、 加强电脑安全防护,及时升级病 毒库,安装防火墙,及时查杀病毒和木马,是防范 电信网络诈骗的有效做法。A. 正确B. 错误

  • 程序=算法+()A. 数据结构B. 程序结构C. 控制结构[1]D. 体系结构

  • 以下哪种方法属于卷积神经网络的基本组件()。A. 卷积层B. 池化层C. 激活函数D. 复制层

  • 下列哪项属于因果推理模型()A. 因果图B. 神经符号推理C. 符号推理模型D. 结构因果模型

  • 下列哪项关于监督学习算法的描述正确()A. 强化学习的训练效果一定优于监督学习B. 主要的监督学习方法包括生成方法和判别方法C. 广度优先搜索算法是一种监督学习算法

  • 下列哪个方法属于知识图谱推理方法()A. 路径排序算法B. 深度学习推断C. 广度优先搜索D. 归纳逻辑程序设计

  • 由脸书(Facebook)公司开发的深度学习编程框架是()A. TensorFlowB. PaddlePaddleC. PyTorchD. Mindspore

  • 1、网上银行系统的一次转账操作过程中发生了转账金额被非法篡改的行为,这破坏了信息安全的()属性。A. 完整性B. 保密性C. 不可否认性D. 可用性

  • 3.判断题K-means聚类算法对数据的尺寸敏感。()A. 对B. 错

  • 下列不属于量子机器学习算法的是()A. 量子支持向量机B. 量子主成分分析C. 薛定谔方程求解D. 深度量子学习

  • 下列哪项贪婪最佳优先搜索算法的描述正确()A. 贪婪最佳优先搜索不属于启发式搜索算法B. 贪婪最佳优先搜索是一种A*搜索算法C. 贪婪最佳优先搜索是一种广度优先搜索算法D. 贪婪最佳优先搜索属于有信息搜索算法

  • 4/5 以下属于人工智能实际应用的是()。A. 机器视觉B. 人脸识别C. 计算机辅助自动规划D. 智能工业机器人E. 刷卡门禁

上一页下一页
logo
广州极目未来文化科技有限公司
注册地址:广州市黄埔区揽月路8号135、136、137、138房
关于
  • 隐私政策
  • 服务协议
  • 权限详情
学科
  • 医学
  • 政治学
  • 管理
  • 计算机
  • 教育
  • 数学
联系我们
  • 客服电话: 010-82893100
  • 公司邮箱: daxuesoutijiang@163.com
  • qt

©2023 广州极目未来文化科技有限公司 粤ICP备2023029972号    粤公网安备44011202002296号