Obtaining optimal solution for most of the real world problems requires an exhaustive search through the problem state space by considering all possible solutions. To solve these problems more efficiently, many different heuristic search algorithms like A*, IDA*, KBFS etc. have been proposed. All of these algorithms make use of a heuristic evaluation function to evaluate the problem states. The performance of such search algorithms depends on the accuracy of the heuristic functions. In single agent search domains, heuristic functions compute an estimate of the solution cost from the current state to the goal state. If the heuristic function is admissible, i.e. it never overestimates the cost of reaching the goal, A* and its variations are guaranteed to return an optimal solution, if one exist. The more accurate the heuristic function is, the more efficient the search algorithm will be. Much research has been devoted to developing more accurate heuristic functions. The main purpose of this thesis is to develop methods to improve the accuracy and the quality of heuristic functions. One of the important admissible heuristic functions already proposed is Pattern Databases (PDBs) which is the state-of-the-art method to optimally solve many combinatorial problems. The main drawback of PDBs is the amount of memory they needed to store the database. In this research, we first try to solve the PDB memory requirement problem. We first introduce a new and general method to compress PDBs by using machine learning techniques. Experimental results show the improvement achieved by our method over the previous compression methods with respect to the amount of memory, the number of generated nodes, and consequently run time. Experimental results show that our full compression system reduces the size of required memory by a factor of up to 61. In the second part of this thesis we use the Perimeter Search (PS) technique to improve the quality of the heuristic functions. We suggest an efficient method to combine PS with PDBs. The regular combination of PS with PDBs needs a large amount of memory to save the PDBs. We introduce a novel method to map different states of the problem to the goal state. This allows us to combine these two methods by using a limited amount of memory. We experimentally show that our method outperforms the state-of-the-art techniques. Key words: Heuristic Search, Pattern Databases, Compression, Decision Tree, Artificial Neural Networks, Perimeter Search
