| 000 -LEADER |
|---|
| fixed length control field |
02890nam a22002417a 4500 |
| 003 - CONTROL NUMBER IDENTIFIER |
|---|
| control field |
ft8915 |
| 005 - DATE AND TIME OF LATEST TRANSACTION |
|---|
| control field |
20251218151423.0 |
| 008 - FIXED-LENGTH DATA ELEMENTS--GENERAL INFORMATION |
|---|
| fixed length control field |
251218b ||||| |||| 00| 0 eng d |
| 041 ## - LANGUAGE CODE |
|---|
| Language code of text/sound track or separate title |
engtag |
| 050 ## - LIBRARY OF CONGRESS CALL NUMBER |
|---|
| Classification number |
QA76.9 A43 C33 2025 |
| 082 ## - DEWEY DECIMAL CLASSIFICATION NUMBER |
|---|
| Classification number |
. |
| 100 1# - MAIN ENTRY--PERSONAL NAME |
|---|
| Personal name |
Cabrera, Kevin Jerome C.; Fetero, Mark Noe S.; Templanza, Mark Angelo S. |
| 245 ## - TITLE STATEMENT |
|---|
| Title |
An enhancement of A* search algorithm with K-step look ahead by Kevin Chen for real road networks |
| 264 #1 - PRODUCTION, PUBLICATION, DISTRIBUTION, MANUFACTURE, AND COPYRIGHT NOTICE |
|---|
| Place of production, publication, distribution, manufacture |
. |
| Name of producer, publisher, distributor, manufacturer |
. |
| Date of production, publication, distribution, manufacture, or copyright notice |
c2025 |
| 300 ## - PHYSICAL DESCRIPTION |
|---|
| Other physical details |
Undergraduate Thesis: (Bachelor of Science in Computer Science) - Pamantasan ng Lungsod ng Maynila, 2025 |
| 336 ## - CONTENT TYPE |
|---|
| Source |
text |
| Content type term |
text |
| Content type code |
text |
| 337 ## - MEDIA TYPE |
|---|
| Source |
unmediated |
| Media type term |
unmediated |
| Media type code |
unmediated |
| 338 ## - CARRIER TYPE |
|---|
| Source |
volume |
| Carrier type term |
volume |
| Carrier type code |
volume |
| 505 ## - FORMATTED CONTENTS NOTE |
|---|
| Formatted contents note |
ABSTRACT: 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 ## - STUDY PROGRAM INFORMATION NOTE |
|---|
| Classification |
Filipiniana |
| 655 ## - INDEX TERM--GENRE/FORM |
|---|
| Genre/form data or focus term |
academic writing |
| 942 ## - ADDED ENTRY ELEMENTS |
|---|
| Source of classification or shelving scheme |
|
| Item type |
Thesis/Dissertation |