Finding Longest Common Subsequence among several strings is one of the most important problems in combinatorial optimization. Given an ensemble of strings, this problem searches for the longest string which is subsequence of all strings. Various applications for this problem are available in molecular biology, genetics, text editing files comparing, data compression, pattern recognition and Web mining. The problem is considered NP-Hard if the number of strings is greater than 2.Till now, no polynomial-time algorithm is proposed for NP-hard problems which solve them optimally. Different solutions for the problem is proposed till now from which, most primitive solutions have been Exact algorithms that try to provide optimal solution for the problem. Since it is not affordable to apply these solutions to large instances of the problem, non-exact algorithms have also gained a great deal of attention. Non-exact algorithms sacrifice optimality to decrease time complexity for NP-Hard problems. The main goal of these algorithms is obtaining suitable solutions especially for large instances of problem in a reasonable period. Non-exact solutions are divided into two categories: The first is approximation methods and the second is heuristic algorithm. For this problem, the later has produced better results than the former. Our aim in this thesis is to develop a new algorithm which can act better than its previous counterparts. New heuristic algorithm developed in this thesis is proven to show superior performance in terms of quality of results as well as exec Keywords: 1- Longest Common Subsequence 2- Heuristic Algorithm 3- Beam Search 4- Object patterns in Images
