Branch and bound- vad händer vid optimering?

 0, 22,  8,  6, 18,  7, 16,  9, 11, 13, 20, 16, 18, 22, 23, 24, 24, 25, 25, 26, 28, 29, 29
22,  0, 14, 18,  4, 20,  6, 14, 14, 14, 11, 20, 15, 19, 20, 21, 21, 22, 22, 23, 25, 26, 26
 8, 14,  0,  4, 10,  6,  8,  4,  6,  8, 12, 11, 13, 17, 18, 19, 19, 20, 20, 21, 23, 24, 24
 6, 18,  4,  0, 14,  2, 12,  4,  5,  7, 16, 10, 12, 16, 17, 18, 18, 19, 19, 20, 22, 23, 23
18,  4, 10, 14,  0, 16,  2, 10, 10, 10,  8, 16, 12, 16, 17, 18, 18, 19, 19, 20, 22, 23, 23
 7, 20,  6,  2, 16,  0, 14,  6,  6,  6, 18,  9, 14, 15, 16, 17, 17, 18, 20, 19, 21, 22, 22
16,  6,  8, 12,  2, 14,  0,  8,  8,  8,  6, 14, 10, 14, 15, 16, 16, 17, 17, 18, 20, 21, 21
 9, 14,  4,  4, 10,  6,  8,  0,  2,  4, 12,  7,  9, 13, 14, 15, 15, 16, 16, 17, 19, 20, 20
11, 14,  6,  5, 10,  6,  8,  2,  0,  2, 12,  6,  8, 11, 12, 13, 13, 14, 14, 15, 17, 18, 18
13, 14,  8,  7, 10,  6,  8,  4,  2,  0, 12,  6,  8,  9, 10, 11, 11, 12, 14, 13, 15, 16, 16
20, 11, 12, 16,  8, 18,  6, 12, 12, 12,  0, 18,  4, 12,  9, 16, 10, 12, 11, 12, 14, 15, 15
16, 20, 11, 10, 16,  9, 14,  7,  6,  6, 18,  0, 14,  6, 10,  8, 14,  9, 20, 10, 14, 13, 13
18, 15, 13, 12, 12, 14, 10,  9,  8,  8,  4, 14,  0,  8,  5, 12,  6,  8,  7,  8, 10, 11, 11
22, 19, 17, 16, 16, 15, 14, 13, 11,  9, 12,  6,  8,  0,  4,  4,  8,  3, 14,  4,  8,  7,  7
23, 20, 18, 17, 17, 16, 15, 14, 12, 10,  9, 10,  5,  4,  0,  8,  4,  4, 10,  3,  5,  6,  6
24, 21, 19, 18, 18, 17, 16, 15, 13, 11, 16,  8, 12,  4,  8,  0, 12,  4, 18,  8, 12, 10, 10
24, 21, 19, 18, 18, 17, 16, 15, 13, 11, 10, 14,  6,  8,  4, 12,  0,  8,  6,  4,  4,  5,  5
25, 22, 20, 19, 19, 18, 17, 16, 14, 12, 12,  9,  8,  3,  4,  4,  8,  0, 14,  4,  8,  6,  6
25, 22, 20, 19, 19, 20, 17, 16, 14, 14, 11, 20,  7, 14, 10, 18,  6, 14,  0, 10,  6,  8,  8
26, 23, 21, 20, 20, 19, 18, 17, 15, 13, 12, 10,  8,  4,  3,  8,  4,  4, 10,  0,  4,  3,  3
28, 25, 23, 22, 22, 21, 20, 19, 17, 15, 14, 14, 10,  8,  5, 12,  4,  8,  6,  4,  0,  2,  2
29, 26, 24, 23, 23, 22, 21, 20, 18, 16, 15, 13, 11,  7,  6, 10,  5,  6,  8,  3,  2,  0,  0
29, 26, 24, 23, 23, 22, 21, 20, 18, 16, 15, 13, 11,  7,  6, 10,  5,  6,  8,  3,  2,  0,  0

#include <algorithm>
#include <climits>
#include <cmath>
#include <cstdint>
#include <cstring>
#include <iostream>
#include <memory>
#include <sstream>
#include <string>
#include <vector>

#define EMPTY_EDGE_SET   0
#define MAX_PATH_COST    (INT_MAX / 2)
#define UNSET_EDGE       (-1)

static std::vector<std::string> args;

typedef int                     cost_t;
typedef int                     edge_t;
typedef std::vector<edge_t>     Path;
typedef uint32_t                EdgeSet;
typedef std::vector<EdgeSet>    EdgeSets;

static std::ostream& operator<<(std::ostream &os, Path &path)
    {
    os << "[ ";
    for (auto edge: path)
        {
        os << edge << ' ';
        }
    os << "]";
    return os;
    }

static std::string edgeSetToString(EdgeSet set)
    {
    std::stringstream repr;
    int i = 1;

    repr << "[ ";
    while (set != 0)
        {
        if ((set & 1) != 0)
            {
            repr << i << ' ';
            }
        i++;
        set >>= 1;
        }
    repr << "]";
    return repr.str();
    }

static void combWithLen(int n, int k, int first, EdgeSet vs, EdgeSets &acc)
    {
    if (k > __builtin_popcount(vs))
        {
        for (int x = first; x < n; x++)
            {
            auto v = vs;
            v |= (1 << x);
            combWithLen(n, k, x + 1, v, acc);
            }
        }
    else
        {
        acc.push_back(vs);
        }
    }

static EdgeSets comb(int n, int k)
    {
    EdgeSets combs;
    combWithLen(n, k, 0, 0, combs);
    return combs;
    }


class CostMatrix
    {
    std::vector<cost_t> c_;
    int                 dim_;
public:
    CostMatrix()
        {
        std::string line;
        while (!std::getline (std::cin, line).eof())
            {
            auto l = std::unique_ptr<char>(new char [line.length() + 1]);
            std::strcpy (l.get(), line.c_str());

            for (auto p = std::strtok (l.get(), ",");
                 p != nullptr;
                 p = std::strtok (nullptr, ","))
                {
                c_.push_back(std::stod(std::string(p)));
                }
            }
        dim_ = std::sqrt(c_.size());
        }

    int dim() const
        {
        return dim_;
        }

    cost_t get(int row, int col) const
        {
#ifdef NDEBUG
        return c_[row * dim_ + col];
#else
        return c_.at(row * dim_ + col);
#endif
        }
    };

struct AccCost
    {
    cost_t cost;
    edge_t from;
    };

class AccCostMatrix
    {
    CostMatrix           &dists_;
    std::vector<AccCost> c_;
    int                  dim_;

    void update(edge_t from, edge_t to, EdgeSet vs = EMPTY_EDGE_SET)
        {
        cost_t thisCost = dists_.get(from, to);

        if (from > 0)
            {
            auto fromIdx = vs * dim_ + (from - 1);
            thisCost += c_[fromIdx].cost;
            }

        to--;
        auto toIdx = (vs | (1 << to)) * dim_ + to;
        if (c_[toIdx].cost > thisCost)
            {
            c_[toIdx].cost = thisCost;
            c_[toIdx].from = from;
            }
        }

    AccCost get(edge_t from, EdgeSet visited) const
        {
#ifdef NDEBUG
        return c_[visited * dim_ + from - 1];
#else
        return c_.at(visited * dim_ + from - 1);
#endif
        }

public:
    AccCostMatrix(CostMatrix &dists) : dists_(dists)
        {
        // Edge 0 is not included, always set as start/end
        dim_ = dists.dim() - 1;
        auto init = AccCost{MAX_PATH_COST, UNSET_EDGE};
        c_.resize((1 << dim_) * dim_, init);
        }

    std::tuple<cost_t, Path> shortestPath ()
        {
        // First step, paths from start to all edges
        for (int k = 1; k <= dim_; k++)
            {
            update(0, k);
            }
        // Branch-and-bound, every subpath of a path of minimum distance is
        // itself of minimum distance.
        for (int s = 2; s < dim_ + 1; s++)
            {
            auto combs = comb(dim_, s);
#pragma omp parallel for
            for (int i = 0; i < combs.size(); i++)
                {
                auto subset = combs[i];
                EdgeSet kIter = subset;
                for (int k = 0; kIter != 0; k++, kIter >>= 1)
                    {
                    if ((kIter & 1) == 0)
                        {
                        continue;
                        }
                    EdgeSet prev = subset & ~(1 << k);
                    EdgeSet mIter = subset;
                    for (int m = 0; mIter != 0; m++, mIter >>= 1)
                        {
                        if (k != m)
                            {
                            update(m + 1, k + 1, prev);
                            }
                        }
                    }
                }
            }
        // Lastly, calculate cost from all shortest path to all edges back to
        // the starting point
        EdgeSet visited = (1 << dim_) - 1;
        Path    path(dim_ + 2);
        cost_t  cost = MAX_PATH_COST;
        AccCost accCost;
        for (int k = 1; k <= dim_; k++)
            {
            accCost = get(k, visited);
            int thisCost = accCost.cost + dists_.get(k, 0);
            if (cost > thisCost)
                {
                cost = thisCost;
                path[1] = k;
                }
            }
        // Backtrack to initial edge
        int step = 2;
        accCost = get(path[1], visited);
        while (accCost.from != 0)
            {
            path[step] = accCost.from;
            visited &= ~(1 << (path[step-1] - 1));
            accCost = get(accCost.from, visited);
            step++;
            }
        std::reverse(path.begin(), path.end());
        return std::make_tuple(cost, path);
        }
    };

int main(int argc, char *argv[])
    {
    args = std::vector<std::string>(argv + 1, argv + argc);
    auto cost_matrix = CostMatrix();
    auto c = AccCostMatrix(cost_matrix);
    cost_t cost;
    Path path;
    std::tie(cost, path) = c.shortestPath();
    std::cout << cost << ' ' << path << '\n';
    }