深度优先搜索算法求解TSP问题（搜索算法） （新）

深度优先搜索算法求解TSP问题（搜索算法） （新）

【问题描述】采用深度优先搜索算法求解TSP问题，并在搜索过程中，使用界限条件（当前结点已经走过的路径长度要小于已求得的最短路径）进行“剪枝”操作（不再对后续结点进行遍历），从而提高搜索效率。采用queue模块中的栈（LifoQueue）来实现深度优先搜索。

【输入形式】在屏幕上输入顶点个数和连接顶点间的边的邻接矩阵。

【输出形式】最优值和其中一条最优路径。

【样例输入】

4

0 30 6 4

30 0 5 10

6 5 0 20

4 10 20 0

【样例输出】

[1]

[1, 2]

[1, 2, 3]

[1, 2, 3, 4]

[1, 2, 4]

[1, 3]

[1, 3, 2]

[1, 3, 2, 4]

[1, 4]

[1, 4, 2]

[1, 4, 2, 3]

[1, 4, 3]

25: [1, 3, 2, 4]

【样例说明】

 输入：顶点个数为4。连接顶点间边的邻接矩阵大小为4行4列，位置[i,j]上元素值表示第i个顶点到第j个顶点的距离，0表示两个顶点间没有边连接。

 输出：最优值为25，最优路径为[1, 3, 2, 4]。

#include<iostream>
using namespace std;
int n, sum = 0, bests = 6728;
int A[15][15] = { 6728 };
int now[15] = { 1 };
int bestw[15] = { 1 };
void output(int m)
{
    cout << "[";
    for (int i = 1; i < m; i++)
        cout << now[i] << ", ";
    cout<<now[m]<<"]"<<endl;
}
void swap(int m)
{
    for (int i = 1; i <= m; i++)
        bestw[i] = now[i];
}
void swap(int& a, int& b)
{
    int t; t = a; a = b; b = t;
}
void dfs(int step)
{
    if (step > n )//判断边界
    {
        if (sum  + A[now[n]][1] < bests)
        {
            bests = sum  + A[now[n]][1];
            swap(n);
        }
    }
    else
    {
        for (int i = step; i <= n; i++)//遍历每一种情况
        {
            if  (A[now[step - 1]][now[i]] != 0&&sum + A[now[step - 1]][now[i]] < bests)//check满足
            {
                sum += A[now[step - 1]][now[i]];
                swap(now[step], now[i]);
                if (step == 2 && now[i] == 4) 
                    swap(now[3], now[4]); 
                output(step);
                dfs(step + 1);//继续搜索
                sum -= A[now[step-1 ]][now[step]];
                swap(now[step], now[i]);
            }
        }
    }
    return;
}

int main( )
{
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            cin >> A[i][j];
        now[i] = i;
    }
    cout <<"[1]" << endl;
    dfs(2);//从第2个箱子开始
    cout << bests << ": [1";
    for (int i = 2; i <= n; i++)
        cout << ','<< bestw[i] ;
    cout << "]";
    return 0;
}