| 迭代延伸A*的分析 |
| |
| 引用本文： | 白治江,韩伟,王成道.迭代延伸A*的分析[J].上海海事大学学报,2005,26(1):57-62. |
| |
| 作者姓名： | 白治江 韩伟 王成道 |
| |
| 作者单位： | 1. 上海海事大学,信息工程学院,上海,200135;华东师范大学,信息学院,上海,200062
2. 华东师范大学,信息学院,上海,200062 |
| |
| 基金项目： | 863项目(2002AA134020-04) |
| |
| 摘 要： | 以问题空间上启发值的分布为启发函数的特征来分析迭代延伸A^*(IDA^*)的时间复杂度。使启发函数的作用相当于减小有效的搜索深度。分析还表明渐进启发分支因数与遍历分支因数相同。实验结果证实用该结论可以准确地预测IDA^*在数码难题这些实际问题上的性能。
|
| 关 键 词： | 延伸 迭代 启发函数 时间复杂度 问题空间 实际问题 作用相 因数 搜索 遍历 |
| 文章编号： | 1672-9492(2005)-01-0057-06 |
| 修稿时间： | 2004年2月20日 |
Analysis of iterative-deepening-A |
| |
| BAI Zhijiang.Analysis of iterative-deepening-A[J].Journal of Shanghai Maritime University,2005,26(1):57-62. |
| |
| Authors: | BAI Zhijiang |
| |
| Institution: | BAI Zhijiang~ |
| |
| Abstract: | The running time of iterative-deepening-A~*(IDA~*) algorithm is analyzed with heuristic function of the problem space and the effect of the function is to reduce the actual search depth. Moreover, the analysis has indicated that the asymptotic heuristic branching factor is same as the brute-force branching factor. The experimental result shows that the performance of IDA~* on actual problems such as Puzzles can be accurately predicted with the main conclusion. |
| |
| Keywords: | probability of heuristic values running time branching factor puzzles IDA~* |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
| 点击此处可从《上海海事大学学报》浏览原始摘要信息 |
| 点击此处可从《上海海事大学学报》下载免费的PDF全文 |
