国际大学生程序设计竞赛试题与算法分析(二) 回溯算法.pdf

信意章赛 令毋次豢绪常寻嗽分潇寥 试题与算法分析 二 回溯 耳法 郭篙山 吴汉荣 中山大学信息科技学院计算机科学系 广州 我 们在日常生活中经常会遇到 一 些 要求最优 解 的问题 比如说从一个 城市到另一个 城 市怎么走 才最快 怎么走 才最省钱 但 是在处理一些 最优解 的问题 方面 没有任何的理论也无法采用精确 的数 学公式来 帮助我们 找到最优解 我们只能求 助于穷 举搜索方法 在 这 里 我们介绍 一种 系 统 化 的穷举 搜索技术 称 为回溯技术 所谓 的回溯技术就是像 人走迷 宫一样 先选择 一个前 进 方 向尝试 一步步 往 前 试 探 在遇到死 胡 同不能再往前的时候 就回退到上 一个分叉点 选 另 一个 方向尝试 而在前进和回撤 的路上都设置 一些 标记 以便 能正 确返回 直 到达到目标 或 者 所有 的 可行方案都已经 尝试完 为止 在通 常的情况下 我 们使用递 归方 式来 实现回溯技术 也就是在每 一个 分叉 点进 行递 归 尝试 在回溯时通 常采用栈来 记 录回溯过程 使用栈可使穷举过 程能回溯到所要位 置 并 继续 在指 定层 次上往 下 穷 举 所 有可能 的解 回溯算法可以用伪码 描述 如下 当前状态 当前状 态等于目标状态 对所有可能的新状态 新状态 回溯算法 是一种十分 常用的算法 象一 些经典 问题如八皇后 问题 骑士周游问题 地图着色问题 都可以采用回溯算 法 来解 本期将 刊登题历年 的国际决赛 和区域赛试题 供读者分析和学习 每道题都先给 出题目 然后是算法分析 由于篇幅所 限 我们只 给 出主要 的解 题思路和算 法分析 具体的程序实 现 留给读者 自行 完成 第一题骨牌矩阵 问题描述 多米诺骨牌是一个小正方形方块 每个骨牌都 标 有 一 个 数 字 一 现 在 有组 骨 牌 每 组两 个 各组编 号 为 一 每组编 号对应 的两个骨牌数 值如下 骨骨牌组组骨牌牌 骨牌组组骨牌牌 骨牌组 组 骨牌牌骨牌组组骨牌牌 编编号号号编号号号编号 号号 编号号号 现将这组骨牌排 成一 个矩 阵 此 时只 能看到每个骨牌上的数 字 一 而 不能知 道每组 的组 号 如图所示 请编程将每组 骨牌分辨 出来 见 图 图中数字 为对应图每组骨牌的编号 骨牌摆放可旋转 例如第组 骨牌经旋 转可得以 种放法 万 了 第 届亚洲台 匕赛区 中山大学队教练 第届 亚洲台能赛区中山大学队队长 晦 卫卫 翻 钧仆 伪 仲 曾 并翎饥 匕心公未 从杏少 湘用 骨牌矩阵骨牌组编号矩阵 图图 如场 比 代曰 曰 什 州 替异知饥 匕 心 兮 术 片未少毛如剐 输入格式 从键 盘输 人一个 文本文件的文件 名 该 文 件 包含了一个行列 的骨牌矩 阵 每 行有个 一 的整数 每个整数之间用空格 分开 每 行 的行 首 行末无多余空格 榆出格式 答案输 出到一个 文本 文件 中 文件 名由键 盘输 人 若问题无解 则输 出忆 若问题有解 则将 所 有 可能的解 输出 每个 解之 间用一个空行分开 最后输 出解 的总数 数 字 间用空格分开 算法分析 这题的算法比较简单 只需使用标 准 的回溯算 法 而且由于本 题的规 模比较 小 不需要对算 法进 行优化 既可满足 时间上 的要求 在骨牌矩阵中 每组 骨牌既可以横 放也可以竖 放 我们可以按 从左 到右从上到下 的顺 序 对 骨牌 矩 阵中的每个位置进 行回溯 判 断相应 的骨牌组应 该是 横 放 还是竖放 最 终目标 就 是 要 求 二 十八组 骨牌 组都能够 不 重 复 地 排 成 一个的矩 阵 而 且每个骨牌上 的数字和输人 的骨牌矩 阵一一对应 还要求 每组骨 牌不互相重叠 例程中的过 程 就 是 用于 回溯的 递 归 过 程 它先 查 找下 一个还 没放置骨 牌的位 置 较 如已 经超 过 矩 阵 的范 围 而且 所 有的骨牌组已经放置 好 则 表示已经 找 到一 个解 将 它输 出否则 按四 种方式尝试放 置个骨牌组 假 如成 功则尝试 放置 下 一个骨牌组 假 如不成 功就回溯 核心算法是 递归放 置一个骨牌组 信 沪息穿赛 查 找 下一 个还 没放置骨牌的位置 力 若没有 则表示已经找 到一个解 输出 返回 把在 处 的骨牌作 为 当前骨牌组 的一个骨牌 把在川处 的骨牌作为当前骨牌组的 另一个骨 牌 判断 当前骨 牌 组是否 未 被使用 如果未被使用则递归 放 置下一个骨牌组 把在 处的骨 牌作为当前骨牌组的另一个骨牌 判 断 当前骨 牌 组是否未被使用 如果未被使用 则递归放 置下 一 个骨 牌组 两种尝 试都失 败 进 行回溯 第二题求马的不同走法总数 问题描述 在 一个的棋 盘 上 马的起 始 位置坐标 纵 横位 置由键 盘输人 求马能返回初 始位置的 所有不同走法 的总数马走 过 的位置不能重复 马 走 旧 字 算法分析 由于棋盘 的大小只有 所以只需使用回 溯算法 搜索马能返回初 始 位 置的所 有不同走法 效率基本上能达到要求 递归的回溯算法 可描述 为 是 当前位置 马从当前位 置出发 走 一 步 到位置的每 一 种走法 在棋盘内位置没有走 过 出发点不同走 法 总数加 标记 已经走 过了 取消位置 的标记 下面讨论算法的具体实现 棋盘用坐标表示 点 表示棋盘上任一个 点 的范围是 从 出发 下 一 步 最多有个位 置 记 为 若 用表示这个方 向 则 即马从点 出发 首先沿的方向行进 当 在此方 向走完所有 的不同走法后 就 进 行回溯 改 变 二 方向继续行进 乃 信 矛窟章赛 各点坐标的计算 设点坐标为 则能到 达点的坐标分 别为 一 一 一 一 一 一 为 简化坐标的计算 引人增 量数组 二 一 一 一 一 一一 一一 则按方向能到达点的坐标是 霎霎霎霎霎霎霎霎霎霎霎霎霎霎霎 入入入入入才才才才 么么夕夕 声 产产产 尹产 产 门门卜卜 夕夕夕夕夕侧侧侧侧 图马的八种不同走法 第三题求不 连续重复字 符序列 问题描述 由大写字母 中前个 字母 组成 字 符序列 所 谓不连续重复 字符序列是 指 字符序列中 无连续 重复的子 串 例如 以下为有连续重复 字 串的字符序列 又如以下为没有连续重复 字 串的字符序列 输入和输出 请编写程 序 读人 整数和 其中 输出第个由前个 字母 组 成 的不连 续 重复字符序列 以及这个 序列 的长度 显然 第 个不连续 重复 字符序列 为 假 定 由给出的和 中至少存在个不连续重复 序列 例如当时 前个不连续 重复序列为 由于所输出序列 可能很长 因此输出时以每 个字母 为组 每组用个空格分开 每行个 字 符 输人以两个时用 空格分开结束 输人样例 输出样例 算法分析 由于只要求最大 为 所以只需使用回溯 算法 搜索生成前个不连续重复 字符序列并输 出 第个不 连续重复字符序列 即可 测试 时保证不会 超时 本题的关键 在于判断字 符 序列有无连续重复 字 串 由于 我们是一面搜索一面判断的 因此 当需 要判断一个长度 为的字符序列有 无连续重复 字 串时 可以确保 前 一 个 字符的序列没 有连续重 复字串 只需检查包含第个字符的字串即可 因 为如果这个 字符序列含有连续重 复字 串 则必 定是 由第个 字符造成 的 判断字符序列有无 连 续重复 字 串的函数可 描述为 检查 长度为的字 串 一 一 返回有 连续 重复字串 返回没有连续重复字串 需要注意的 一点是本 题 最好使用非递 归 的搜 索算法 否则容易造成堆栈溢 出 可以考虑的优化措施有 为了提高信息 的利 用率 对 每个字符序 列 若没有搜索过 可搜索至 生成前个不连续重 乃 翻 场少找 曰 什 州 枯豆 翎饥 匕心琶 未 八上下少七湘用 信息竟赛 复字符序列并 用一个 字符 串数组记录搜 索过程 然 后从 中还原出第个字符 序列输出若已经搜索 过 直接从中还 原出第个字符序列并输 出 当 时 所 产 生 的前个序列是 相 同 的 所以可以直接调 用的结 果 求不连续重复字符序列 可描述 为 初始化 读人新 的和 输人合法 协 声 迁 的字 申还未产生产生的字串 还原 出第个序列并输出 二二 把新的序列 添加人记录字串田 已经产生了 个字符序列停止搜索 二 二 的前一个字符初始化下一层 的搜索 一 回退一 层 把 添加人记录字 串田 还原的过程可描述为 记 录搜索过 程和还 原出第个 字 串 的 实 现 方 法有很 多 这里对我使用 的方法做简单说明 非递 归 的搜索过程可描述 为 当前搜索的深度 二 的前一个字符 当前生成 的字符序列 连 还未生成个字符序列 二 前 个字母 没有连续重复字 串 让 一 删 除的最后一个字符 二 口 中存放 的是还原 出来 的字 串 例如 二 时 搜 索 结 束后 记录以下字 符 串 一 一 一 表示 往回退 一位 此 字 串可表示 二 时 的个 序列 然后还原出第个序列并输 出 收稿日期 一一 北女女女北流流女女流女女流女女流女流女女北北女女女女北女流流女女交流流北女女北北流女北北 上接第页 翻 坏 饰 样 践 曰 仲 们 曹 开知仇 匕 心分未 从山少七湘用 数据库包含了主数据库以及 帐号权 限 统计 汇 总等辅 助数据库 系统管理模块 的功能包 含 系统初始化 原始 数 据 的 录人和修 改 数 据定 期 备 份 定 期 统 计收费额 并自动划 款 发送 电子邮件等子 功 能 安 全 维 护模 块 有 帐号管理 权 限管理 操 作跟 踪用日志记录 等功能 实现用户安全性 数据安全性 操作安全性 的全面管理 这种 系统结构模 块 化程