Enhanced Dynamic Programming Approaches for Efficient Solutions to the Traveling Salesman Problem
Journal of Computer Science Application and Engineering (JOSAPEN) · 2024
DOI: 10.70356/josapen.v2i2.32 ↗Kurz gefasst
Fachartikel in der Zeitschrift Journal of Computer Science Application and Engineering (JOSAPEN), 2024. Verfasst von Adriel Moses Anson. Die Arbeit wurde bisher 2-mal zitiert (Crossref). Der Volltext ist frei zugänglich (Open Access, CC BY-SA 4.0).
Abstract (Originalsprache)
This study aims to enhance dynamic programming techniques for efficiently solving the Traveling Salesman Problem, a fundamental combinatorial optimization challenge. Given its NP-hard classification, traditional exact algorithms become computationally infeasible as the problem size increases. The research revisits foundational dynamic programming principles, notably the Held-Karp algorithm, and identifies existing limitations. The study begins with a comprehensive literature review, followed by an analysis of the dynamic programming challenges specific to TSP. Novel algorithms are then developed, implemented, and rigorously tested against benchmark instances. Performance evaluation is conducted using metrics such as execution time, memory usage, and solution optimality across different problem sizes. Results demonstrate significant improvements in efficiency and scalability, with enhanced algorithms achieving optimal solutions in reduced time and computational resource usage. However, the exponential growth in complexity remains a challenge for larger instances. The study concludes with recommendations for future research, focusing on further algorithmic refinements and exploring hybrid approaches to address large-scale TSPs.
Zitieren
APA
Anson, A. M. (2024). Enhanced Dynamic Programming Approaches for Efficient Solutions to the Traveling Salesman Problem. Journal of Computer Science Application and Engineering (JOSAPEN). https://doi.org/10.70356/josapen.v2i2.32
Vancouver
Anson AM. Enhanced Dynamic Programming Approaches for Efficient Solutions to the Traveling Salesman Problem. Journal of Computer Science Application and Engineering (JOSAPEN). 2024. doi:10.70356/josapen.v2i2.32
BibTeX
@article{Anson2024,
author = {Anson, Adriel Moses},
title = {Enhanced Dynamic Programming Approaches for Efficient Solutions to the Traveling Salesman Problem},
journal = {Journal of Computer Science Application and Engineering (JOSAPEN)},
year = {2024},
doi = {10.70356/josapen.v2i2.32}
}
EUVIMED