不同数据结构下回溯法效率的比较

• 作者: 王岚岚 迟呈英
• 来源期刊: 沈阳师范大学学报（自然科学版）
• 学科: 工学
• 关键词: 回溯法 深度优先搜索 数据结构 稀疏矩阵 四向链表
• 年，卷（期）: 2005,（4）
• 页码范围: 372-376
• 页数: 5页
• 分类号: TP311.2
• 字数: 4179字
• 语种: 中文
• DOI: 10.3969/j.issn.1673-5862.2005.04.012

摘要

一般而言,因溯法比枚举法的效率高出几个数量级,因此,其效率问题对于输入规模较大的问题而言至关重要.以一个典型的回溯问题为例,通过对比,说明回溯法在不同数据结构下,其时间效率的差异,验证对于可表示成稀疏矩阵的数据集,在使用四向链表结构时,可以大大提高时间效率.这对于那些适合回溯法解决的问题是非常有意义的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	王岚岚	鞍山师范学院计算中心	4	3	1.0	1.0
2	迟呈英	鞍山科技大学计算机科学与工程学院	10	69	5.0	8.0