Abstract
This paper formulates learning optimal Bayesian network as a shortest path finding problem. An A*search algorithm is introduced to solve the prob-lem. With the guidance of a consistent heuristic,the algorithm learns an optimal Bayesian network by only searching the most promising parts of the solution space. Empirical results show that the A*search algorithm significantly improves the time and space efficiency of existing methods on a set of benchmark datasets.