你的分享就是我们的动力 ---﹥

旅行商问题 tsp

时间:2013-07-05 15:02来源:www.chengxuyuans.com 点击:

代码简介

The travelling salesman problem (TSP) or travelling salesperson problem asks the following question: Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city? It is an NP-hard problem in combinatorial optimization, important in operations research and theoretical computer science.
The problem was first formulated in 1930 and is one of the most intensively studied problems in optimization. It is used as a benchmark for many optimization methods. Even though the problem is computationally difficult, a large number of heuristics and exact methods are known, so that some instances with tens of thousands of cities can be solved.

代码片段

//
//  this simple data structure algorithm
//
//
//  Created by Thomas Huang(°¢è÷?÷) on 12-12-16.
//  Copyright (c) 2012 __MyCompanyName__. All rights reserved.
//
#include <stdio.h>
#include <stdlib.h>
#include<string.h>
#include<time.h>

#include"azm_set.h"
#include"azm_graphalg.h"

#define            STRSIZ                2


typedef struct EdgeData_ {

char               vertex1[STRSIZ],
                   vertex2[STRSIZ];

double             weight;

} EdgeData;



#define            PTHVCT                6
#define            PTHECT               11

static char PthTestV[PTHVCT][STRSIZ] = {

   "a", "b", "c", "d", "e", "f"

};

static EdgeData PthTestE[PTHECT] = {

   {"a", "b", 8.0},
   {"a", "c", 4.0},
   {"b", "c", 6.0},
   {"b", "d", 2.0},
   {"b", "f", 4.0},
   {"c", "e", 4.0},
   {"c", "f", 1.0},
   {"e", "f", 5.0},
   {"f", "b", 2.0},
   {"f", "d", 7.0},
   {"f", "e", 4.0}

};

static void print_graph_pth(const azm_graph_t *graph) {

    azm_set_t  *adjacent;

    azm_path_vertex_t *vertex;

    azm_list_elmt_t *element,
                    *member;

    int i,
        j;



    fprintf(stdout, "Vertices=%d, edges=%d\n", azm_graph_vcount(graph), azm_graph_ecount
    (graph));

    i = 0;
    element = azm_list_head(&azm_graph_adjlists(graph));

    while (i < azm_list_size(&azm_graph_adjlists(graph))) {

    vertex = ((azm_adjlist_t *)azm_list_data(element))->vertex;
    fprintf(stdout, "graph[%03d]=%s: ", i, (char *)vertex->data);

    j = 0;
    adjacent = &((azm_adjlist_t *)azm_list_data(element))->adjacent;
    member = azm_list_head(adjacent);

    while (j < azm_set_size(adjacent)) {

        vertex = azm_list_data(member);
        if (j > 0) fprintf(stdout, ", ");
        fprintf(stdout, "%s(%4.1lf)", (char *)vertex->data, vertex->weight);
        member = azm_list_next(member);
        j++;

        }

    i++;
    fprintf(stdout, "\n");
    element = azm_list_next(element);

    }

    fprintf(stdout, "\n");

    return;

}




static int match_pth(const void *pth1, const void *pth2) {

    return strcmp(((const azm_path_vertex_t *)pth1)->data, ((const azm_path_vertex_t  *)pth2)->
            data);

}


static int route(azm_list_t *paths, azm_path_vertex_t *destination, azm_path_vertex_t **next, int
   (*cmp)(const void *, const void *)) {

    azm_path_vertex_t *temp,
                      *parent;

    azm_list_elmt_t *iter;

    int    found;



    found = 0;

    for (iter = azm_list_head(paths); iter != NULL; iter =
        azm_list_next(iter)) {

        if (cmp(azm_list_data(iter), destination) == 0) {

            temp = azm_list_data(iter);
            parent = ((azm_path_vertex_t *)azm_list_data(iter));
            found = 1;
            break;

        }

    }


    if (!found){

        fprintf(stdout, "No Path : (\n" );
        return -1;
    }



    fprintf(stdout, "the way to %s:\n", (char *)parent->data);
    while (parent != NULL) {

        temp = azm_list_data(iter);
        found = 0;

        for (iter = azm_list_head(paths); iter != NULL; iter =
        azm_list_next(iter)) {


            if (cmp(azm_list_data(iter), parent) == 0) {
                fprintf(stdout, "%s(%4.1lf)", (char *)parent->data, parent->d);

                parent = ((azm_path_vertex_t *)azm_list_data(iter))->parent;
                if(parent != NULL)
                    fprintf(stdout, "<-");

                found = 1;
                break;

        }

    }



    if (!found)
        return -1;

    }

    fprintf(stdout, "\n");

    *next = temp;

    return 0;

}



int main(int argc, char **argv) {

    azm_graph_t graph;

    azm_path_vertex_t  *pth_start,
                       *pth_vertex,
                        pth_vertex1,
                       *pth_vertex2;

    azm_list_t  paths;

    azm_list_elmt_t  *element;

    int i;



    azm_graph_init(&graph, free, match_pth);

    fprintf(stdout, "Computing shortest paths\n");

    for (i = 0; i < PTHVCT; i++) {

        if ((pth_vertex = (azm_path_vertex_t *)malloc(sizeof(azm_path_vertex_t ))) == NULL)
            return 1;

        if (i == 1)
            pth_start = pth_vertex;

            pth_vertex->data = PthTestV[i];

        if (azm_graph_ins_vertex(&graph, pth_vertex) != 0)
            return 1;
//        fprintf(stdout, "\n%d:\n", i);
//        print_graph_pth(&graph);

    }

    for (i = 0; i < PTHECT; i++) {

        if ((pth_vertex2 = (azm_path_vertex_t *)malloc(sizeof(azm_path_vertex_t))) == NULL)
            return 1;

        pth_vertex1.data = PthTestE[i].vertex1;
        pth_vertex2->data = PthTestE[i].vertex2;
        pth_vertex2->weight = PthTestE[i].weight;


        if (azm_graph_ins_edge(&graph, &pth_vertex1, pth_vertex2) != 0)
            return 1;
    }

    print_graph_pth(&graph);

    if (azm_graph_shortest(&graph, pth_start, &paths, match_pth) != 0)
        return 1;

    for (element = azm_list_head(&paths); element != NULL; element =
        azm_list_next(element)) {

        pth_vertex = azm_list_data(element);

        fprintf(stdout, "vertex=%s, parent=%s, d=%.1lf\n", (char *)pth_vertex->
                    data, pth_vertex->parent != NULL ? (char *)pth_vertex->parent->data :
                    "*", pth_vertex->d);

    }


    fprintf(stdout,"\n");
    pth_vertex1.data = "e";
    if (route(&paths, &pth_vertex1, &pth_vertex, match_pth) != 0)
        return 1;
    fprintf(stdout, "\nNext vertex in the route from %s to %s is %s\n", (char *)
    pth_start->data, (char *)pth_vertex1.data, (char *)pth_vertex->data);

    azm_list_destroy(&paths);
    azm_graph_destroy(&graph);

    return 0;

}

转载注明地址:http://www.chengxuyuans.com/code/C++/65456.html