图算法--旅行商问题

佚名 6年前 (2018-09-27) 算法 1978人围观抢沙发百度已收录

旅行商问题的描述

试想一下，一个业务员因工作需要必须访问多个城市。他的目标是每个城市只访问一次，并且尽可能地缩短旅行的距离，最终返回到他开始旅行的地点，这就是旅行商问题的主要思想。

在一幅图中，访问每个顶点一次，并最终返回起始顶点，这个访问的轨迹称为哈密顿圈。要解决旅行商问题，需要用图G=（V，E）作为模型，寻找图中最短的哈密顿圈。G是一个完整的、无方向的带权图，其中V代表将要访问的顶点的集合，E为连接这些顶点的边的集合。E中每条边的权值由顶点之间的距离决定。由于G中一个完整的、无方向的图，因此E包含V（V-1）/2条边。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

事实上，旅行商问题是一种特殊的非多项式时间问题，称为NP完全问题。NP完全问题是指那些多项式时间算法未知，倘没有证据证明没有解决的可能性的问题。考虑到这种思想，通常用一种近似算法来解决旅行商问题。

旅行商问题的接口定义

tsp

int tsp (List *vertices,const TspVertex *start, List *tour, int (*match)(const void *key1, const void key2))

返回值：如果计算近似旅行商路线成功，返回0；否则，返回-1。

描述：为存储在vertices中的顶点计算一条近似旅行商的路线。路线的起始点为start指定的顶点。此操作会改变vertices，所以如果有必要，在调用此操作之前需要先备份vertices。

vertices中每个元素都必须是TspVertex类型。用TspVertex结构体的成员data来保存与顶点相关的数据，例如顶点标识符。用其成员x和y来指定顶点的坐标。match函数判断两个顶点是否匹配，它仅用来比较TspVertex结构体的data成员。计算得到的路线存储在tour中，tour是TspVertex结构体列表。tour中保存的顶点会按照路线中顶点的顺序排放。tour中元素指向vertices中实际的顶点，所以只要能够访问tour，函数调用者就必须保证vertices的内存空间有效。如果不再使用tour，那么可以调用list_destroy来销毁tour。

复杂度：O(V²)，其中V是路线中要访问的顶点的个数。

旅行商问题的实现与分析

解决旅行商问题，首先从一个由顶点列表表示的图开始。用这种方式表示的图，其每条边都是隐式的。列表中的每个顶点都是一个TspVertex结构体。此结构体包含4个成员：data用来保存顶点有送的数据；x和y表示顶点的坐标；color为顶点的色值。

tsp操作首先将所有的顶点涂成白色（除起始顶点外，起始顶点会涂黑），且立刻加入线路中。同时，记录起始顶点的坐标值，这样在主循环的首次迭代过程中，就可以计算起始顶点与其他顶点之间的距离。在主循环中，将所有剩余顶点加入路线中。在每次迭代过程中，寻找离最后加入的顶点最近的白色顶点。每次加入一个顶点，就为下次迭代记录它的坐标，同时将其涂成黑色。在循环结束后，再次将起始顶点加入路线中，以形成一条闭合路径。

tsp的时间复杂度是O（V²），其中V是路径中要访问的顶点个数。这是因为，对于主循环中每V-1次迭代，都需要搜索颜色为白色而且需要为其计算距离的顶点。注意O（V²）的复杂度对于计算一条最优路径的复杂度O（V！）来说已经是很大的改进了。

头文件：旅行商问题头文件

/*graphalg.h*/
#ifndef GRAPHALG_H
#define GRAPHALG_H

#include "graph.h"
#include "list.h"
/*定义旅行商问题中结点的数据结构*/
typedef struct TspVertex_
{
    void    *data;
    
    double  x,y;
    
    VertexColor  color;
}TspVertex;

/*函数接口*/
int tsp(List *vertexs, const TspVertex *start, List *tour, int (match*)(const void *key1, const void *key2));

#endif // GRAPHALG_H

示例16-5：解决旅行商问题的实现

/*tsp.c*/
#include <float.h>
#include <math.h>
#include <stdlib.h>

#include "graph.h"
#include "graphalg.h"
#include "list.h"

int tsp(List *vertices, const TspVertex *start, List *tour, int (*match)(const void *key1, const void *key2))
{
    TspVertex  *tsp_vertex,
               *tsp_start,
               *selection;
    ListElmt   *element;
    double     minimum,
               distance,
               x,
               y;
    int        found,
               i;

    /*初始化列表tour(存储计算得到的路线)*/
    list_init(tour,NULL);

    /*初始化图中的所有顶点*/
    found = 0;

    for(element = list_head(vertices); element != NULL; element = list_next(element))
    {
        tsp_vertex = list_data(element);
        if(match(tsp_vertex,start))
        {
            /*将起始顶点加入到路线列表中*/
            if(list_ins_next(tour,list_tail(tour),tsp_vertex) != 0)
            {
                list_destroy(tour);
                return -1;
            }

            /*保存起始顶点以及它的坐标值*/
            tsp_start = tsp_vertex;
            x = tsp_vertex->x;
            y = tsp_vertex->y;

            /*将起始顶点涂成黑色*/
            tsp_vertex->color = black;
            found = 1;
        }
        else
        {
            /*除此之外的其他顶点都涂成白色*/
            tsp_vertex->color = white;
        }
    }
/*如果没有找到起始顶点，程序返回*/
if(!found)
{
    list_destroy(tour);
    return -1;
}

/*使用最近邻点法计算路线*/
while(i < list_size(vertices)-1)
{
    /*从白色顶点中选择离当前顶点最近的顶点*/
    minmum = DBL_MAX;
    
    for(element = list_head(vertices); element != NULL; element = list_next(element))
    {
        tsp_vertex = list_data(element);
        if(tsp_vertex->color == white)
        {
            distance = sqrt(pow(tsp_vertex->x-x,2.0) + pow(tsp_vertex->y-y, 2.0));
            
            if(distance < minimum)
            {
                minimum = distance;
                selection = tsp_vertex;
            }
        }
    }
    /*保存符合要求顶点的坐标*/
    x = selection->x;
    y = selection->y;
    
    /*将被选中的顶点涂成黑色*/
    selection->color = black;
    
    /*将选中顶点插入到路线链表中*/
    if(list_ins_next(tour, list_tail(tour),selection) != 0)
    {
        list_destroy(tour);
        return -1;
    }
    /*准备选取下一个顶点*/
    i++;
}

/*最后再将起始顶点插入到计算路线中，形成闭合路线*/
if(list_ins_next(tour,list_tail(tour),tsp_start) != 0)
{
    list_destroy(tour);
    return -1;
}

return 0;
}