TSP问题

参考文献：

贪心算法：旅行商问题（TSP)
旅行商(TSP)问题专题——多种方法对比
算法设计与分析-TSP六种方法-贪心算法

详细设计：

/*题目描述：TSP（Traveling Salesman Problem ）是指：有一个推销员，要到n个城市推销商品，他要找出一个包含所有n个城市的具有最短路程的环路，是图问题中最广为人知的问题。
TSP的历史很久，最早的描述是1759年欧拉研究的骑士周游问题，即对于国际象棋棋盘中的64个方格，走访64个方格一次且仅一次，并且最终返回到起始点。类似的问题有：

中国邮递员问题（Chinese Postman Problem CPP）
一个邮递员从邮局出发，到所辖街道投递邮件，最后返回邮局，如果他必须走遍所辖的每条街道至少一次，那么他应如何选择投递路线，使所走的路程最短？

配送路线问题（Route of Distribution）
TSP问题在物流中的描述是对应一个物流配送公司，欲将n个客户的订货沿最短路线全部送到，如何确定最短路线。

要求及说明：
(1) 上网查找TSP问题的应用实例；
(2) 分析求TSP问题的全局最优解的时间复杂度；
(3) 将城市网存入文件，运行时从文件读取城市网的信息，文件中应存放顶点数，边数以及每条边，不能直接存放邻接矩阵或者邻接表；
(4) 设计一个求近似解的算法，输出所求的环路，并计算该环路上的总代价；
(5) 采用模块化设计。*/

#include <fstream>
#include <iostream>
#include <string>
using namespace std;
#define MVNum 100 //最大点个数
#define QNum 10   //最大队列数组个数
//边节点声明
typedef struct ArcNode
{
    int adjvex;              //该边所指向的顶点的位置
    int info;                //和边相关的信息
    struct ArcNode *nextarc; //指向下一条边的指针
    struct ArcNode *lastarc; //指向上一条边的指针
} ArcNode, *LinArcNode;

//顶点节点声明
typedef struct VNode
{
    string data;
    LinArcNode firstarc; //指向第一条依附该顶点的边的指针
} VNode, AdjList[MVNum]; // AdjList表示邻接表类型

//邻接表
typedef struct
{
    AdjList vertices;
    int vexnum; //图的顶点数
    int arcnum; //图的边数
} ALGraph;

//队声明
typedef struct Queue
{
    LinArcNode front;
    LinArcNode rear;
} LinkQueue;

//初始化队列
LinkQueue InitQueue(LinkQueue &Q)
{
    Q.front = new ArcNode;
    Q.rear = Q.front;
    Q.rear->nextarc = NULL;
    Q.rear->lastarc = NULL;
    return Q;
}

//进队列
LinkQueue InQueue(LinkQueue &Q, LinArcNode &L) //进队列的是边节点
{
    cout << "进队列：" << L->adjvex << " " << L->info << endl;
    cout << "------------------------ " << endl;

    LinArcNode p = new ArcNode;
    p->adjvex = L->adjvex;
    p->info = L->info;
    p->lastarc = L->lastarc;
    p->nextarc = L->nextarc;

    Q.rear->nextarc = p;
    p->lastarc = Q.rear;
    Q.rear = p;
    return Q;
}

//出队列
LinkQueue OutQueue(LinkQueue &Q, LinArcNode &info)
{
    if (Q.rear == Q.front)
    {
        cout << "队空" << endl;
        return Q;
    }
    LinArcNode p = Q.front->nextarc;
    info = p;
    Q.front->nextarc = p->nextarc;
    if (Q.rear == p)
    {
        Q.rear = Q.front;
    }
    delete p;
    return Q;
}

//判断队空
int QueueEmpty(LinkQueue &Q)
{
    if (Q.front == Q.rear)
    {
        return 1;
    }
    return 0;
}

//返回顶点的位置号
int LocateVex(ALGraph G, string v)
{
    for (int i = 0; i <= G.vexnum; i++)
    {
        if (G.vertices[i].data == v)
        {
            return i;
        }
    }
    return 0;
}

//采用邻接表表示法创建无向图
int CreateUDG(ALGraph &G)
{

    ifstream srcFile("info.txt", ios::in); //以文本模式打开in.txt备读
    if (!srcFile)
    { //打开失败
        cout << "error opening source file." << endl;
        return 0;
    }

    srcFile >> G.vexnum >> G.arcnum; //输入总顶点数，总边数
    for (int i = 1; i <= G.vexnum; i++)
    {
        srcFile >> G.vertices[i].data; //顶点信息
        G.vertices[i].firstarc = NULL;
    }

    int i = 0, j = 0;

    for (int k = 1; k <= G.arcnum; k++)
    {
        string d1, d2;
        int value;
        srcFile >> d1 >> d2 >> value;
        i = LocateVex(G, d1);
        j = LocateVex(G, d2); //确定v1和v2在G中位置，即顶点在G.vertices中的序号

        ArcNode *p1 = new ArcNode; //生成一个新的边节点
        p1->adjvex = j;            //邻接点序号为j
        p1->info = value;
        p1->nextarc = G.vertices[i].firstarc;
        p1->lastarc = NULL;

        if (G.vertices[i].firstarc != NULL)
        {
            G.vertices[i].firstarc->lastarc = p1;
        }
        G.vertices[i].firstarc = p1; //将新结点*p1插入顶点vi的边表头部

        ArcNode *p2 = new ArcNode; //生成一个对称的新的边节点
        p2->adjvex = i;
        p2->info = value;
        p2->nextarc = G.vertices[j].firstarc;
        p2->lastarc = NULL;

        if (G.vertices[j].firstarc != NULL)
        {
            G.vertices[j].firstarc->lastarc = p2;
        }
        G.vertices[j].firstarc = p2; //将新结点*p2插入顶点vj的边表头部
    }
    srcFile.close(); //关闭文件
    return 0;
}

//输出无向图
int OutUDG(ALGraph &G)
{
    cout << "-------------------------------------" << endl;
    cout << "图的邻接表输出：" << endl;
    for (int i = 1; i <= G.vexnum; i++)
    {
        cout << "[" << i << "] ";
        cout << G.vertices[i].data << " ";
        ArcNode *p = G.vertices[i].firstarc;
        while (p)
        {
            cout << p->adjvex << " -> ";
            p = p->nextarc;
        }
        cout << "NULL";
        cout << endl;
    }
    cout << "-------------------------------------" << endl;
    return 0;
}

//返回与起始点相连的路径最小边
int MinArcNode(ALGraph &G, int &begin, bool *visited)
{
    LinArcNode p = G.vertices[begin].firstarc;
    int result = 0;
    if (p != NULL)
    {
        while (visited[p->adjvex]) //开始如果是一个已被访问点，找到其他未被访问点，前提已经假设一定会找到
        {
            p = p->nextarc;
        }
        LinArcNode min = p;

        while (p)
        {
            if (min->info > p->info && !visited[p->adjvex]) //较小且被访问
            {
                min = p;
            }
            p = p->nextarc;
        }
        begin = min->adjvex;
        result = min->info;
    }
    return result;
}

//贪心算法
int TSPGreedy(ALGraph &G, int begin, bool *visited)
{

    int ALLvalue = 0; //总代价
    int B = begin;    //记录出发点
    for (int i = 1; i <= G.vexnum; i++)
    {
        visited[begin] = true;                    //开始点被访问
        cout << G.vertices[begin].data << " -> "; //输出开始点
        if (i == G.vexnum)                        //判断当前节点是否为最后一个节点 ,此处已假设必可以找到一点 ，即没有进入死胡同的情况
        {
            LinArcNode p = G.vertices[B].firstarc; //记录出发点的边链表头指针
            while (begin != p->adjvex)             //判断有没有一条边 和我现在的开始点相连
            {
                p = p->nextarc;
            }
            ALLvalue = ALLvalue + p->info; //找到之后就将路程加上去
        }
        else
        {
            ALLvalue = ALLvalue + MinArcNode(G, begin, visited); //返回前链表的没有被访问的最小边
        }
    }
    cout << G.vertices[B].data << endl;
    return ALLvalue;
}

int main()
{
    ALGraph G;
    bool visited[MVNum] = {false};
    CreateUDG(G);
    OutUDG(G);

    cout << "路线为：";
    int value = TSPGreedy(G, 1, visited);
    cout << "总代价为：" << value << endl;
    return 0;
}