The Study Of Dynamic Programming Technology Based On Embedded GIS Navigation Path

With the development of the society and economy, transportation industry is developing at an unprecedented rate. After this perennial development, the potential problems in the field of transport are also revealed day by day. Particularly in an unfamiliar environment, the driver will inevitably take a long way around and even drive the wrong road which will not only result in a waste of time and resource, but also seriously obstruct traffic when he runs into the traffic peak, what is more serious is that the environment will be severely polluted by the CO NO x HC. Therefore, vehicle navigation system reflects the value of its existence, navigation path in which dynamic programming technology is the top priority of the system.This paper is mainly related to the embedded system, digital map visualization, road network topology, the path planning technology and etc while focusing on the following three parts.1. Analysis of hardware and software's architecture. Firstly, designed hardware module and the overall framework of the electronic map's software and secondly organized road data.2. Organization of the navigation topological data. On the basis of road network data's abstraction and storage which was researched by the previous academic, this paper considered the division of a line segment, the integration of the redundant data and the demarcation of the border. After data processing, it was authenticated by the classic shortest path search algorithms.3. Dynamic programming based on the restricted searching area with a two-dimensional flow pattern. In this paper, the embedded navigation electronic map had the following problem. When the road network data was large enough, all of the data couldn't be read into the memory. General algorithms were used that didn't realize the characteristics of rapidity and accuracy when it performed the path navigation. Even if the embedded memory was large enough (it could accommodate all of the road network data), the electronic map caused "stuck" phenomenon in the path planning. In order to avoid the problem, this paper presented the restricted searching area algorithm with a two-dimensional flow pattern. Firstly, it determined whether the starting point and the end point existed in the current displayed main block, reserved and adjacent eight blocks. Secondly, it judged the boundary data to determine the searching area. Finally, it calculated the distance between the source point and the points by dynamic programming algorithm and found a full path through using information which data contained and the end point backstepping. After pretreatment, when using dynamic programming for path search, it not only reduced invalid computation of huge data, but also searching direction was clearer that improved the searching efficiency.This paper studied the developer platform which was based on an embedded Linux operating system and the QT / Embedded as compared with the embedded WinCE operating system, greatly reducing development costs.