Dissertation > Excellent graduate degree dissertation topics show

The Research on Digital Map Optimal Path Algorithms Chosen

Author: BuBing
Tutor: WuFaDong
School: Chinese Geology University (Beijing)
Course: Quaternary Geology
Keywords: Dijkstra's algorithm Shortest Path Optimization algorithm Core area Blind spot
CLC: U116.2
Type: Master's thesis
Year: 2008
Downloads: 388
Quote: 1
Read: Download Dissertation

Abstract


Dijkstra algorithm is the Dutch mathematician EW Dijkstra label setting method proposed in 1959 (label setting algorithms) is the the theoretically most perfect , by far the most widely used network shortest path algorithm . The first half of this article is to analyze and summarize the ideas and programming of Dijkstra's algorithm implementation process . To identify defects of the algorithm , the search efficiency is low, the time complexity of O (n2 ) . The main reason - algorithm data structure in exchange for space savings due to the restrictions of the level of development of the computer hardware space to store into a very important position at the expense of proper time efficiency . Space storage problem is not the main issues to consider , it is necessary to re - consider the existing algorithms improve , thereby improving the efficiency of the shortest path algorithm . Whether it is the shortest distance , fastest time or the lowest cost core algorithm are the shortest path algorithm . The classic shortest path algorithm - Dijkstra algorithm is the theoretical basis for most systems used to solve the shortest path problem , just a different system to Dijkstra's algorithm using different implementations . Later in this article currently two major optimization ways that target sort and limit the search area to analyze , focus on building a new type of search area model to achieve optimization , and summed up the two ideas must comply modeling . In the ellipse algorithm model based on the analysis , we explore three novel optimization model , rectangular optimization model , the fan algorithm optimization model and optimization model . And proposed the new concept of the \After the exploration and study of optimization of the algorithm is bound to greatly improve the time and space efficiency of the work , the improved algorithm can basically meet the geographic information system for dealing with the kind of data and a large number of requirements , and more inclined to stability easy to achieve high efficiency, and this is the optimal path algorithm characteristics .

Related Dissertations

  1. Design and Implementation of the Online Map System Based on LBS,TN929.5
  2. Information Extraction and Processing from Digital Body and Garment Models,TP391.72
  3. The Research on Emergency Material Dispatch Problem Based on Hub-and-Spoke Network,F252
  4. Research on Agent-based Self-organization Evolution Mechanism of Wireless Sensor Networks,TN929.5
  5. Several Research and Analysis Base on Min-cost Max-flow Algorithm,TP301.6
  6. Campus Information System Design and Implementation Based on GIS,TP311.52
  7. A Study on Reliable Path Finding under Emmrgency Logistics,F259.2
  8. Discussion and Research on Local Support Vector Machine,TP18
  9. Single- and multi- assignment assigned coexistence with hub Logistics Network Design,F252
  10. A Two-stage Approach for the Time Dependent Rural Postman Problem with Time Windows,O221.4
  11. Reflected Wave Tomographic Simulation and the Application in Xi’an Ground Fissures,P631.4
  12. The Study of the Freeway Emergency Command System Based on GIS,P208
  13. Research and Design of Campus Electronic Map Navigation System Based on MapX,P208
  14. Research on Expressway Maintenance Sites Classification and Selection,U418.2
  15. Collection and Processing of Picking Routing Information in Distribution Center,F253.9
  16. The shortest path based on PVM Study of method,O157.5
  17. Spatial information service based on SSH traffic control system analysis and design,U495
  18. The Research on the New Transportation Organization Plan of Wuhan Terminal After the Operation of North Wuhan Marshalling Yard,U292
  19. Research and Realization of Vehicle Monitoring and Scheduling in Environmental Protection Emergency Command System,TP277
  20. Research and Application Based on Mixed Algorithm in Logistics Transportation,TP301.6
  21. Research on Urban Geographic Information System for Transportation Based on Vector Graph,P208

CLC: > Transportation > Integrated transport > Integrated transport system and structure > Reasonable transportation > Transport Route Selection
© 2012 www.DissertationTopic.Net  Mobile