| 宽度优先反复加宽及其启发式搜索算法研究 |
| |
| 引用本文： | 王士同.宽度优先反复加宽及其启发式搜索算法研究[J].计算机工程与设计,1996,17(1):3-8. |
| |
| 作者姓名： | 王士同 |
| |
| 作者单位： | 华东船舶工业学院 |
| |
| 摘 要： | 首先针对搜索树中深度固定且目标唯一的寻优问题，指出宽度优先反复加宽的搜索效率要比深度优先反复加深的搜索效率高，基于此，提出了基于宽度优先反复加宽的启发式搜索算法ＩＷＡ＊，算法ＩＷＡ＊是可采纳的。为了保持算法ＩＷＡ＊的搜索效率高于算法ＩＤＡ＊的搜索效率，同时又使算法ＩＷＡ＊的存贮空间复杂度减低，文中基于分层技术，提出了基于深度优先的ＩＷＡ＊算法──ＩＤＷＡ＊。算法ＩＤＷＡ＊也是一个可采纳的启发式搜索算法。
|
| 关 键 词： | 启发式搜索，宽度优先反复加宽，深度优先搜索 |
Research on Width-First Iterative Widening and Its Heuristic Search Algorithms |
| |
| Wang Shitong.Research on Width-First Iterative Widening and Its Heuristic Search Algorithms[J].Computer Engineering and Design,1996,17(1):3-8. |
| |
| Authors: | Wang Shitong |
| |
| Abstract: | In this papar, the fact is pointed out that for optimal-finding problem of asearch tree with only a fixed goal, the search efficiency of width-first iterative widening is larger than that of depth-first iterative deepening. Based on this, heuristic search algorithmIWA * based on width-first iterative widening is presented, and its admissibilily is proved.To make the storage complexity of IWA * greatly-decreased and keep the property that the search efficiency of IWA* is larger than the search efficiency of IDA*, by using proper hierarchical technologies for search trees, the IWA* algorithm IDWA* based on depth-first search is presented, and its admissibility is also proved. |
| |
| Keywords: | Heuristic search Width-first iterative widening Depth-first search |
| 本文献已被 CNKI 维普 等数据库收录！ |
|
