EUVIMEDEUVIMED entdecken
Open Access · CC BY-SA 4.0

Enhanced Dynamic Programming Approaches for Efficient Solutions to the Traveling Salesman Problem

Adriel Moses Anson

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).

AbstractBibliografische AngabenZitierenVerwandte Studien

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}
}
Kostenlos starten →