Para acceder a los documentos con el texto completo, por favor, siga el siguiente enlace: http://hdl.handle.net/2117/97596

Limited discrepancy AND/OR search and its application to optimization tasks in graphical models
Larrosa Bondia, Francisco Javier; Rollón Rico, Emma; Dechter, Rina
Universitat Politècnica de Catalunya. Departament de Ciències de la Computació; Universitat Politècnica de Catalunya. LOGPROG - Lògica i Programació
Many combinatorial problems are solved with a Depth-First search (DFS) guided by a heuristic and it is well-known that this method is very fragile with respect to heuristic mistakes. One standard way to make DFS more robust is to search by increasing number of discrepancies. This approach has been found useful in several domains where the search structure is a height-bounded OR tree. In this paper we investigate the generalization of discrepancy-based search to AND/OR search trees and propose an extension of the Limited Discrepancy Search (LDS) algorithm. We demonstrate the relevance of our proposal in the context of Graphical Models. In these problems, which can be solved with either a standard OR search tree or an AND/OR tree, we show the superiority of our approach. For a fixed number of discrepancies, the search space visited by the AND/OR algorithm strictly contains the search space visited by standard LDS, and many more nodes can be visited due to the multiplicative effect of the AND/OR decomposition. Besides, if the AND/OR tree achieves a significant size reduction with respect to the standard OR tree, the cost of each iteration of the AND/OR algorithm is asymptotically lower than in standard LDS. We report experiments on the minsum problem on different domains and show that the AND/OR version of LDS usually obtains better solutions given the same CPU time.
Peer Reviewed
Àrees temàtiques de la UPC::Informàtica::Informàtica teòrica::Algorísmica i teoria de la complexitat
Algorithms
AND/OR search trees
Limited discrepancy search algorithm
LDS
Graphical models
Algorismes
info:eu-repo/semantics/publishedVersion
info:eu-repo/semantics/conferenceObject
AAAI Press (Association for the Advancement of Artificial Intelligence)
         

Mostrar el registro completo del ítem

Documentos relacionados

Otros documentos del mismo autor/a

Rollón Rico, Emma; Larrosa Bondia, Francisco Javier; Dechter, Rina
Dechter, Rina; Kask, Kalev; Lam, William; Larrosa Bondia, Francisco Javier