rs.fran

Boa noite! Estou implementando o algoritmo de Christofides, e um dos passos para implementação é obter o casamento mínimo entre os vértices de grau ímpar para torná-los de grau par. Eu entendi que o casamento mínimo é colocar arestas entre os vértices de grau ímpar de modo que todos passem a ter grau par. Porém, essas arestas tem que ser colocada de uma maneira que a soma dos pesos seja mínima. Pensei em combinar todas as maneiras possíveis de casamento e então pegar a menor, porém, com muitos vértices, isso seria inviável... Vocês podem me ajudar a pensar em alguma estratégia? Obrigada

né (:

Use uma função rand() limitando os aleatórios de 0 a 4

Oi gente, estou desenvolvendo um trabalho da faculdade e preciso ler uma base de dados TSPLIB, para o problema do caixeiro viajante. A base segue o modelo: http://www.dcs.gla.ac.uk/~pat/af2009/tspDemo/a280.tsp Como posso ler esses inteiros ignorando os espaços iniciais? Exemplo, a primeira linha é: " 1 288 149". Eu sei como fazer isso para um número fixo de espaços, com dois espaços, por exemplo, eu poderia fazer " %d", porém a entrada terá espaços variáveis.. sendo que um número de 1 dígito tem 2 espaços na frente, um de 2 dígitos tem 1 espaço, e um de 3 dígitos não tem espaço nenhum. Como faço isso? Obrigada

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).

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

Olá! Estou estudando programação dinâmica e encontrei um algoritmo do problema da mochila, porém não consegui reconhecer se ele é ou não implementado por programação dinâmica, poderiam me ajudar? Caso ele seja pd, poderiam me explicar por que? #include <stdio.h>#include <stdlib.h>#include <string.h> struct { double val, wgt, vol; const char * name;} items[] = { // value in hundreds, volume in thousandths {30, .3, 25, "panacea"}, {18, .2, 15, "ichor"}, {25, 2., 2, "gold"}, {0,0,0,0}}; /* silly setup for silly task */int best_cnt[16] = {0}, cnt[16] = {0};double best_v = 0; void grab_em(int idx, double cap_v, double cap_w, double v){ double val; int t = cap_w / items[idx].wgt; cnt[idx] = cap_v / items[idx].vol; if (cnt[idx] > t) cnt[idx] = t; while (cnt[idx] >= 0) { val = v + cnt[idx] * items[idx].val; if (!items[idx + 1].name) { if (val > best_v) { best_v = val; memcpy(best_cnt, cnt, sizeof(int) * (1 + idx)); } return; } grab_em(idx + 1, cap_v - cnt[idx] * items[idx].vol, cap_w - cnt[idx] * items[idx].wgt, val); cnt[idx]--; }} int main(void){ int i; grab_em(0, 250, 25, 0); printf("value: %g hundreds\n", best_v); for (i = 0; items[i].name; i++) printf("%d %s\n", best_cnt[i], items[i].name); return 0;} Obrigada!

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!

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... vou tentar! obrigada

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

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..

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.

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!

Funcionou! Muito obrigada!

Boa noite, estou com um problema.. parece simples de resolver, mas não estou conseguindo enxergar. Tenho o seguinte código: struct p { int chave; int peso; int habilidade;} p;typedef struct p* povoados;typedef struct i{ int chave; int n_povos; int distancia_max; int peso_nave; int qtd_caminhos; povoados *povoado;} instancia; e uma função que lê os dados de um arquivo de entrada e salva na struct instância.. porém, quando faço isso: int leEntrada (FILE **arq_entrada, instancia inst){ fscanf(*arq_entrada, "%d \n ", &inst.chave); fscanf(*arq_entrada, "%d %d %d %d \n ", &inst.n_povos, &inst.distancia_max, &inst.peso_nave, &inst.qtd_caminhos); inst.povoado = (povoados *) calloc ((inst.n_povos)+1, sizeof(povoados)); if (inst.povoado == NULL) { printf ("\n Erro: Memoria Insuficiente \n"); return (0); } fscanf(*arq_entrada, "%d %d %d \n ", &inst.povoado.chave, &inst.povoado.peso, &inst.povoado.habilidade); //essa é a linha do erro return(0);} obtenho os erros: request for member 'chave’ in something not a structure or union. request for member 'peso’ in something not a structure or union. request for member 'habilidade’ in something not a structure or union. Alguém pode me ajudar? Obrigada!