#include <stdio.h&gt

Download (0)

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 adj;

struct vert;

struct grph;

/* Adjecent list */

typedef struct adj {

struct nd* node; /* Adjecent node */

int weight; /* Arc weight */

} AdjNode;

/* Node */

typedef struct nd {

int name; /* Node name */

vector<struct adj> adjlist; /* Adjecent list */

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 */

vector<AdjNode>::iterator adjlist;

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

adjlist=start->adjlist.begin();

while(adjlist!=start->adjlist.end()) {

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

cost+=adjlist->weight;

/* Calculating minimum */

if(cost<minimum) { minimum=cost;

best.clear();

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

iter!=journey.end();

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

}

cost-=adjlist->weight;

return true;

}

/* Scan forward-star */

(3)

++adjlist;

} }

/* Depth-first visit of graph */

adjlist=start->adjlist.begin();

while(adjlist!=start->adjlist.end()) { if(!adjlist->node->visited) { /* Searching tree pruning */

if(cost+adjlist->weight<minimum) { journey.push_back(adjlist->node->name);

/* Take a path, then backtrack */

if(adjlist->node->inTSJourney) ++visited;

cost+=adjlist->weight;

adjlist->node->visited=true;

found|=TSPRecursive(adjlist->node,visited);

adjlist->node->visited=false;

cost-=adjlist->weight;

if(adjlist->node->inTSJourney) --visited;

journey.pop_back();

} }

/* Scan forward-star */

++adjlist;

}

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;

/* Filling adjecent list */

do { int idx;

int weight;

s>>idx;

s>>weight;

newNode->adjlist.push_back(AdjNode());

AdjNode* adjNode=&newNode->adjlist.back();

/* 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;

adjNode->node=target;

adjNode->weight=weight;

} 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;

}

figura

Updating...

Riferimenti

Argomenti correlati :