文章基本信息

标题：A Case of Pathology in Multiobjective Heuristic Search
本地全文：下载
作者：J.L. Pérez de la Cruz ; L. Mandow ; E. Machuca 等
期刊名称：Journal of Artificial Intelligence Research
印刷版ISSN：1076-9757
出版年度：2013
卷号：48
页码：717-732
出版社：American Association of Artificial
摘要：This article considers the performance of the MOA* multiobjective search algorithm with heuristic information. It is shown that in certain cases blind search can be more efficient than perfectly informed search, in terms of both node and label expansions. A class of simple graph search problems is defined for which the number of nodes grows linearly with problem size and the number of nondominated labels grows quadratically. It is proved that for these problems the number of node expansions performed by blind MOA* grows linearly with problem size, while the number of such expansions performed with a perfectly informed heuristic grows quadratically. It is also proved that the number of label expansions grows quadratically in the blind case and cubically in the informed case.