| 正则搜索树的分支因数 |
| |
| 引用本文： | 白治江,杨振亚,王成道.正则搜索树的分支因数[J].上海海事大学学报,2003,24(3):239-242. |
| |
| 作者姓名： | 白治江 杨振亚 王成道 |
| |
| 作者单位： | 1. 上海海运学院,信息工程学院,上海,200135
2. 华东师大,电子系,上海,200062 |
| |
| 摘 要： | 正则搜索树的分支因数对算法的复杂度有决定性影响。尤其在深度优先的启发式搜索中,决定时间复杂度的启发式分布与分支因数紧密相关。本文介绍两种分支因数的计算方法:数值法与解析法。在数码难题及鲁比克魔方这两类实际的问题空间上,用这两种方法可获得相同结果。这些结果是进一步研究算法时间复杂度的必要基础。
|
| 关 键 词： | 时间复杂度 平衡比率 分支因数 数码难题 鲁比克魔方 |
| 文章编号： | 1000-5188(2003)03-0239-0004 |
| 修稿时间： | 2003年2月17日 |
Branching Factor of Regular Search Trees |
| |
| BAI Zhi-jiang,YANG Zhen-y,WANG Cheng-dao.Branching Factor of Regular Search Trees[J].Journal of Shanghai Maritime University,2003,24(3):239-242. |
| |
| Authors: | BAI Zhi-jiang YANG Zhen-y WANG Cheng-dao |
| |
| Abstract: | The branching factor of a regular search tree has a decisive effect on the time complexity of a search algorithm. It is closely relative to the equilibrium distribution that is necessary to determine the time complexity. In this paper, we present both analytic and numerical techniques for computing the exact number of nodes at a given depth, and determining the asymptotic branching factor. We give the branching factor of Ruble's Cube and Sliding-tile Puzzles from the Five Puzzle to the Ninety-Nine Puzzle. |
| |
| Keywords: | time complexity equilibrium fraction branching factor sliding-tile puzzles Ruble's Cube |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
| 点击此处可从《上海海事大学学报》浏览原始摘要信息 |
| 点击此处可从《上海海事大学学报》下载免费的PDF全文 |
