000			02890nam a22002417a 4500
003			ft8915
005			20251218151423.0
008			251218b ||||| |||| 00| 0 eng d
041			_aengtag
050			_aQA76.9 A43 C33 2025
082			_a.
100	1		_a Cabrera, Kevin Jerome C.; Fetero, Mark Noe S.; Templanza, Mark Angelo S.
245			_aAn enhancement of A* search algorithm with K-step look ahead by Kevin Chen for real road networks
264		1	_a. _b. _cc2025
300			_bUndergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2025
336			_2text _atext _btext
337			_2unmediated _aunmediated _bunmediated
338			_2volume _avolume _bvolume
505			_aABSTRACT: This study presents an enhancement of the A* Search Algorithm with k-step look-ahead heuristics, initially introduced by Kevin Chen, to improve path-finding efficiency in real-world road networks. While Chen’s approach improved heuristic accuracy, it exhibited significant computational inefficiencies particularly in large-scale graphs making it less suitable for real road network systems such as GPS navigation. This research addresses those limitations through three key enhancements – heuristic caching, look-ahead parallelization, and the adoption of a 4-ary heap data structure. Each enhancement targets a specific bottleneck in Chen’s original algorithm. Heuristic caching reduces redundant calculations by using precomputed estimates, improving responsiveness when revisiting nodes and delivering runtime gains of up to 23.11%. This contributes to faster route computation, allowing real-time route planning becomes more responsive. Look-ahead parallelization distributes k-step expansions across threads, validating simultaneous path evaluations. This addresses the sequential bottleneck in Chen’s method and submit the highest improvement, with runtime reductions up to 48.05%, further enhancing scalability for large maps and allowing the system to handle large-scale road networks. Additionally, switching to a 4-ary heap enhances priority queue performance by reducing tree depth, improving runtime by up to 14.69% in dense urban environments. This supports faster algorithm processing and better overall application efficiency. These enhancements were validated on real-world road networks of varying scales; Mattawa (small), Jersey City (medium), and New York City (large), showing consistent percentage improvements. Furthermore, the researchers identifies performance-affecting factors that influence algorithmic efficiency. By successfully addressing the limitations of Chen’s K-step look-ahead heuristics, this study opens the way for further advancements in real-world path-finding algorithms, establishing greater efficiency in large-environments.
526			_aF
655			_aacademic writing
942			_2lcc _cMS
999			_c37378 _d37378