void BT(int n, int *s, int *p, int *w, int b, int penalidade, int *peso_objetos, int *fo, int *inv, int tamanho_maximo_lista_tabu, int BTmax) { int melhor_posicao, valor_bit; struct lista *iniciotabu, *finaltabu, *tabu; int iterBT = 0; // numero corrente de iteracoes da Busca Tabu int MelhorIter = 0; // Iteracao em que ocorreu a melhor solucao int *s_star; int fo_star; int delta; clock_t CPUiniciotabu, CPUfimtabu; s_star = cria_vetor(n); inicializa_vetor(s_star,n); atualiza_melhor_solucao(s, s_star, n); fo_star = *fo; printf("\nIniciando a Busca Tabu com fo = %d\n", *fo); printf("peso dos objetos = %2d inviabilidade = %d \n",*peso_objetos, *inv); // getchar(); iniciotabu = finaltabu = NULL; CPUiniciotabu = CPUfimtabu = clock(); limpa_arquivo("valordefoBT.out"); imprime_fo("valordefoBT.out", (float)(CPUfimtabu - CPUiniciotabu)/CLOCKS_PER_SEC, *fo, iterBT); while (iterBT - MelhorIter < BTmax) { iterBT++; delta = melhor_vizinho(s, n, *peso_objetos, w, p, penalidade, b, *fo, fo_star, &melhor_posicao, &valor_bit, &iniciotabu, &finaltabu); // printf("\ndelta do melhor vizinho = %d melhor posicao = %d valor bit = %d\n", delta, melhor_posicao, valor_bit); // getchar(); tabu = (struct lista *)malloc(sizeof(struct lista)); if (!tabu) { printf("Faltando memoria ...\n"); getchar(); exit(1); } /* vou inserir um registro na lista tabu */ tabu->posicao = melhor_posicao; insere_lista_tabu(tabu, &iniciotabu, &finaltabu); /* vou calcular o tamanho da lista tabu e imprimi-la */ printf("Tamanho da lista tabu = %2d\n", lenght_lista_tabu(&iniciotabu, &finaltabu)); display_lista_tabu(&iniciotabu, &finaltabu); /* vou manter uma lista tabu com tamanho_maximo_lista_tabu elementos, isto e', se a lista tiver mais que essa quantidade de elementos, vou apagar o primeiro registro da lista */ if (lenght_lista_tabu(&iniciotabu, &finaltabu) > tamanho_maximo_lista_tabu){ /* vou apagar o primeiro registro da lista tabu */ apaga_registro_tabu(iniciotabu, &iniciotabu, &finaltabu); printf("novo Tamanho da lista tabu = %2d\n", lenght_lista_tabu(&iniciotabu, &finaltabu)); display_lista_tabu(&iniciotabu, &finaltabu); } s[melhor_posicao] = valor_bit; (*fo) += delta; // printf("fo corrente = %d \n",*fo); // getchar(); (*peso_objetos) = (*peso_objetos) - (w[melhor_posicao])*(!valor_bit) + (w[melhor_posicao])*(valor_bit); CPUfimtabu = clock(); imprime_fo("valordefoBT.out", (float)(CPUfimtabu - CPUiniciotabu)/CLOCKS_PER_SEC, *fo, iterBT); if (*fo > fo_star){ MelhorIter = iterBT; atualiza_melhor_solucao(s, s_star, n); fo_star = *fo; //imprime_solucao(s_star,n); printf("\n****** fo_star = %3d **********\n",fo_star); } printf("\n------ Iteracoes sem melhora = %d\n",iterBT - MelhorIter); } CPUfimtabu = clock(); imprime_fo("valordefoBT.out", (float)(CPUfimtabu - CPUiniciotabu)/CLOCKS_PER_SEC, *fo, iterBT); printf("********** Melhor Solucao Obtida *************** \n"); imprime_solucao(s_star,n); *peso_objetos = calcula_peso_objetos(s_star, n, w); *inv = calcula_inviabilidade(*peso_objetos, b); printf("Saindo da Busca Tabu com fo_star = %d\n",fo_star); printf("peso dos objetos = %2d inviabilidade = %d \n",*peso_objetos, *inv); printf("Numero de solucoes analisadas = %ld \n",iterBT*n); printf("Numero de solucoes existentes = %.0f \n", exp(n*log(2))); printf("******************************************** \n"); getchar(); atualiza_melhor_solucao(s_star, s, n); libera_vetor(s_star); *fo = fo_star; }