Research On Map Path-Finding Based On A* Algorithm

For a long time, search algorithm has been a very important field of artificial intelligence. In the more than 50 years research, search algorithm has developed into a mature theory system. Search algorithm includes matching, choice and i 1 lustration of knowledge, and the result of matching and illustration always cause re-search algorithm. In all the applications of search algorithm, people always focus on the map Path-Finding.According to the characteristics of search technology, this paper makes some improvement to the A~*algorithm on the base of analyzing it. Its main aim is to make A~*algorithm more quicker and smoother and to lay a foundation for the map Path-Finding.Firstly, this paper introduces the common method of search process of the describing process of the Produce System and a method of knowledge expression —State space in artificial intelligence. Then, it introduces two basic strategies —tradition search technology and heuristically search technology in the aspect of artificial intelligence. At last, it expatiates one of the heuristically search technologies—A~* algorithm and its characteristic and method of realization, discusses the heuristically ability and search efficiency of evaluation function, and gives a new map Path-Finding algorithm based on A~*algorithm, which includes the creation of map file, search algorithm and evaluation function and so on.Besides, this paper mainly focus on the A~*algorithm in search algorithm. It makes an improvement in quickening and smoothing the path on the base of A~*algorithm according to the map structure, and realizes a kind of map Path-Finding based on A~* algorithm.Evaluation function is obtained by never-ending study, depending on the given field knowledge and adjusting its eigenvalue and weight. Experiments indicate that there is a very important effect on using the search information obtained.Finally, the new map Path-Finding algorithm based on A~*algorithm is described in detail under the environment which use Windows 2000 as client operation system and use Visual C++.NET as development tool. In this way, it reaches the aim of the intelligentized map Path-Finding put forward in the paper.