Attempting to solve the Travelling Salesman Problem using idiomatic C++

Question

Please tell me anything that comes to mind. However, I am most interested in ways to make my code more idiomatic (modern) C++.

tsp.h:

//  File:    tsp.h
//  Author:  Rodion "rodde" Efremov; Aug 21, 2016
//  License: there is no such, you can use it freely in your projects. However,
//           if the code in this file fails, I am not to be held responsible.

#ifndef TSP_H
#define TSP_H
#include <vector>

namespace net {

namespace coderodde {

namespace tsp {

    //////////////////////////////////////////
     //// Computes the length of a tour. ////
    //////////////////////////////////////////
    double
    get_tour_length(const std::vector<int>& tour,
                    const std::vector<std::vector<double>>& distance_matrix);

    ////////////////////////////////////////////////////////////////////////////
       //// Solves the travelling salesman problem. The undirected graph  ////
      //// is specified by the adjacency matrix, that is expected to be  ////
     //// a square matrix.                                              ////
    ////////////////////////////////////////////////////////////////////////////
    std::vector<int>
    travelling_salesman(std::vector<std::vector<double>>& distance_matrix);

} // End of net::coderodde::tsp

} // End of net::coderodde

} // End of net

#endif // TSP_H

tsp.cpp:

//  File:    tsp.cpp - implementation of tsp.h
//  Author:  Rodion "rodde" Efremov; Aug 21, 2016
//  License: there is no such, you can use it freely in your projects. However,
//           if the code in this file fails, I am not to be held responsible.

#ifndef TSP_H
#define TSP_H
#include "tsp.h"
#include <vector>

namespace net {

    namespace coderodde {

        namespace tsp {

            //////////////////////////////////////////
            //// Computes the length of a tour. ////
            //////////////////////////////////////////
            double
            get_tour_length(const std::vector<int>& tour,
                            const std::vector<std::vector<double>>& distance_matrix)
            {
                double tour_length = 0.0;

                for (size_t index = 0; index < tour.size(); ++index)
                {
                    const size_t next_index = (index + 1) % tour.size();
                    const int node = tour[index];
                    const int next_node = tour[next_index];
                    tour_length += distance_matrix[node][next_node];
                }

                return tour_length;
            }

            ////////////////////////////////////////////////////////////////////////////
            //// Solves the travelling salesman problem. The undirected graph  ////
            //// is specified by the adjacency matrix, that is expected to be  ////
            //// a square matrix.                                              ////
            ////////////////////////////////////////////////////////////////////////////
            std::vector<int>
            travelling_salesman(std::vector<std::vector<double>>& distance_matrix)
            {
                int n = 0;
                std::vector<int> ret(distance_matrix.size());
                std::generate(ret.begin(), ret.end(), [&n]{ return n++; });
                std::vector<int> best_tour;
                double best_tour_length = std::numeric_limits<double>::max();

                do
                {
                    double tentative_tour_length = get_tour_length(ret, distance_matrix);

                    if (best_tour_length > tentative_tour_length)
                    {
                        best_tour_length = tentative_tour_length;
                        best_tour = ret;
                    }
                } while (std::next_permutation(ret.begin(), ret.end()));

                return best_tour;
            }


        } // End of net::coderodde::tsp

    } // End of net::coderodde

} // End of net

#endif // TSP_H

main.cpp:

#include <iostream>
#include <vector>
#include "tsp.h"

using net::coderodde::tsp::get_tour_length;
using net::coderodde::tsp::travelling_salesman;

/*******************************************************************************
 * The demo graph is a clique of 4 nodes with the following weights:
 *
 * a - b: 4
 * a - c: 1
 * a - d: 6
 * b - c: 5
 * b - d: 3
 * c - d: 2
 *******************************************************************************/
int main(int argc, char** argv) {
    std::vector<std::vector<double>> distance_matrix = {
        // a, b, c, d:
        { 0.0, 4.0, 1.0, 6.0 }, // a
        { 4.0, 0.0, 5.0, 3.0 }, // b
        { 1.0, 5.0, 0.0, 2.0 }, // c
        { 6.0, 3.0, 2.0, 0.0 }  //
    };

    std::vector<int> best_tour = travelling_salesman(distance_matrix);
    std::cout << "Best tour: ";

    for (auto i : best_tour)
    {
        std::cout << i << " -> ";
    }

    std::cout << best_tour[0]
              << ", cost: "
              << get_tour_length(best_tour, distance_matrix)
              << std::endl;
    return 0;
}

Answer 1

In your get_tour_length function, I would rewrite the loop as follows:

for(size_t index = 1; index < tour.size(); ++index)
{
    int node = tour[index];
    int prev_node = tour[index-1];
    tour_length += distance_matrix[prev_node][node];
}
tour_length += distance_matrix[0][tour.size() - 1];

It doesn't make sense to use the % operator in the loop because the condition under which it does anything occurs exactly once and it occurs at the end. Putting it inside the loop is just wasting an extra cpu cycle for a mod operation that does nothing (N-1) times. Instead of someone having to parse what exactly the mod is doing during the loop, it's very explicit now that the same thing happens a number of times during the loop (adding two adjacent nodes), and then it is explicit that at the end, we add the first and last node.

Also, it is good that you are being const conscious but using const on the variables inside the loop isn't really accomplishing anything.

I don't know why you need 3 levels of namespaces, but if you have other code, then you are free to organize it how you wish.