| 不同数据结构下回溯法效率的比较 |
| |
| 引用本文： | 王岚岚,迟呈英.不同数据结构下回溯法效率的比较[J].沈阳师范大学学报(自然科学版),2005,23(4):372-376. |
| |
| 作者姓名： | 王岚岚 迟呈英 |
| |
| 作者单位： | 1. 鞍山师范学院,计算中心,辽宁,鞍山,114005
2. 鞍山科技大学,计算机科学与工程学院,辽宁,鞍山,114044 |
| |
| 摘 要： | 一般而言,因溯法比枚举法的效率高出几个数量级,因此,其效率问题对于输入规模较大的问题而言至关重要.以一个典型的回溯问题为例,通过对比,说明回溯法在不同数据结构下,其时间效率的差异,验证对于可表示成稀疏矩阵的数据集,在使用四向链表结构时,可以大大提高时间效率.这对于那些适合回溯法解决的问题是非常有意义的.
|
| 关 键 词： | 回溯法 深度优先搜索 数据结构 稀疏矩阵 四向链表 |
| 文章编号： | 1008-374X（2005）04-0372-05 |
| 收稿时间： | 2005-01-10 |
| 修稿时间： | 2005年1月10日 |
Improving the efficiency of backtracking |
| |
| WANG Lan-lan,CHI Cheng-ying.Improving the efficiency of backtracking[J].Journal of Shenyang Normal University: Nat Sci Ed,2005,23(4):372-376. |
| |
| Authors: | WANG Lan-lan CHI Cheng-ying |
| |
| Abstract: | General speaking,backtracking is more efficient than enumeration in quantity,therefore efficiency in problem is very important when inputting a large amount of data.This paper present the classic backtracking as an example,through comparing,explains backtracking efficiency difference under various data structure;when database can be expressed in sparseness matrix,then it can be expressed in 4-way linked list,which improves greatly the efficiency than before.The method is most useful for solving problem by backtracking. |
| |
| Keywords: | backtracking depth-first search data structures sparse matrix 4-way linked list |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
