lzx1413's blog

动态规划算法求解旅行商问题

Posted on | | Visitors

使用动态规划求解旅行商问题，即寻找一条最短路径，访问且仅访问一次所有的城市。只是一个完全NP问题，目前没有多项式时间解法，使用动态规划时求最优解的可行方法之一。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <set>
#include <vector>
#define NODE_NUM  6//城市节点数
using namespace std;
static const int dis[NODE_NUM][NODE_NUM] = {
    0,10,20,30,40,50,
    12,0,18,30,25,21,
    23,19,0,5,10,15,
    34,32,4,0,8,16,
    45,27,11,10,0,18,
    56,22,16,20,12,0
};//测试数据
struct Status {
    int curcity;//当前城市编号
    vector<int> unvisited;//已经访问城市编号集
    set<int> type;//已访问城市编号排序结果
    int distance;//当前城市到最后的城市1的距离
    bool contain(int i)//已访问该城市返回true
    {
        if (i == curcity)
            return true;
        else
        {
            for (auto index : unvisited)
            {
                if (index == i)
                    return true;
            }
        }
        return false;
    }
};
void printStatus(const vector<Status>&status_vec)
{
    for (auto status : status_vec)
    {
        cout << status.curcity << " " << endl;
        for (auto city : status.unvisited)
        {
            cout << city << " ";
truetrue}
        cout << ">> distance " << status.distance << endl;
    }
}
//合并相同状态 当已访问城市相同时，只保存距离最小的
vector<Status> combine(vector<Status> vec)
{
    vector<Status> new_vec;
    Status temp;
    vector<bool> flag(vec.size(),true);
    bool init_flag = false;
    for (int i = 0; i < vec.size(); ++i)
    {
        if (!flag[i])
            continue;
        else if (flag[i]&&!init_flag)
        {
            temp = vec[i];
            flag[i] = false;
            init_flag = true;
            for (int j = i + 1; j < vec.size(); ++j)
            {
                if (temp.curcity == vec[j].curcity&&temp.type == vec[j].type)
                {
                    if (vec[j].distance < temp.distance)
                        temp = vec[j];
                    flag[j] = false;
                }
            }
            new_vec.push_back(temp);
            init_flag = false;
        }
    }
    return new_vec;
}
int main()
{
    vector<Status> pre_vector;
    vector<Status> cur_vector;
    //初始化
    for (int i = 1; i < NODE_NUM; i++)
    {
        Status temp;
        temp.curcity = i;
        temp.distance = dis[i][0];
        cout << temp.distance << endl;
        cur_vector.push_back(temp);
    }
    //逆推
    for (int j = 0; j < NODE_NUM-2; j++)
    {
        pre_vector = cur_vector;
        cur_vector.clear();
        for (int i = 1; i < NODE_NUM; i++)
        {
            for (auto temp : pre_vector)
            {
                if (!temp.contain(i))//访问新城市
                {
                    Status new_stat = temp;
                    vector<int>::iterator int_iter = new_stat.unvisited.begin();
                    new_stat.unvisited.insert(int_iter,new_stat.curcity);
                    new_stat.type.insert(new_stat.curcity);
                    new_stat.distance += dis[i][new_stat.curcity];
                    new_stat.curcity = i;
                    cur_vector.push_back(new_stat);
                }
            }
    }
    cur_vector = combine(cur_vector);
    }
    //获取最短路径
    Status shortest=cur_vector[0];
    int min_dis=shortest.distance+dis[0][shortest.curcity];
    for(auto status : cur_vector)
    {
        int temp_dis=dis[0][status.curcity]+status.distance;
        if(temp_dis<min_dis)
        {
            min_dis=temp_dis;
            shortest=status;
        }    
    }
    //打印结果
    vector<int>::iterator iter_city;
    cout<<"minimum distance is "<<min_dis<<endl;
    cout<<"the shortest path is "<<"1 "<<shortest.curcity+1;
    for(iter_city=shortest.unvisited.begin();iter_city!=shortest.unvisited.end();iter_city++)
        cout<<" "<<*iter_city+1;
    cout<<" 1"<<endl;
    getchar();
    return 0;
}

输出结果为：

$\alpha$

1 2 6 5 4 3 1
参考资料(http://blog.csdn.net/zouxinfox/article/details/1917107)