Simulation of shortest path using a-star algorithm / Nurul Hani Nortaja

• Main Author: Nurul Hani , Nortaja
• Format: Thesis
• Published: 2004
• Subjects: QA75 Electronic computers. Computer science
• Online Access: http://studentsrepo.um.edu.my/9948/1/Nurul_Hani_Nortaja_%2D_Academic_exercise.pdf; http://studentsrepo.um.edu.my/9948/

The shortest path problem has been widely studied for decades. It has been applied in many practical applications. For most of the cases of the shortest route finding, the Dijkstra's algorithm is known to be an optimal search algorithm. Nonetheless, the A • algorithm do have some unique properties which is more efficient in finding the shortest path especially in human real-world problem. In this thesis, the scope of study focuses on the efficiency of the A • algorithm to make the pathfinding for a shortest route from parking entrance to the empty parking space in parking lot in fastest time and easier way. The development of A* simulation is only one modul apart from the overall automated parking system. For WXES318l, the thesis only cover the first part of A • development and implementation that includes the algorithm flowchart, pseudocode and the calculation process of the formula for the shortest route (F = G + H). As for WXES3l82, the thesis cover the development of programming code, the code implementation and testing and the evaluation including discussion about the problem/constraints meed in the coding program development. This thesis also provides an explanation about the advantages. functions, characteristics. the degree of complexity in A • algorithm and its implementation in real-world application. The steps to calculate a shortest path using A • algorithm is shown by using appropriate examples and related figures. The development process for this simulation is using programming language of Microsoft Visual C I t 6.0 and the coding creation depends on the algorithm flowchart and the formula pseudocode. Besides that, there is an interface view for the expected simulation output which mainly is in MSDos Prompt. The A* algorithm is considered to be more efficient than Dijkstra's algorithm because it searchers towards a goal without considering all nodes in a state space, but rather more focus and directed. This means A • algorithm only calculates and consider the next node m path that has the lowest value of G and F, plus searching the shortest route by using heuristic estimation in Manhattan method. Definitely this best first search algorithm saves the searching time and improves performance of shortest path finding.