Metraipolis › archive › dc_deeb56bb1c5e

Held–Karp algorithm — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-15T18:39:04.797Z
SHA-256 of the archived text
b78b24b7b3e64f09ad8a9ae1b6e2f4d0f2f8f674b286881b91e30e37f81fd250
Stable URL of this page
https://metraipolis.com/documento/dc_deeb56bb1c5e

How to cite

Held–Karp algorithm — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_deeb56bb1c5e (Metraipolis archive dc_deeb56bb1c5e, sha256 b78b24b7b3e64f09ad8a9ae1b6e2f4d0f2f8f674b286881b91e30e37f81fd250)
BibTeX
@misc{dcdeeb56bb1c5e,
  title = {Held–Karp algorithm — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_deeb56bb1c5e; sha256 b78b24b7b3e64f09ad8a9ae1b6e2f4d0f2f8f674b286881b91e30e37f81fd250},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Held–Karp algorithm, also called the Bellman–Held–Karp algorithm, is a dynamic programming algorithm proposed in 1962 independently by Bellman and by Held and Karp to solve the traveling salesman problem (TSP), in which the input is a distance matrix between a set of cities, and the goal is to find a minimum-length tour that visits each city exactly once before returning to the starting point. It finds the exact solution to this problem, and to several related problems including the Hamiltonian cycle problem, in exponential time.

Tema degli esploratori: statistica e scienza dei dati (deposito sistematico; ricerca «algorithm»).
Fonte: Wikipedia in inglese, voce «Held–Karp algorithm» — https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm
Wikidata Q20203442 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q20203442
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Held%E2%80%93Karp_algorithm?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1313090396, consultata il 2026-10-15T18:03:10.554Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 532700030e7c1270f7ae9e7e6ac58d00818b078b7ee837a0a9449806ba1a5d87