# #include &lt;stdio.h&gt

## Testo completo

(1)

/********************************************************

* Algoritmo di Branch-Bound *

* esegui: tsp nome_file nodo_A nodo_B nodo_C * ********************************************************/

#include <stdio.h>

#include <stdlib.h>

#include <limits.h>

#include <iostream>

#include <fstream>

#include <sstream>

#include <map>

#include <vector>

using namespace std;

/*****************************

* Data structure definition *

*****************************/

/* Forward */

struct vert;

struct grph;

struct nd* node; /* Adjecent node */

int weight; /* Arc weight */

/* Node */

typedef struct nd {

int name; /* Node name */

bool inTSJourney; /* If in the journey */

bool visited; /* If already visited */

nd(int nm) { name=nm;

inTSJourney=false;

visited=false;

} } Node;

/* Graph */

typedef struct grph {

(2)

map<int, struct nd*> nodes; /* Nodes */

} Graph;

/****************

* Input values * ****************/

/* The graph and starting point of TSP */

Graph graph;

Node* source;

int journeyLen;

/* Temporary variables about journey */

vector<int> journey;

vector<int> best;

int minimum=INT_MAX;

int cost=0;

/************************************

* Recursive TSP problem resolution *

************************************/

bool TSPRecursive(Node* start, int visited) { bool found=false;

/* Take forward-star of current node */

if(visited==journeyLen-1) { /* Last step */

if(adjlist->node->name==source->name) { /* Closing hamiltonian cycle */

/* Calculating minimum */

if(cost<minimum) { minimum=cost;

best.clear();

for(vector<int>::iterator iter=journey.begin();

iter!=journey.end();

++iter) best.push_back(*iter);

}

return true;

}

/* Scan forward-star */

(3)

} }

/* Depth-first visit of graph */

/* Take a path, then backtrack */

journey.pop_back();

} }

/* Scan forward-star */

}

return found;

}

/**********************

* Source graph input * **********************/

void sourceGraphInput(const char* fileName) { ifstream stream(fileName);

do {

/* Get line */

char str[255];

stream.getline(str,255);

istringstream s(str);

/* Creating node */

int name;

s>>name;

(4)

Node* newNode;

map<int, Node*>::iterator iter;

if((iter=graph.nodes.find(name))==graph.nodes.end()) { newNode=new Node(name);

graph.nodes[name]=newNode;

} else newNode=iter->second;

do { int idx;

int weight;

s>>idx;

s>>weight;

/* Searching adjecent node, or auto-create it */

Node* target;

map<int, Node*>::iterator iter;

if((iter=graph.nodes.find(idx))==graph.nodes.end()) { target=new Node(idx);

graph.nodes[idx]=target;

} else target=iter->second;

} while((s.get()!=EOF)&&(s.unget()));

} while((stream.get()!=EOF)&&(stream.unget()));

stream.close();

}

/********************

* Game starts here * ********************/

int main(int argc, char* argv[]) { if(argc<3) {

printf("\nSintassi: TSP [graph_file] [journey_0 ... journey_n]\n\n\n");

return -1;

}

/* Source graph input */

sourceGraphInput(argv[1]);

/* Creating required journey */

source=graph.nodes[atoi(argv[2])];

for(int count=2; count<argc; ++count)

graph.nodes[atoi(argv[count])]->inTSJourney=true;

(5)

journeyLen=argc-2;

/* Starting algorithm */

source->visited=true;

if(TSPRecursive(source,0)) {

printf("\n\n===================\nSolution:\n");

if(best.size()) printf("%d, ",source->name);

for(vector<int>::iterator iter=best.begin();

iter!=best.end();

++iter) printf("%d, ",*iter);

printf("%d\n",source->name);

printf("Overall cost: %d\n===================\n\n\n",minimum);

}

else printf("\n\n==============\nEmpty solution\n==============\n\n\n");

return 0;

}

Updating...

## Riferimenti

Argomenti correlati :