Algoritmo per problema TST in C??

[giack83]

Salve a tutti,

devo implementare il problema del commesso viaggiatore in C; in poche parole date 1000 cordinate di citta, devo trovare il cammini (percorso) piu breve per passarle tutte.
Han detto di utilizzare l'algoritmo 2 OPT.
Cercando in google non ho trovato informazioni su esso, ci sarebbe qualcuno che perpiacere mi potrebbe dire come funziona, o dare il pseucodice? almeno da averne una idea su come implementarlo.

Grazie mille.

[pbg4]

Io userei uno SPath usando un approccio Dijkstra.
Ti metto il codice, vedi se puoi prendere spunto per fare quello che ti serve. Ciao


#include <stdio.h>

#include <stdlib.h>

#define TRUE 1

#define FALSE 0



typedef int bool;



/* grafo non etichettato */



#include "grafo.h" /* implementazione mediante liste di adiacenza */

typedef int itemType; /* code di interi */

#include "queue.h"





define N 25 /* N: numero dei nodi del grafo */



int dist[N]; /* array delle distanze */

int ST[N]; /* albero dei cammini */





void ShortestPaths(TipoGrafo g, int NumNodi, int nodo_iniz, void visita(int))

{

int i, j;

queue nodi_da_visitare;

bool visitati[NumNodi];





/* inizializzazione */

for (i = 0; i < NumNodi; i++) {visitati[i] = 0; dist[i]=0; ST[i]=i;}





nodi_da_visitare=initQueue(NumNodi*NumNodi);

enqueue(nodi_da_visitare, nodo_iniz);



/* cicla finche' ci sono nodi da visitare */

while (!emptyQueue(nodi_da_visitare)) {

/* prendi il prossimo nodo i da visitare */

i=dequeue(nodi_da_visitare);



/* analizza il nodo i e lo pone tra i nodi visti */

if (!visitati[i]) {



struct edge *ptr; /* implementazione esplicita */



visita(i);

visitati[i] = 1;



/* aggiunge i successori non visitati del nodo i ai nodi da visitare */

ptr=g[i];

while (ptr!=NULL){

if (!visitati[ptr->v]){

enqueue(nodi_da_visitare, ptr->v);

ST[ptr->v]=i;

dist[ptr->v]=dist[i]+1;

}

ptr=ptr->next;

} /* end-while */

} /* end-if */

} /* end-while */

} /* VisitaInAmpiezza-ST */







void StampaPath(int s, int t) {

if (s==t) printf("%d ", s);

else if (ST[t]==t) printf("Nessun cammino tra %d e %d", s,t);

else {

StampaPath(s,ST[t]);

printf("%d ", t);

}

}







/******* grafi etichettati *************/









typedef char *TipoEticNodo;

typedef unsigned float TipoEticArco;





struct arcoEtic {

int v;

TipoEticArco etic;

struct arcoEtic *next;

};





struct nodoEtic {

TipoEticNodo etic;

struct arcoEtic *next;

};



typedef struct nodoEtic *TipoGrafoEtic;







#include "pqueue.h" /* itemType gia' definito come int */



/* def. funzione di confronto */

int DistCmp(int i, int j){

/* distanze minori dalla sorgente hanno priorit‡ maggiore */

return (dist[i]<dist[j])? 1: ((dist[i]==dist[j])? 0: -1);

}







void RipristinaUp(pqueue pq, int v, int cmp(itemType, itemType)){

/* v e' il vertice. E' aumentata la priorita' */



int temp, k;

k=pq->top[pq->cnt-1];

while (pq->top[k]!=v) k--;

fixUp(pq, k, cmp);

}




void Dijkstra_like(TipoGrafoEtic g, int NumNodi, int nodo_iniz) {

/* shortest paths: approccio Dijkstra */



int i, j;

pqueue pq; /* coda di priorit‡ sugli interi */

bool visitati[NumNodi];



/* inizializzazione */

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

visitati[i] = FALSE;

ST[i]=i;

dist[i]=0;

}

pq = initPQ(NumNodi*NumNodi); /* impl. heap */





insertPQ(pq, nodo_iniz, DistCmp);

while (!emptyPQ(pq)) {

i=delMax(pq, DistCmp); /* il vertice i e' quello di priorita' max */



if (!visitati[i]) {

struct arcoEtic *ptr=g[i].next;

visitati[i]=TRUE;



while (ptr!=NULL){

if (!visitati[ptr->v] && dist[ptr->v]==0){ /* adiacente non in pq */

ST[ptr->v]=i;

dist[ptr->v]=dist[i]+ptr->etic;

insertPQ(pq,ptr->v,DistCmp);

} else if (!visitati[ptr->v] && dist[ptr->v]>dist[i]+ptr->etic){

ST[ptr->v]=i;

dist[ptr->v]= dist[i]+ptr->etic;

RipristinaUp(pq,ptr->v, DistCmp);

}

ptr=ptr->next;

} /* end-while */

} /* end-if */

} /* end-while */

}

[-Ivan-]

Originariamente inviato da giack83

Salve a tutti,

devo implementare il problema del commesso viaggiatore in C; in poche parole date 1000 cordinate di citta, devo trovare il cammini (percorso) piu breve per passarle tutte.
Han detto di utilizzare l'algoritmo 2 OPT.
Cercando in google non ho trovato informazioni su esso, ci sarebbe qualcuno che perpiacere mi potrebbe dire come funziona, o dare il pseucodice? almeno da averne una idea su come implementarlo.

Grazie mille.

Non farai mica scienze dell'informazione a cesena?
Anche io devo farlo e sono messo un po' male per ora però ci sto lavorando su.

[pbg4]

No, sono laureato in informatica! In bocca al lupo per l'esame...
pbg4

[giack83]

Grazie per le risposte, si faccio scienze dell'informazione....

cmq devo per forza utilizzare l'algoritmo 2-OPT, qualcosa su esso avete?
anche un pseudocodice va bene, almeno da avere uno spunto.....