This paper studies the complexity of two different algorithms proposed as extensions of A* for multiobjective search: MOA* and NAMOA*. It is known that, for any given problem, NAMOA* requires the consideration of no more alternatives than MOA* when provided with the same heuristic information. In this paper we show that, in fact, expansions performed by MOA* can be many more than those demanded by the problem, and hence than those performed by NAMOA*. More specifically, we show a sequence of problems whose size grows linearly such that the number of expansions performed by NAMOA* grows also linearly, but the number of expansions performed by MOA* grows exponentially. Therefore, there are problems where NAMOA* performs exponentially better than MOA*.
展开▼
