data.txt

14
0	633	257	91	412	150	80	134	259	505	353	324	70	211
633	0	390	661	227	488	572	530	555	289	282	638	567	466
257	390	0	228	169	112	196	154	372	262	110	437	191	74
91	661	228	0	383	120	77	105	175	476	324	240	27	182
412	227	169	383	0	267	351	309	338	196	61	421	346	243
150	488	112	120	267	0	63	34	264	360	208	329	83	105
80	572	196	77	351	63	0	29	232	444	292	297	47	150
134	530	154	105	309	34	29	0	249	402	250	314	68	108
259	555	372	175	338	264	232	249	0	495	352	95	189	326
505	289	262	476	196	360	444	402	495	0	154	578	439	336
353	282	110	324	61	208	292	250	352	154	0	435	287	184
324	638	437	240	421	329	297	314	95	578	435	0	254	391
70	567	191	27	346	83	47	68	189	439	287	254	0	145
211	466	74	182	243	105	150	108	326	336	184	391	145	0

DynamicProgrammingTSP.cpp

//
// Created by Chen on 2016-12-24.
//

#include "DynamicProgrammingTSP.h"
#include <set>
#include <map>

using namespace std;

DynamicProgrammingTSP::DynamicProgrammingTSP(const std::string &data_filename) : TSP(data_filename) {}

int
DynamicProgrammingTSP::solve() {
    set<int>                      empty, others;
    /*用于记录子阶段的结果的map*/
    map<pair<int, set<int>>, int> results;

    /*初始化S为空集时的状态*/
    for (auto i = 1; i < m_ncitys; ++i) {
        results[make_pair(i, empty)] = m_cost[i][0];
        others.insert(i);
    }

    /*动态更新*/
    /*考虑S为1~n-1个城市集的结果*/
    for (auto size_of_citys_set = 1; size_of_citys_set < m_ncitys; ++size_of_citys_set) {
        /*对每一个城市*/
        for (auto city = 0; city < m_ncitys; ++city) {
            /*当有n-1个城市时，初始城市只能为0，故当0已经被处理时直接跳出循环即可*/
            if (size_of_citys_set == m_ncitys - 1 && city != 0) {
                break;
            }

            /*获取所有大小为size_of_citys_set(不包括当前城市和城市0)的城市集*/
            auto city_sets = get_possible_city_sets(city, size_of_citys_set);

            /*对每一个城市集，利用公式g(i,S) = min(L(i,j) + g(j, S-{j})) 来找到其最优解*/
            for (const auto &city_set: city_sets) {
                int min_cost = 0x7FFFFFFF;

                for (const auto &j: city_set) {
                    /*获得除去该城市的城市集合*/
                    set<int> tmp(city_set);
                    tmp.erase(j);

                    /*更新最小值*/
                    min_cost = min(min_cost, m_cost[city][j] + results[make_pair(j, tmp)]);
                }

                /*设置最优解*/
                results[make_pair(city, city_set)] = min_cost;
            }
        }
    }

    /*返回最优解 g(0, V-{0})*/
    return results[make_pair(0, others)];
}

/*获取可能的其余城市组合的集合*/
set<set<int>>
DynamicProgrammingTSP::get_possible_city_sets(int city, int size_of_citys_set) {
    vector<int> candidates;
    for (auto   i = 1; i < m_ncitys; ++i) {
        if (i != city) {
            candidates.push_back(i);
        }
    }

    return getSet(candidates, size_of_citys_set);
}

std::set<std::set<int>>
DynamicProgrammingTSP::getSet(std::vector<int> citys, int count) {
    set<set<int>> results;
    auto          tmp = set<int>();
    comb(results, citys, tmp, 0, count);

    return results;
}

void
DynamicProgrammingTSP::comb(std::set<std::set<int>> &results, const std::vector<int> &citys, std::set<int> &tmp,
                            int offset, int rem_count) {
    if (rem_count == 0) {
        results.insert(tmp);
        return;
    }

    for (auto i = offset; i <= citys.size() - rem_count; ++i) {
        tmp.insert(citys[i]);
        comb(results, citys, tmp, i + 1, rem_count - 1);
        tmp.erase(citys[i]);
    }
}

DynamicProgrammingTSP.h

//
// Created by Chen on 2016-12-24.
//

#ifndef TSP_DP_DYNAMICPROGRAMMINGTSP_H
#define TSP_DP_DYNAMICPROGRAMMINGTSP_H

#include "TSP.h"

class DynamicProgrammingTSP: public TSP {
public:
    DynamicProgrammingTSP(const std::string &data_filename);

    int solve() override;

    std::set<std::set<int>> get_possible_city_sets(int city, int i);

    std::set<std::set<int>> getSet(std::vector<int> citys, int count);

    void comb(std::set<std::set<int>> &results, const std::vector<int> &citys, std::set<int> &tmp, int offset, int rem_count);
};


#endif //TSP_DP_DYNAMICPROGRAMMINGTSP_H

main.cpp

#include <iostream>
#include <chrono>

using namespace std;

#include "DynamicProgrammingTSP.h"

int main() {
    /*计算开始时间*/
    auto start = std::chrono::system_clock::now();

    string data_path("E:\\baiduyun\\Codes\\C++\\tsp-dp\\data.txt");

    /*初始化对象*/
    DynamicProgrammingTSP tsp(data_path);

    /*获得结果*/
    cout << "result : " << tsp.solve() << endl;

    /*计算结束时间*/
    auto end     = std::chrono::system_clock::now();
    /*获得程序总运行时间*/
    auto elapsed = std::chrono::duration_cast<std::chrono::milliseconds>(end - start);
    std::cout << elapsed.count() << " milliseconds\n";
    return 0;
}

TSP.cpp

//
// Created by Chen on 2016-12-24.
//

#include "TSP.h"
#include <iostream>
#include <fstream>
#include <iterator>
#include <vector>

using namespace std;

TSP::TSP(const std::string &data_filename){
    /*读取数据*/
    ifstream data_file(data_filename);

    /*初始化城市个数*/
    data_file>>m_ncitys;

    /*初始化城市间距离*/
    for(auto row=0;row<m_ncitys;++row){
        m_cost.push_back(vector<int>(m_ncitys));
        for(auto col=0;col<m_ncitys;++col){
            data_file>>m_cost[row][col];
        }
    }

    /*测试数据读取*/
//    for(auto &row: m_cost){
//        copy(row.cbegin(),row.cend(),ostream_iterator<int>(cout, " "));
//        cout<<endl;
//    }
    cout<<"-------load data finished--------"<<endl;
}

TSP.h

//
// Created by Chen on 2016-12-24.
//

#ifndef TSP_DP_TSP_H
#define TSP_DP_TSP_H


#include <vector>
#include <map>
#include <set>

class TSP {
    using matrix = std::vector<std::vector<int>>;
public:
    TSP(const std::string &data_filename);

    virtual ~TSP(){};
    virtual int solve()=0;
//    void printPath();

protected:
    /*城市的个数*/
    std::size_t m_ncitys;

    /*城市间的费用*/
    matrix m_cost;
};


#endif //TSP_DP_TSP_H