EUVIMEDEUVIMED entdecken
Crossref

Comparison of eleven measures for estimating difficulty of open-loop TSP instances

Lahari Sengupta, Pasi Fränti

Applied Computing and Intelligence · 2021

DOI: 10.3934/aci.2021001 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Applied Computing and Intelligence, 2021. Verfasst von Lahari Sengupta und 1 weiteren Autor:innen. Die Arbeit wurde bisher 4-mal zitiert (Crossref) und nennt 45 Literaturangaben.

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

From the theory of algorithms, we know that the time complexity of finding the optimal solution for a traveling salesman problem (TSP) grows exponentially with the number of targets. However, the size of the problem instance is not the only factor that affects its difficulty. In this paper, we review existing measures to estimate the difficulty of a problem instance. We also introduce MST branches and two other measures called greedy path and greedy gap. The idea of MST branches is to generate minimum spanning tree (MST) and then calculate the number of branches in the tree. A branch is a target, which is connected to at least two other targets. We perform an extensive comparison of 11 measures to see how well they correlate to human and computer performance. We evaluate the measures based on time complexity, prediction capability, suitability, and practicality. The results show that while the MST branches measure is simple, fast to compute, and does not need to have the optimal solution as a reference unlike many other measures. It correlates equally good or even better than the best of the previous measures ‑ the number of targets, and the number of targets on the convex hull.

Zitieren

APA

Sengupta, L., & Fränti, P. (2021). Comparison of eleven measures for estimating difficulty of open-loop TSP instances. Applied Computing and Intelligence. https://doi.org/10.3934/aci.2021001

Vancouver

Sengupta L, Fränti P. Comparison of eleven measures for estimating difficulty of open-loop TSP instances. Applied Computing and Intelligence. 2021. doi:10.3934/aci.2021001

BibTeX
@article{Sengupta2021,
  author = {Sengupta, Lahari and Fränti, Pasi},
  title = {Comparison of eleven measures for estimating difficulty of open-loop TSP instances},
  journal = {Applied Computing and Intelligence},
  year = {2021},
  doi = {10.3934/aci.2021001}
}
Kostenlos starten →