Get Math Help

GET TUTORING NEAR ME!

(800) 434-2582

By submitting the following form, you agree to Club Z!'s Terms of Use and Privacy Policy

    Home / Get Math Help

    Traveling Salesman Problem

    Statement

    Let C be a set of m cities with distances d(c_i, c_j) element Z^+ for each pair of cities c_i, c_j element C, and let B be a positive integer. Then the traveling salesman problem asks if there is a tour of C having length B or less, i.e., a permutation <c_π(1), c_π(2), ..., c_π(m)> of C such that sum_(i=1)^(m - 1)d(c_π(i), c_π(i + 1)) + d(c_π(m), c_π(1))<=B.

    Alternate name

    TSP

    History

    status | proved NP-complete

    Classes

    NP complete problems | NP problems | mathematical problems | solved mathematics problems

    Back to List | POWERED BY THE WOLFRAM LANGUAGE