Ir para o conteúdo
AnaCal

alteraçao do post anterior -> resolver iteractividade

Mensagens Recomendadas

AnaCal

Tenho o seguinte codigo para fazer uma procura do caminho. Recursivamete ele funciona mas ao tentar coloca lo nao recursivo ele nao me imprime o melhor caminho e nao estou a conseguir ver o erro. Eis o que fiz

#include<stdio.h> 
#include<iostream.h> 


int i, j, chegou = 0; // i e j servem para inicializar as matrizes utilizadas pelo algoritmo. A variavel chegou é a solução para o problema
const int larguraX = 6, alturaY = 6; // linhas e colunas
const int FIM = 3; // informa que a saida foi encontrada, é responsavel pelo valor que recebera a variavel chegou
const int parede = 1; // informa das paredes do labirinto
const int ja_passou = 9; // representa caminhos que o algoritmo ja encontrou, a cada movimento é armazenado o valor 9
const int maior_custo = 5555; // auxiliar para encontrar o custo de menor valor
const int melhor_caminho = 8; // apresenta o melhor caminho
const int inicialX = 4; // coordenadas do
const int inicialY = 1; // ponto inicial
const int finalX = 0; // coordenadas do 
const int finalY = 5; // ponto final

int caminho[larguraX][alturaY]; // guarda toda a informaçao referentes aos caminhos que podem ser percorridos no tabuleiro, copia da matriz. Memoriza o melhor caminho e as casas visitadas
int guarda_caminho[larguraX][alturaY]; // usada para imprimir o melhor caminho - meh
int menor_custo[larguraX][alturaY];  

int F[larguraX][alturaY]; // menor custo estimado para cada movimento do agente
int G[larguraX][alturaY]; // custo do movimento para cada passo executado pelo agente
int H[larguraX][alturaY]; // valor mais baixo estimado da distancia para todas as posiçoes em relacao ao no final


//prototipo da função A*(star) 
void encontrar_caminho(int x, int y);
main() {
        int tabuleiro[larguraX][alturaY] = { { 1, 0, 1, 0, 1, 3},
                                             { 1, 0, 0, 0, 0, 0}, 
                                             { 1, 0, 1, 0, 0, 0}, 
                                             { 1, 0, 1, 0, 1, 1}, 
                                             { 1, 5, 1, 0, 0, 0},
                                             { 1, 1, 1, 1, 1, 1}, 
                                             };
//configurar o caminho com informações do tabuleiro
        for (i = 0; i < larguraX; i++) {
                for (j = 0; j < alturaY; j++) {
                        caminho[i][j] = tabuleiro[i][j];
                        guarda_caminho[i][j] = tabuleiro[i][j];
                }
        }
//configurar o caminho com informações do tabuleiro
        for (i = 0; i < larguraX; i++) {
                for (j = 0; j < alturaY; j++) {
                        menor_custo[larguraX][alturaY] = 555;
                }
        }
//gerar F e G 
        for (i = 0; i < larguraX; i++) {
                for (j = 0; j < alturaY; j++) {
                        F[i][j] = 0;
                        G[i][j] = 0;
                }
        }
//calcular custo de H de cada célula do tabuleiro 
        for (i = 0; i < alturaY; i++) {
                for (j = 0; j < larguraX; j++) {
                        H[i][j] = 6 * (abs(i - finalX) + abs(j - finalY));
                }
        }
// Iniciar o sistema aqui 
        i, j = 0;
        encontrar_caminho(inicialX, inicialY);
        int c = 0;
        printf("\n=============================================================\n");
        printf(" :: O melhor caminho é representado pelo símbolo: \" * \"\n");
        printf("=============================================================\n");
//imprimir o melhor caminho 
        for (i = 0; i < 6; i++) {                                                 // 7
                for (j = 0; j < 6; j++) {
                        if (guarda_caminho[i][j] == 8) {
                                printf(" * ");
                        } else {
                                printf(" %d ", guarda_caminho[i][j]);
                        }
                        c++;
                        if (c == 6) {
                                printf("\n");
                                c = 0;
                        }
                }
        getchar();
        }
        getchar();
        printf("\n=============================================================\n");
        printf(" ::                                                       ::\n");
        printf("=============================================================\n");
}

// funcão para descobrir o caminho 
void encontrar_caminho(int x, int y) {
     
     do {
        printf("\n %d   %d  %d", x, y, chegou);
        system("pause");
        if (guarda_caminho[x][y] == FIM) {
                chegou = 1;
        }
        if ((caminho[x + 1][y] != parede) && (caminho[x + 1][y] != ja_passou) && (chegou != 1)) {
                G[x + 1][y] = G[x][y] + 6;
                F[x + 1][y] = G[x + 1][y] + H[x + 1][y];
                menor_custo[x + 1][y] = F[x + 1][y];
        } else {
                menor_custo[x + 1][y] = maior_custo;
        }
        if ((caminho[x - 1][y] != parede) && (caminho[x - 1][y] != ja_passou) && chegou != 1) {
                G[x - 1][y] = G[x][y] + 6;
                F[x - 1][y] = G[x - 1][y] + H[x - 1][y];
                menor_custo[x - 1][y] = F[x - 1][y];
        } else {
                menor_custo[x - 1][y] = maior_custo;
        }
        if ((caminho[x][y + 1] != parede) && (caminho[x][y + 1] != ja_passou) && chegou != 1) {
                G[x][y + 1] = G[x][y + 1] + 6;
                F[x][y + 1] = G[x][y + 1] + H[x][y + 1];
                menor_custo[x][y + 1] = F[x][y + 1];
        } else {
                menor_custo[x][y + 1] = maior_custo;
        }
        if ((caminho[x][y - 1] != parede) && (caminho[x][y - 1] != ja_passou) && chegou != 1) {
                G[x][y - 1] = G[x][y - 1] + 6;
                F[x][y - 1] = G[x][y - 1] + H[x][y - 1];
                menor_custo[x][y - 1] = F[x][y - 1];
        } else {
                menor_custo[x][y - 1] = maior_custo;
        }
        
        /**/
        /* 1 */        
		while( (caminho[x + 1][y] != ja_passou && caminho[x + 1][y] != parede && chegou != 1) || 
                 (menor_custo[x + 1][y] < menor_custo[x - 1][y]) || 
                 (menor_custo[x + 1][y] < menor_custo[x][y + 1]) ||
                 (menor_custo[x + 1][y] < menor_custo[x][y - 1])){

		x = x +1;

			if ((caminho[x + 1][y] != parede) && (caminho[x + 1][y] != ja_passou) && (chegou != 1)) {
				G[x + 1][y] = G[x][y] + 6;
				F[x + 1][y] = G[x + 1][y] + H[x + 1][y];
				menor_custo[x + 1][y] = F[x + 1][y];
			} else {
					menor_custo[x + 1][y] = maior_custo;
			}
			if ((caminho[x - 1][y] != parede) && (caminho[x - 1][y] != ja_passou) && chegou != 1) {
					G[x - 1][y] = G[x][y] + 6;
					F[x - 1][y] = G[x - 1][y] + H[x - 1][y];
					menor_custo[x - 1][y] = F[x - 1][y];
			} else {
					menor_custo[x - 1][y] = maior_custo;
			}
			if ((caminho[x][y + 1] != parede) && (caminho[x][y + 1] != ja_passou) && chegou != 1) {
					G[x][y + 1] = G[x][y + 1] + 6;
					F[x][y + 1] = G[x][y + 1] + H[x][y + 1];
					menor_custo[x][y + 1] = F[x][y + 1];
			} else {
					menor_custo[x][y + 1] = maior_custo;
			}
			if ((caminho[x][y - 1] != parede) && (caminho[x][y - 1] != ja_passou) && chegou != 1) {
					G[x][y - 1] = G[x][y - 1] + 6;
					F[x][y - 1] = G[x][y - 1] + H[x][y - 1];
					menor_custo[x][y - 1] = F[x][y - 1];
			} else {
					menor_custo[x][y - 1] = maior_custo;
			}

			caminho[x + 1][y] = ja_passou;

            }


        /**/    
            
        /* 2 */   

		while((caminho[x - 1][y] != ja_passou && caminho[x - 1][y] != parede && chegou != 1) || 
                 (menor_custo[x - 1][y] < menor_custo[x][y + 1]) || 
                 (menor_custo[x - 1][y] < menor_custo[x][y - 1])){
            
            x = x -1;
            
			if ((caminho[x + 1][y] != parede) && (caminho[x + 1][y] != ja_passou) && (chegou != 1)) {
				G[x + 1][y] = G[x][y] + 6;
				F[x + 1][y] = G[x + 1][y] + H[x + 1][y];
				menor_custo[x + 1][y] = F[x + 1][y];
			} else {
					menor_custo[x + 1][y] = maior_custo;
			}
			if ((caminho[x - 1][y] != parede) && (caminho[x - 1][y] != ja_passou) && chegou != 1) {
					G[x - 1][y] = G[x][y] + 6;
					F[x - 1][y] = G[x - 1][y] + H[x - 1][y];
					menor_custo[x - 1][y] = F[x - 1][y];
			} else {
					menor_custo[x - 1][y] = maior_custo;
			}
			if ((caminho[x][y + 1] != parede) && (caminho[x][y + 1] != ja_passou) && chegou != 1) {
					G[x][y + 1] = G[x][y + 1] + 6;
					F[x][y + 1] = G[x][y + 1] + H[x][y + 1];
					menor_custo[x][y + 1] = F[x][y + 1];
			} else {
					menor_custo[x][y + 1] = maior_custo;
			}
			if ((caminho[x][y - 1] != parede) && (caminho[x][y - 1] != ja_passou) && chegou != 1) {
					G[x][y - 1] = G[x][y - 1] + 6;
					F[x][y - 1] = G[x][y - 1] + H[x][y - 1];
					menor_custo[x][y - 1] = F[x][y - 1];
			} else {
					menor_custo[x][y - 1] = maior_custo;
			}

			caminho[x - 1][y] = ja_passou;
            
		} 


        /**/ 
            
       /* 3 */      
   
		while ((caminho[x][y + 1] != ja_passou && caminho[x][y + 1] != parede && chegou != 1) ||
                (menor_custo[x][y + 1] < menor_custo[x][y - 1])){

		    y = y + 1;

			if ((caminho[x + 1][y] != parede) && (caminho[x + 1][y] != ja_passou) && (chegou != 1)) {
				G[x + 1][y] = G[x][y] + 6;
				F[x + 1][y] = G[x + 1][y] + H[x + 1][y];
				menor_custo[x + 1][y] = F[x + 1][y];
			} else {
					menor_custo[x + 1][y] = maior_custo;
			}
			if ((caminho[x - 1][y] != parede) && (caminho[x - 1][y] != ja_passou) && chegou != 1) {
					G[x - 1][y] = G[x][y] + 6;
					F[x - 1][y] = G[x - 1][y] + H[x - 1][y];
					menor_custo[x - 1][y] = F[x - 1][y];
			} else {
					menor_custo[x - 1][y] = maior_custo;
			}
			if ((caminho[x][y + 1] != parede) && (caminho[x][y + 1] != ja_passou) && chegou != 1) {
					G[x][y + 1] = G[x][y + 1] + 6;
					F[x][y + 1] = G[x][y + 1] + H[x][y + 1];
					menor_custo[x][y + 1] = F[x][y + 1];
			} else {
					menor_custo[x][y + 1] = maior_custo;
			}
			if ((caminho[x][y - 1] != parede) && (caminho[x][y - 1] != ja_passou) && chegou != 1) {
					G[x][y - 1] = G[x][y - 1] + 6;
					F[x][y - 1] = G[x][y - 1] + H[x][y - 1];
					menor_custo[x][y - 1] = F[x][y - 1];
			} else {
					menor_custo[x][y - 1] = maior_custo;
			}

			caminho[x][y + 1] = ja_passou;
			               
		}
        
                      
       /**/   

		while ((caminho[x][y - 1] != ja_passou && caminho[x][y - 1] != parede && chegou != 1)){
              
              y = y - 1; 	
              
			if ((caminho[x + 1][y] != parede) && (caminho[x + 1][y] != ja_passou) && (chegou != 1)) {
				G[x + 1][y] = G[x][y] + 6;
				F[x + 1][y] = G[x + 1][y] + H[x + 1][y];
				menor_custo[x + 1][y] = F[x + 1][y];
			} else {
					menor_custo[x + 1][y] = maior_custo;
			}
			if ((caminho[x - 1][y] != parede) && (caminho[x - 1][y] != ja_passou) && chegou != 1) {
					G[x - 1][y] = G[x][y] + 6;
					F[x - 1][y] = G[x - 1][y] + H[x - 1][y];
					menor_custo[x - 1][y] = F[x - 1][y];
			} else {
					menor_custo[x - 1][y] = maior_custo;
			}
			if ((caminho[x][y + 1] != parede) && (caminho[x][y + 1] != ja_passou) && chegou != 1) {
					G[x][y + 1] = G[x][y + 1] + 6;
					F[x][y + 1] = G[x][y + 1] + H[x][y + 1];
					menor_custo[x][y + 1] = F[x][y + 1];
			} else {
					menor_custo[x][y + 1] = maior_custo;
			}
			if ((caminho[x][y - 1] != parede) && (caminho[x][y - 1] != ja_passou) && chegou != 1) {
					G[x][y - 1] = G[x][y - 1] + 6;
					F[x][y - 1] = G[x][y - 1] + H[x][y - 1];
					menor_custo[x][y - 1] = F[x][y - 1];
			} else {
					menor_custo[x][y - 1] = maior_custo;
			}

			caminho[x][y - 1] = ja_passou; 	   
              
		}
}
        /**/
        while (chegou != 1);

        guarda_caminho[x][y] = melhor_caminho;

}


Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites
KTachyon

Tu não transformas uma solução recursiva numa solução iterativa simplesmente substituindo as chamadas recursivas por cópias da função recursiva... Pelo menos é isso que me parece que estás a fazer. Por isso é normal que a tua solução recursiva não funcione.

Uma solução iterativa:

Defines precedências: Primeiro defines a ordem das direcções que o algoritmo vai tomar, por exemplo, N, E, S, W.

A partir da posição inicial, se houver caminho para N, vai, senão, se houver caminho para E, vai, senão... excepto se a direcção anterior for a oposta da que queremos tomar agora.

Marcas o terreno já percorrido, mas registas também as direcções que tomas a cada posição. Quando chegas a um ponto em que só podes voltar para trás, voltas, mas tiras também o registo dessa direcção.

No final, com o registo de todas as direcções, sabes exactamente o caminho percorrido.


“There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.”

-- Tony Hoare

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.