Traveling Salesman Problem

AKA, Robots Shortest Tour.

Context:

Input: Some set of 2D Cartesian coordinates.

Output: The minimum distance such that all points are visited.

The First Reveal: Brute Force

The general idea is to generate a complete graph from the set of points. We define a complete graph a simple undirected graph in which every pair of distinct vertices is connected by a unique edge.

What this effectively produces is a graph with complete freedom. The robot is not constrained to the path it could take, but we'll leave it to the greedy algorithm to take care of the rest. Running a MST algorithm on this graph will then generate the minimum weight of all distances, such that all nodes are linked.

Of course, we'd have to cover distance between each edge in the process.

Consider the complete graph above, with a radius of 10. We then obtain:

      -5 9(0) : 10 0-17, 0 10-5, -5 -9-18, 5 9-10, 5 -9-20, -10 0-10, 0 -10-19,
      10 0(0) : -5 9-17, 0 10-14, -5 -9-17, 5 9-10, 5 -9-10, -10 0-20, 0 -10-14,
      0 10(0) : -5 -9-19, 5 9-5, -5 9-5, 10 0-14, 5 -9-19, -10 0-14, 0 -10-20,
     -5 -9(0) : -5 9-18, 10 0-17, 0 10-19, 5 9-20, 5 -9-10, -10 0-10, 0 -10-5,
       5 9(0) : -5 9-10, 10 0-10, 0 10-5, 5 -9-18, -10 0-17, 0 -10-19, -5 -9-20,
      5 -9(0) : -5 9-20, 10 0-10, 0 10-19, -5 -9-10, 5 9-18, -10 0-17, 0 -10-5,
     -10 0(0) : -5 9-10, 10 0-20, 0 10-14, -5 -9-10, 5 9-17, 5 -9-17, 0 -10-14,
     0 -10(0) : -5 9-19, 10 0-14, 0 10-20, -5 -9-5, 5 9-19, 5 -9-5, -10 0-14,

And our MST algorithm should generate:

        ID    WEIGHT PARENT_ID
      10 0        10       5 9
      -5 9         5      0 10
      0 10         0      null
     -5 -9         5     0 -10
       5 9         5      0 10
     0 -10         5      5 -9
     -10 0        10      -5 9
      5 -9        10      10 0

                  min_weight: 50

Which is correct, and makes sense: the more points we add along $x^2+y^2=r^2$ should converge towards $2 \pi r$.

Implementation

• I've assumed use of my MST algorithm in my Data Structures and Algorithms Book. Here are the features I've added in:

class Graph {
    Graph(const vector<pair<int, int>> &coords) {
        generate_complete_graph(coords);
    }

    ...

    void db_print_points(const pair<string, vector<pair<string, int>>> &points) {
        cout << "---(" << points.first << ")---: ";
        for (auto i : points.second)
            cout << "(" << i.first << " " << i.second << ")";
        cout << "\n\n";
    }

    int distance(const pair<int, int> &p1, const pair<int, int> &p2)
    {
        return sqrt(pow(p1.first - p2.first, 2) + pow(p1.second - p2.second, 2));
    }

    void generate_complete_graph(const vector<pair<int, int>> &points)
    {
        for (int i = 0; i < points.size(); i++) {

            string main_id = to_string(points[i].first) + " " + to_string(points[i].second);
            vector<pair<string, int>> coords;
            pair<string, vector<pair<string, int>>> cmpt_cord_set;

            // j != i; doesnt connected to itself redundently
            for (int j = 0; j < points.size(); j++) {
                if (j == i) continue;
                string match_id = to_string(points[j].first) + " " + to_string(points[j].second);
                int dist = distance(points[i], points[j]);
                coords.push_back({ match_id, dist });

            }

            cmpt_cord_set.first = main_id;
            cmpt_cord_set.second = coords;

            //db_print_points(cmpt_cord_set);
            //pause();

            add_hash_list(cmpt_cord_set);
        }
    }
}


void test()
{
    cout << "\n\n";

    vector<pair<int, int>> coordinates = { {0, 10},{5, 9},{10, 0},{5, -9},
                                           {0, -10},{-5, -9},{-10, 0},{-5, 9}};

    Graph g(coordinates);
    g.traverse_all();

    unordered_map<string, MST_info> test = g.MST_prims(Node("0 10"));
    print_MST(test);

}

int main()
{
    test();
}