Traditional search algorithms work on problems that can be modeled in a tree-like shape, this is, solving a problem corresponds to traversing the tree from the root to one of the leaves of the tree that represents a solution. Each one of the edges can be seen as a transition between different states of the problem where each state depends on the previous and the decision taken. There’s a subset of these problems where we can identify subproblems which are independent from each other, in other words, the solutions of one don’t depend on the other. Sometimes we can also identify equivalent subproblems that can be solved interchangeably. Consequently, it’s interesting to have a graph than can model these relations and, later, algorithms that exploit them to solve the given problems. The models that capture these independencies are called AND/OR trees (or graphs depending on their connectivity) and yield solutions in the form of a sub-tree. An example modeled with a common search tree (which corresponds to an OR tree) has inherently larger size than an AND/OR tree since the later as it takes into account the subproblems’ independency. Intuitively we can think that an OR tree solves subproblems in a chain-like manner while AND/OR trees branches them out yielding a tree with a smaller height. As it’ll be seen later, these graphs can be used to model inference problems (graphical models, in general) and exact and approximated algorithms have been implemented used to obtain the answers compute the answers to the most common queries. The modeling, solution and complexity of finding solutions to these problems are the subject of study of the present work. Orderings of variables and pseudo-trees, the underlying structures needed to construct the problem’s space, will be studied as well due to their impact in the complexity of said algorithms. The new contributions of this work are the analysis of the trade-offs between the width and height of the pseudo-trees and the implementation of AND/OR Beam Search and Anytime AND/OR Beam Search as an attempt to tackle the weaknesses of some of the state-of-the-art algorithms.