Gerar todas as possibilidades de caminhos

[rs.fran]

Boa noite!

 

Estou com um problema de geração de possibilidades.. Preciso obter todas as possibilidades de caminhos em um grafo lido do arquivo de entrada. Representei esse grafo com uma matriz de adjacência, só que não tenho nenhuma ideia de como vou gerar todas as possibilidades.

Eu sei que:

As primeiras possibilidades são os próprios vértices isolados;

As próximas são os vértices dois a dois ligados por uma aresta;

As demais possibilidades vão crescendo gradativamente até que eu chegue à distância máxima que posso caminhar no grafo (esse valor é fornecido). Sendo que cada aresta tem um peso (a distancia que preciso percorrer para chegar de um vertice ao outro)

um exemplo de possibilidades para um grafo 1----2----3  seria:

1

2

3

12

23

123

321

1232

12321

123212

.

.

.

(isso continuaria até que eu não estourasse a distância máxima)

O problema é que eu não consegui visualizar como esse gerador será feito, já que terei possibilidades de "tamanhos" diferentes, começando com 1 vértice e terminando com o máximo que eu puder sem ultrapassar a distancia que posso caminhar...

podem me dar alguma ideia de como implementar esse "gerador de possibilidades"?

Obrigada!

[Listeiro 037]

Tem como calcular valores de distâncias fazendo multiplicação de matrizes. No caso, ela mesma por ela mesma. Ocorre no caso da n-ésima potência da matriz.

http://pt.wikipedia.org/wiki/Matriz_de_adjac%C3%AAncia

 

Se for isso mesmo que você deseja é só adaptar. Escreve-se:

 

* 'do vertice x até o vértice y não existe caminho de tamanho tal'. 

ou

'do vertice x até o vértice y existe caminho de tamanho tal'. 

 

Agora se for prá apenas descrever os caminhos, melhor usar uma função recursiva e filas/listas prá servir como malha do grafo.

[rs.fran]

Tem como calcular valores de distâncias fazendo multiplicação de matrizes. No caso, ela mesma por ela mesma. Ocorre no caso da n-ésima potência da matriz.

http://pt.wikipedia.org/wiki/Matriz_de_adjac%C3%AAncia

 

Se for isso mesmo que você deseja é só adaptar. Escreve-se:

 

* 'do vertice x até o vértice y não existe caminho de tamanho tal'. 

ou

'do vertice x até o vértice y existe caminho de tamanho tal'. 

 

Agora se for prá apenas descrever os caminhos, melhor usar uma função recursiva e filas/listas prá servir como malha do grafo.

Obrigada pela resposta,

Na verdade, minha matriz de adjacência está criada.. Vamos supor que cada vértice do meu grafo é uma cidade. Eu preciso listar todos os caminhos possíveis, desde os caminhos que só tem uma cidade, por exemplo, caminhos 1, 2, 3 para um grafo de 3 cidades, até os caminhos que contém o máximo de cidades que eu consigo alcançar que não ultrapasse uma certa distância limite que eu posso andar, sendo que cada estrada entre as cidades tem uma certa distancia. Eu sei como fazer para gerar combinações com um número fixo de cidades, mas variando a quantidade de cidades, não consegui.

[rs.fran]

 

Obrigada pela resposta!

Esse algoritmo de dijkstra retorna sempre o menor caminho entre dois vértices, certo? No caso, eu não precisaria do menor caminho, mas sim de todos os caminhos existentes que não ultrapassam a distância.. por exemplo: começando da cidade 1, eu tenho: 1, 12, 123 1232, 12321, e por ai ele iria combinando até que, ao somar o tamanho dos caminhos que vão sendo adicionados, ele ultrapassasse a distância máxima que posso andar..

[Listeiro 037]

Obrigada pela resposta,

Na verdade, minha matriz de adjacência está criada.. Vamos supor que cada vértice do meu grafo é uma cidade. Eu preciso listar todos os caminhos possíveis, desde os caminhos que só tem uma cidade, por exemplo, caminhos 1, 2, 3 para um grafo de 3 cidades, até os caminhos que contém o máximo de cidades que eu consigo alcançar que não ultrapasse uma certa distância limite que eu posso andar, sendo que cada estrada entre as cidades tem uma certa distancia. Eu sei como fazer para gerar combinações com um número fixo de cidades, mas variando a quantidade de cidades, não consegui.

 

Tem como colocar esse trecho que você sabe aqui?

[Plástico Bolha]

Isso, mas você pode usar ele para o seu propósito \@

[rs.fran]

Tem como colocar esse trecho que você sabe aqui?

 

Eu tinha pensado da seguinte maneira: encontre um caminho na matriz de adjacencia (nesse caso, onde tem o "1" na matriz, tem caminho). Ao encontrar um caminho de a para b (a-, procure outro caminho de b para outra cidade, por exemplo c, e salve essa possibilidade a-b-c como um caminho válido.. o problema é que eu não sei fazer isso variando de 1 até o máximo. só fixo, por exemplo, se eu quisesse com 4, faria ele procurar novamente um caminho de c para qualquer outra, por exemplo d, e meu caminho seria a-b-c-d.. fazendo isso para todos os "1" da matriz

[Plástico Bolha]

No código original que eu fiz  . . . Eu resolvi assim, eu criei uma matriz usando malloc . . . E cada linha da matriz guardava 1 caminho diferente . . . Então eu fazia um for do tamanho das linhas do grafo, e testava TUDO COM TUDO e guardava TODOS os resultados dentro da matriz CAMINHO.

 

FOR(I)

    FOR(J)

           CAMINHO[J] = DIKSTRA(G,I,J);

 

 

Depois que você tem todos os resultados dentro da matriz caminho é só você criar algum algoritmo simples para verificar por exemplo o caminho a b c d. Não sei se você conhece o dijkstra, mas vá no you tube, e veja um vídeo do algoritmo rodando graficamente, para ver que ele faz isso que você quer.

[rs.fran]

Isso, mas você pode usar ele para o seu propósito \@

 

Há uma maneira de transformar o dijkstra para que ele gere todos os caminhos existentes? Porque no caso, eu não sei em qual "cidade" ele iria terminar, e o algoritmo recebe duas cidades...

No código original que eu fiz  . . . Eu resolvi assim, eu criei uma matriz usando malloc . . . E cada linha da matriz guardava 1 caminho diferente . . . Então eu fazia um for do tamanho das linhas do grafo, e testava TUDO COM TUDO e guardava TODOS os resultados dentro da matriz CAMINHO.

 

FOR(I)

    FOR(J)

           CAMINHO[J] = DIKSTRA(G,I,J);

vou tentar! obrigada

[Listeiro 037]

http://wiki.icmc.usp.br/images/e/eb/GrafosTAD2.pdf

 

Encontrei esse slide e a folha 12 me chamou a atenção.

Precisaria ter certeza de que funciona com grafos ponderados, isto é, arestas com peso.

Será elevar a matriz a uma dada potência e verificar no elemento certo da matriz se a distância apresentada excede o limite.

[Plástico Bolha]

Sim ele aceita peso . . .

[rs.fran]

Sim ele aceita peso . . .

hahaha vida de computaçao, virar a noite programando.. vou tentar implementar essas soluçoes.

Ps.: Nao estou assassinando o portugues, meu teclado simplesmente decidiu que nao quer pegar mais acentos no forum '0'

http://wiki.icmc.usp.br/images/e/eb/GrafosTAD2.pdf

 

Encontrei esse slide e a folha 12 me chamou a atenção.

Precisaria ter certeza de que funciona com grafos ponderados, isto é, arestas com peso.

Será elevar a matriz a uma dada potência e verificar no elemento certo da matriz se a distância apresentada excede o limite.

Boa! vou colocar os pesos direto na matriz de adjacencia!

[Plástico Bolha]

hahaha vida de computaçao, virar a noite programando.. vou tentar implementar essas soluçoes.

Ps.: Nao estou assassinando o portugues, meu teclado simplesmente decidiu que nao quer pegar mais acentos no forum '0'

Boa! vou colocar os pesos direto na matriz de adjacencia!

 

Ja fiquei 3 noites sem dormir fazendo essas porcaria rsrs, o meu grafo tinha que calcular 1000000 de vértices, os vértices eram aleatórios, criados em um arquivo.txt  . . . PARA CADA MALDITO ALGORITMO, tinha que calcular o tempo individual de cada maldito algoritmo de busca ........... o dijkstra era um desses malditos algoritmos . . . Virei um zumbi programador movido a cafeina. O grafo tinha que ser feito com lista encadeada + Fila + Pilha . . . Bons tempos 

 

 

LoL apagaram o meu post aonde tinha o dijkstra  . . .

[rs.fran]

Ja fiquei 3 noites sem dormir fazendo essas porcaria rsrs, o meu grafo tinha que calcular 1000000 de vértices, os vértices eram aleatórios, criados em um arquivo.txt  . . . PARA CADA MALDITO ALGORITMO, tinha que calcular o tempo individual de cada maldito algoritmo de busca ........... o dijkstra era um desses malditos algoritmos . . . Virei um zumbi programador movido a cafeina. O grafo tinha que ser feito com lista encadeada + Fila + Pilha . . . Bons tempos 

 

 

LoL apagaram o meu post aonde tinha o dijkstra  . . .

nao consegui implementar, alguem tem mais alguma ideia que possa ajudar?

[Listeiro 037]

Coloca aí o que você já fez prá ver o que está errado.

[rs.fran]

void sub(struct Pilha *minhapilha, struct Pilha *copiapilha, int **matrizAdj, int *empilhados, instancia inst, int *distancia_percorrida, int j, int *cont_v){    int a, b, a_anterior, i, vazia = 0, inseriu;// ultimo_emp;    int *possibilidade; // vetor que armazena o caminho válido obtido    int insere_povo; // variável que pega da pilha o povo a ser inserido no vetor possibilidade;    a = j; // fixa a coluna j da função anterior como linha da nova função. A partir de agora, será procurado um caminho de a para outro povoado    //ultimo_emp = j;    b = 0;    // procura um caminho válido de a para b    while (b < inst.n_povos){        //printf("dentro while sub\n");        inseriu = 0;        // verifica que há caminho        if (matrizAdj[a][b] != 0) {            //printf("dentro if sub\n");            // verifica se a distância já percorrida mais a distancia de a para b não vai ultrapassar a distancia máxima            if (*distancia_percorrida + matrizAdj[a][b] <= inst.distancia_max){                // verifica se o povoado b já foi inserido na pilha                if (empilhados[b] == 0){                    empilhados[b] = 1; // marca como inserido na pilha                    //empilhados[ultimo_emp] = 0;                    distancia_percorrida = distancia_percorrida + matrizAdj[a][b]; // atualiza a distância percorrida                    empilhar(minhapilha,;                    empilhar(copiapilha,;                    *cont_v = *cont_v + 1;                    a_anterior = a; // salva o penúltimo vértice (povo) inserido na pilha                    a = b; // atualiza "a" para que a próxima busca seja realizada a partir do último povo empilhado                    b = 0;                    inseriu = 1;                    //ultimo_emp = b;                }            }        }    }    if (inseriu != 1){        a = a_anterior;        b = 0;        possibilidade = (int *) calloc ((*cont_v)+1, sizeof(int));        for (i = *cont_v; i > 0; i--){            while (vazia == 0){                insere_povo = retornatopo(copiapilha);                possibilidade[i] = insere_povo;                desempilhar(copiapilha);                vazia = estavazia(copiapilha);            }        }        desempilhar(minhapilha);        copiapilha = minhapilha;    }}void subgrafo(int **matrizAdj, instancia inst){    int distancia_percorrida, ultimo_emp; // armazena a distância percorrida até o último povoado inserido    int i, j, k;    struct Pilha minhapilha; // pilha para armazenar os povoados inseridos no caminho (representa cada caminho)    struct Pilha copiapilha;    int *empilhados; // vetor que controla se os povoados já estão inseridos no caminho válido a ser passado para a mochila (função "dinamica")    int cont_v = 0; // conta o numero de povoados inseridos no caminho    empilhados = ((int *) calloc ((inst.n_povos)+1, sizeof(int)));    criarpilha (&minhapilha, inst.n_povos);    criarpilha (&copiapilha, inst.n_povos);    // percorre matriz de adjacência para encontrar um caminho válido    for (i = 0; i < inst.n_povos; i++){        for (j = 0; j < inst.n_povos; j++){            distancia_percorrida = 0;            ultimo_emp = 0;            cont_v = 0;            // zera o vetor empilhados            for(k = 0; k < inst.n_povos; k++){                empilhados[k] = 0;            }                // verifica se há caminho entre o povoado i e j            if (matrizAdj[i][j] != 0) {                distancia_percorrida = matrizAdj[i][j];                // verifica se a distância entre i e j é válida                if (distancia_percorrida <= inst.distancia_max){ // empilhar caminhos válidos para i e j                    empilhar(&minhapilha,i);                    empilhar(&copiapilha,i);                    cont_v = cont_v + 1;                    empilhados[i] = 1; // marca o povo i como empilhado (inserido no caminho)                    //ultimo_emp = i;                    empilhar(&minhapilha,j);                    empilhar(&copiapilha,j);                    cont_v = cont_v + 1;                    empilhados[j] = 1;                    //empilhados[ultimo_emp] = 0;                    //ultimo_emp = j;                    /* chamada da função sub, que tenta encontrar o maior caminho a partir dos povoados já empilhados (procurando um novo caminho                    que parte de j) */                    sub(&minhapilha, &copiapilha, matrizAdj,empilhados,inst,&distancia_percorrida,j, &cont_v);                }            }            }    }            }

Fiz isso, vai ser meio difícil de entender porque o código é grande, mas basicamente, ele procura na lista de adjacencia por uma aresta (exemplo, achou na posição i,j) a partir daí, chama a função sub que procura outra aresta partindo de j para outro vértice.. e por ai vai. o problema é que meu algoritmo não considera por exemplo, fazer o caminho 2123, e nem faz caminhos do tipo 124 e 123 (pensei num bactracking para voltar o ultimo inserido, mas não saiu).