Predicting the performance of IDA* using conditional distributions

摘要: Korf, Reid, and Edelkamp introduced a formula to predict the number of nodes IDA* will expand on single iteration for given consistent heuristic, experimentally demonstrated that it could make very accurate predictions. In this paper we show that, in addition requiring heuristic be consistent, their formula's predictions are only at levels brute-force search tree where values obey unconditional distribution they defined then used formula. We propose new works well without these requirements, i.e., can IDA*'s performance inconsistent heuristics if any level do not distribution. order achieve introduce conditional which is generalization also provide extensions our handle individual start states augmentation with bidirectional pathmax (BPMX), tech nique propagating when used. Experimental results demonstrate accuracy method all its variations.