Abstract: In this paper, based on the mechanism which can dynamically modify heuristic evaluation function, the improved algorithm Learning-IDA* for iterative-deepening-A (i.e. algorithm IDA*) is presented. Algorithm Learning-IDA* has a very important learning property: if heuristic evaluation function is lower bound of actual optimal cost, over repeated uses of learning-IDA* , heuristic evaluation function will eventually converge to actual optimal cost. At last, based on the idea that modified heuristic evaluation function may be propagated, the improved algorithm Learning-PIDA* is also presented.

摘要： 基于动态改变启发式估价函数值的机制,提出了反复加深的启发式搜索算法IDA的改进算法Learning-IDA。该算法具有重要的学习性质:若启发式估价函数取最佳耗散值的下界,则通过使用Learnin-IDA算法大量解题,启发式估价函数最终将收敛到最佳耗散值。最后,基于启发式估价函数值向上传播的思想,本文还提出了Learnin-IDA的改进算法Learning-PIDA。

关键词: 启发式搜索, 学习, 反复加深, 算法

CLC Number: 

• TP301.6