Category Travelling Salesperson Problem

(See also: all categories, featured categories, featured articles, all articles. Sort articles by name, created, edited)

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that a visitor can take to see each city exactly once and return to their city of origin?

Imagine a travelling staypuft marshmallow man (smm) who is tasked with stepping on each church in a given town. Given the Smm has a slow lumbering gate and is susceptible to attacks from ghostbuster franchisees, he wishes to minimize the distance travelled. Devise an algorithm to determine the minimal path the Smm can take.

Sources

• Wikipedia: Travelling Salesperson Problem (tsp)