3

Buenas trato de hacer el siguiente problema.

Aqui esta mi solución:

#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
#define MAX 10005
#define Node pair< int , int >
#define INF 1<<30

struct cmp {
    bool operator() ( const Node &a , const Node &b ) {
        return a.second > b.second;
    }
};

vector< Node > ady[ MAX ]; vector<int> distancia[ MAX ];
bool visitado[ MAX ];
priority_queue< Node , vector<Node> , cmp > Q;
int V;

void init(){
    for( int i = 0 ; i <= V ; ++i ){
        for (int j = 0; j <= V; ++j){
            distancia[i].push_back(INF);
        }
        visitado[ i ] = false;
    }
}

void relajacion( int actual , int adyacente , int peso ,int inicial){
    if( distancia[ inicial ][actual] + peso < distancia[ inicial][adyacente ] ){
        distancia[ inicial][adyacente ] = distancia[ inicial ][actual] + peso;
        Q.push( Node( adyacente , distancia[inicial][ adyacente ] ) );
    }
}

void dijkstra( int inicial ){
    init();
    Q.push( Node( inicial , 0 ) );
    distancia[ inicial ][inicial]=0;
    int actual , adyacente , peso;

    while( !Q.empty() ){
        actual = Q.top().first;
        Q.pop();
        if( visitado[ actual ] ) continue;
        visitado[ actual ] = true;

        for( int i = 0 ; i < ady[ actual ].size() ; ++i ){
            adyacente = ady[ actual ][ i ].first;
            peso = ady[ actual ][ i ].second;
            if( !visitado[ adyacente ] ){
                relajacion( actual , adyacente , peso ,inicial);
            }
        }
    }
}

int main(){
    int origen, destino , peso , inicial;
    int f;

    while(cin>>f>>V){
        vector <int> fire(f);
        for(int i=0;i<f;i++){
            scanf("%d",&fire[i]);

        }

        for (int i = 0; i < V; ++i){
            scanf("%d %d %d" , &origen , &destino , &peso );
            ady[ origen ].push_back( Node( destino , peso ) );
            ady[ destino ].push_back( Node( origen, peso ) );
        }

        for (int i = 1; i <= V; ++i){
            dijkstra(i);
        }

        int consulta=0;
        int cont2=INF;

        for (int i = 1; i <= V; ++i){
            int cont=0;
            int nuevo=INF;
            fire.push_back(i);

            for (int k = 1; k <= V; ++k){
                nuevo=INF;
                vector<int>::iterator it=find(fire.begin(),fire.end(),k);
                if(it!=fire.end())continue;

                for (int j = 0; j < fire.size(); ++j){
                    if(k!=fire[j]){
                        if(nuevo>distancia[k][fire[j]]){
                            nuevo=distancia[k][fire[j]];
                        }
                    }
                }

                if(nuevo==INF){
                    nuevo=0;
                }

                cont+=nuevo;
            }

            if(cont2>cont){
                cont2=cont;
                consulta=i;
            }

            fire.pop_back();
        }

        printf("%d",consulta);
        return 0;
    }
}

La cual es ineficiente por el tema de la complejidad O(f2*i) , y la memoria que ocupa , sin embargo , creo que no esta del todo mal , sino en la ultima parte , si pudieran darme una ayuda , ojo se que la solución esta en alguna web , solo quiero una pista,que llevo un buen tiempo en este problema,u otro enfoque , pues creo que usando algun algoritmo voraz podría salir.

3
  • 1
    Este problema segun entiendo vendria a ser el muy estudiado "agente viajero" , que hasta el momento no tiene una solucion total. El agoritmo mas comun es dijkstra como bien lo pones. te recomiendo leer mas sobre el tema, en ingles puedes encontrar informacion muy detallada buscando Travel salesman problem, (TSP).
    – Cristyan
    el 15 jun. 2016 a las 19:23
  • Bueno si , pense en dijkstra para hallar los caminos , luego hice fuerza bruta , pero se iba a 25*10^6 , tomando en cuenta que para los jurados 1x 10^6 es un segundo.
    – Kevin AB
    el 15 jun. 2016 a las 19:26
  • Cuál es tu pregunta? Edito para decir que el link al problema ya no funciona y la pregunta ahora tiene mucha menos utilidad...
    – Alfabravo
    el 19 abr. 2018 a las 18:05

1 respuesta 1

0

El problema que quieren resolver NO es TSP (que en español suele llamarse el problema del viajante de comercio, no del agente viajero, no se qué van a encontrar si googlean el agente viajero). No se a qué le llaman solución total, imagino que quieren decir solución polinomial, y sí, efectivamente TSP no tiene soluciones polinomiales conocidas pero NO SE SABE si tiene o no soluciones polinomiales porque no se sabe si P (el conjunto de problemas con soluciones polinomiales) es o no igual a NP (otro conjunto de problemas, donde está por ejemplo TSP).

Dicho esto, Dijkstra es un algoritmo que resuelve el problema de camino mínimo, un problema que SÍ se sabe que sale en tiempo polinomial.

Lo de 10^6 es mentira, en un segundo entran aproximadamente 10^8 operaciones, pero no se mide en operaciones, se mide en tiempo, es lo que tarda tu programa en ejecutar, correlo en tu computadora con casos grandes y vas a poder ver vos cuánto tarda.

El problema lo que pide formalmente es dado un grafo ponderado no dirigido (la ciudad) y algunos vértices distinguidos (los de las estaciones) encontrar el menor vértice (en índice) tal que agregar a ese vértice una estación minimiza la distancia máxima entre u y v para todo u vértice del grafo y v vértice con estación.

Este ES un problema de camino mínimo y sale por ejemplo con el algoritmo de Dijkstra. También sale con el algoritmo de Floyd-Warshall que es muchísimo más fácil de implementar.

Si alguna de estas palabras (grafo, algoritmo, computadora, vértice, índice, distancia, Dijkstra, Floyd-Warshall, etc) no se entendió, creo que están todas en Wikipedia.

3
  • 3
    Hola Guest. Esta publicación se ntiende más como un comentario muy extenso más que una respuesta. En este sitio, a diferencia de un foro, se utiliza la sección de respuestas para brindar una respuesta al problema expuesto por el autor de la pregunta. Te sugiero que edites esta publicación para que refleje una pregunta. Si lo único que quieres es colocar comentarios para los lectores, lo puedes solicitar a un moderador reportando tu propia respuesta e indicando que quieres publicarlo como comentario. Espero tu respuesta al respecto.
    – user227
    el 9 sep. 2016 a las 16:46
  • Estimado Luiggi, si leés laparte donde dice "Este ES un problemade camino mínimo..." ahí doy una respuesta a la pregunta, y hasta le recomiendo usar Floyd-Warshall por ser más sencillo de implementar (y después de todo si Dijkstra estuviese bien implementado, pero sin cola de prioridad o alguna estructura de consulta y eliminación de mínimo y actualización de la misma en orden logarítmico la complejidad de N Dijkstras es N^3 al igual que la de Floyd) por lo que considero que estoy dando información valiosa para responder la pregunta, si te parece que no es así, por favor, hacemelo saber.
    – guest
    el 11 sep. 2016 a las 1:07
  • Comprendo tu punto, pero ese texto se puede considerar un comentario, no una respuesta. Te diría que ahondes más en ese tema. Cabe resaltar que el OP ha brindado el código de su implementación a este problema. Si decirle que debe implementar algo totalmente nuevo es la solución, por lo menos brindarle una base sobre una implementación. Dices "si Dijkstra estuviese bien implementado", entonces te pediría que brindes los detalles para que el código refleje que el algoritmo esté bien implementado (no te pido que lo resuelvas, solo que brindes más información al respecto).
    – user227
    el 11 sep. 2016 a las 1:22

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.