Branch&Bound

#include <iostream>
#include <vector>
#include <ctime>

typedef std::vector<std::vector<int>> Matrix;

void branch_and_bound_helper(const Matrix& distances, std::vector<int>& path, std::vector<bool>& visited, int distance, int& lower_bound, std::vector<int>& final_path)
{
    const auto depth = path.size();
    const auto last_node = path[depth - 1];

    if (depth == distances.size())
    {
        lower_bound = distance;
        final_path = path;
        //std::cout << distance << std::endl;
    }

    for (size_t i = 0; i < distances.size(); i++)
    {
        if (visited[i])
            continue;

        auto temp_distance = distance + distances[last_node][i];

        if (depth + 1 == distances.size())
            temp_distance += distances[i][path[0]];

        if (lower_bound > temp_distance)
        {
            visited[i] = true;
            path.push_back(i);

            branch_and_bound_helper(distances, path, visited, temp_distance, lower_bound, final_path);

            visited[i] = false;
            path.pop_back();
        }
    }
}

std::pair<int, std::vector<int>> branch_and_bound(const Matrix& distances)
{
    auto path = std::vector<int>(1, 0);
    path.reserve(distances.size());

    auto visited = std::vector<bool>(distances.size(), false);
    visited[0] = true;

    int lower_bound = int(1e9);

    std::vector<int> final_path;

    branch_and_bound_helper(distances, path, visited, 0, lower_bound, final_path);

    return std::make_pair(lower_bound, final_path);
}


int main()
{
    Matrix distances = { {0,56,131,85,123,154,156,198,218,169,235,262,209,262,272,141},
        {56,0,119,65,90,123,149,186,198,150,192,219,157,209,220,87},
        {131,119,0,50,88,81,30,67,115,80,139,184,176,224,239,132},
        {85,65,50,0,40,71,80,124,166,86,151,179,70,122,132,82},
        {123,90,88,40,0,31,106,137,140,77,106,135,112,164,174,45},
        {154,123,81,71,31,0,87,118,103,54,76,101,95,144,54,133},
        {156,149,30,80,106,87,0,35,102,62,120,169,181,230,244,151},
        {198,186,67,124,137,118,35,0,73,73,132,182,212,248,275,182},
        {218,198,115,166,140,103,102,73,0,49,68,147,197,222,260,171},
        {169,150,80,86,77,54,62,73,49,0,54,109,149,175,212,132},
        {235,192,139,151,106,76,120,132,68,54,0,73,166,137,228,149},
        {262,219,184,179,135,101,169,182,147,109,73,0,93,67,156,143},
        {209,157,176,70,112,95,181,212,197,149,166,93,0,57,63,70},
        {262,209,224,122,164,144,230,248,222,175,137,67,57,0,49,122},
        {272,220,239,132,174,54,244,275,260,212,228,156,63,49,0,132},
        {141,87,132,82,45,133,151,182,171,132,149,143,70,122,132,0}
    };
    unsigned int start_time = clock();
    auto result = branch_and_bound(distances);

    std::cout << "Min distance: " << result.first << std::endl;
    std::cout << "Path: ";

    for (auto v : result.second)
    {
        std::cout << v << " ";
    }

    std::cout << std::endl;

    unsigned int end_time = clock(); // конечное время
    unsigned int search_time = end_time - start_time; // искомое время

    std::cout << "Elapsed time:" << search_time / 1000.f;
}