Held–Karp algorithm

The Held–Karp algorithm, also called 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). TSP is an extension of the Hamiltonian circuit problem. The problem can be described as: find a tour of N cities in a country (assuming all cities to be visited are reachable), the tour should (a) visit every city just once, (b) return to the starting point and (c) be of minimum distance.Broadly, the TSP is classified as symmetric travelling salesman problem (sTSP), asymmetric travelling salesman problem (aTSP), and multi-travelling salesman problem (mTSP).The mTSP is generally treated as a relaxed vehicle routing problem. The Held–Karp algorithm, also called 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). TSP is an extension of the Hamiltonian circuit problem. The problem can be described as: find a tour of N cities in a country (assuming all cities to be visited are reachable), the tour should (a) visit every city just once, (b) return to the starting point and (c) be of minimum distance.Broadly, the TSP is classified as symmetric travelling salesman problem (sTSP), asymmetric travelling salesman problem (aTSP), and multi-travelling salesman problem (mTSP).The mTSP is generally treated as a relaxed vehicle routing problem. sTSP: Let V = {v1 ,..., vn } be a set of cities, E = {( r, s ) : r, s ∈ V } be the edge set, and drs = dsr be a cost measure associated with edge ( r, s ) ∈ E. aTSP: If drs ≠ dsr for at least one ( r, s ) then the sTSP becomes an aTSP.The aTSP and sTSP are defined on different graphs – complete directed and undirected. sTSP can be considered, in many cases, as a subproblem of the aTSP. mTSP: The mTSP is defined as: In a given set of nodes, let there be m salesmen located at a single depot node. The remaining nodes (cities) that are to be visited are intermediate nodes. Then, the mTSP consists of finding tours for all m salesmen, who all start and end at the depot, such that each intermediate node is visited exactly once and the total cost of visiting all nodes is minimized.