BUSCA EM LARGURA - codigo

Prévia do material em texto

FAINOR – FACULDADE INDEPENDETE DO NORDESTE
RELATÓRIO DE INTELIGÊNCIA ARTIFICIAL
BUSCA EM LARGURA
Vitória da Conquista – Bahia
2018.2
FAINOR – FACULDADE INDEPENDENTE DO NORDESTE
Aluno: Bruno Oliveira Caires Souza
 
 
Relatório realizado como avaliação parcial do VIII Semestre do curso de Engenharia da Computação, FAINOR, da disciplina Inteligência Artificial, a pedido do professor Marcos Gomes Prado.
Vitória da conquista- Bahia
2018.2
	1 ALGORITMO E GRAFO
Foi construído o algoritmo em linguagem C++ a fim de atender uma busca em largura que imprima as possíveis rotas de trajetos que ligam cidades daqui da Bahia.
Para fim educativo, o grafo construído foi bem limitado, a ponto de mostrar quando o percurso existe e não existe. Sendo assim, segue abaixo o grafo utilizado para esse algoritmo:
I
Note quenesse grafo, as únicas cidades que estão “excluídas” e só tem rotas entre elas é Camaçari e Salvador.
Logo abaixo, segue o algoritmo:
#include<iostream> //bibliotecas do C++
#include <cstdlib> //bibliotecas do C++
#include<vector> //bibliotecas do C++
using namespace std;
//logo após, foi feito um boll para saber se realmente foi encontrado o caminho ou não.
bool testaObjetivo(int atual,int objetivo){
	if(atual == objetivo)
		return true;	
	else
		return false;
	}
int main()
{
	int inicial,atual,objetivo,filho,op;
	vector<int>listaVisitados, listaVisitar,copia,imprimeCaminho; //declarando os vetores
	int mPai[10]={100,100,100,100,100,100,100,100,100,100}; //grafo pai e seus estados
	system("clear");
 cout<<"-----------------------------";
 cout<<"\nBem vindo!";
 cout<<"\nSoftware de busca em largura de cidades, onde voce irá definir rotas das cidades";
 cout<<"\nComo pode ver abaixo, cada número corresponde a uma cidade, se digitar 0, é Vitoria da conquista";
 cout<<"\nE assim sucessivamente, logo abaixo voce vera todas as opções";
 cout<<"\n----------------------------";
 cout<<"\n\nOpcao 0 - Vitória da Conquista";
 cout<<"\nOpcao 1 - Anage";
 cout<<"\nOpcao 2 - Brumado";
 cout<<"\nOpcao 3 - Itambe";
 cout<<"\nOpcao 4 - Itabuna";
 cout<<"\nOpcao 5 - Itapetinga";
 cout<<"\nOpcao 6 - Eunapolis";
 cout<<"\nOpcao 7 - Ilheus";
 cout<<"\nOpcao 8 - Camacari";
 cout<<"\nOpcao 9 - Salvador";
 cout<<"\n";
	cout<<"\n\nDigite o valor da cidade inicial que voce deseja fazer a rota:\n";
	cin >> inicial;
	cout<< "\n\nDigite o valor da cidade destino que voce deseja:\n";
	cin >> objetivo;
	
	int grafo[10][10];
	//Matriz
	{
		grafo[0][0]=0;grafo[0][1]=1;grafo[0][2]=0;grafo[0][3]=1;grafo[0][4]=0;grafo[0][5]=0;grafo[0][6]=0;grafo[0][7]=0;grafo[0][8]=0;grafo[0][9]=0;
		grafo[1][0]=1;grafo[1][1]=0;grafo[1][2]=1;grafo[1][3]=0;grafo[1][4]=0;grafo[1][5]=0;grafo[1][6]=0;grafo[1][7]=0;grafo[1][8]=0;grafo[1][9]=0;
		grafo[2][0]=0;grafo[2][1]=1;grafo[2][2]=0;grafo[2][3]=0;grafo[2][4]=0;grafo[2][5]=0;grafo[2][6]=0;grafo[2][7]=0;grafo[2][8]=0;grafo[2][9]=0;
		grafo[3][0]=1;grafo[3][1]=0;grafo[3][2]=0;grafo[3][3]=0;grafo[3][4]=1;grafo[3][5]=1;grafo[3][6]=0;grafo[3][7]=0;grafo[3][8]=0;grafo[3][9]=0;
		grafo[4][0]=0;grafo[4][1]=0;grafo[4][2]=0;grafo[4][3]=1;grafo[4][4]=0;grafo[4][5]=0;grafo[4][6]=0;grafo[4][7]=1;grafo[4][8]=0;grafo[4][9]=0;
		grafo[5][0]=0;grafo[5][1]=0;grafo[5][2]=0;grafo[5][3]=1;grafo[5][4]=0;grafo[5][5]=0;grafo[5][6]=0;grafo[5][7]=0;grafo[5][8]=0;grafo[5][9]=0;
		grafo[6][0]=0;grafo[6][1]=0;grafo[6][2]=0;grafo[6][3]=0;grafo[6][4]=0;grafo[6][5]=0;grafo[6][6]=0;grafo[6][7]=1;grafo[6][8]=0;grafo[6][9]=0;
		grafo[7][0]=0;grafo[7][1]=0;grafo[7][2]=0;grafo[7][3]=0;grafo[7][4]=1;grafo[7][5]=0;grafo[7][6]=1;grafo[7][7]=0;grafo[7][8]=0;grafo[7][9]=0;
		grafo[8][0]=0;grafo[8][1]=0;grafo[8][2]=0;grafo[8][3]=0;grafo[8][4]=0;grafo[8][5]=0;grafo[8][6]=0;grafo[8][7]=0;grafo[8][8]=0;grafo[8][9]=1;
		grafo[9][0]=0;grafo[9][1]=0;grafo[9][2]=0;grafo[9][3]=0;grafo[9][4]=0;grafo[9][5]=0;grafo[9][6]=0;grafo[9][7]=0;grafo[9][8]=1;grafo[9][9]=0;
	}
	//////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
	atual = inicial;
	
	while(true){ //BUSCA EM LARGURA
		
		listaVisitados.push_back(atual);
	
		int a = 0;
		while(a<10){ //preenche de lista estados a visitar		
			if(grafo[atual][a] != 0){ //quando acha o num 1 na matriz
				
				listaVisitar.push_back(a);		
			}
			a++;	
		}
	
		//sucessao		
		for(int i = 0;i<listaVisitados.size();i++){ //Para n repetir um estado
			for(int j = 0;j<listaVisitar.size();j++){
				if(listaVisitar.at(j) == listaVisitados.at(i)) 
					listaVisitar.erase(listaVisitar.begin()+j);
			}
		}
		if(listaVisitar.empty()){ // Se acabarem as opçoes
			cout << "\nCaminho nao foi encontrado :(\n";
			break;
		}
		
		copia=listaVisitar; //Salva quem é pai de quem
		for(int i = 0;i <= copia.size();i++){
			if(mPai[copia.back()] == 100)//para nao sobrescrever
				mPai[copia.back()] = atual;
			copia.pop_back();	
		} 
	
		atual = listaVisitar.front(); //sucessao do atual
		listaVisitar.erase(listaVisitar.begin());
		
		if(testaObjetivo(atual,objetivo)){ //Se o obj for encontrado
			cout<<"\nCaminho encontrado! Trajeto abaixo!\n";
			break;
		}
	
		//Fim sucessao	
	}//FIM DA BUSCA
	
	
	cout<< "\nSigla da Cidade Origem -> " << inicial << "\tSigla da Cidade Destino -> " << objetivo <<"\n\n";	
	
 //Imprimir Caminho
 	if(testaObjetivo(atual,objetivo)){
 		
 		cout << "\Caminho :\n\n";
 		filho = objetivo;
 		
		while(true) { 
			if(filho == 100) // 100 representa estados q n tem pai ;-;
				break;
			imprimeCaminho.push_back(filho);
			filho = mPai[filho]; //	pai se torna filho;	
	 }
	 
		while(true){
 //cout<< " " <<imprimeCaminho.back(); 
			if(imprimeCaminho.back()==0)
			cout<<"Vitoria da conquista->";
			else if(imprimeCaminho.back()==1)
			cout<<"Anage->";
			else if(imprimeCaminho.back()==2)
			cout<<"Brumado->";
			else if(imprimeCaminho.back()==3)
			cout<<"Itambe->";
			else if(imprimeCaminho.back()==4)
			cout<<"Itabuna->";
			else if(imprimeCaminho.back()==5)
			cout<<"Itapetinga->";
			else if(imprimeCaminho.back()==6)
			cout<<"Eunapolis->";
			else if(imprimeCaminho.back()==7)
			cout<<"Ilheus->";
			else if(imprimeCaminho.back()==8)
			cout<<"Camaçari->";
			else if(imprimeCaminho.back()==9)
			cout<<"Salvador->";
			imprimeCaminho.pop_back();
			if(imprimeCaminho.empty())
				break;
		}
	 	
	}
 
	cout << "\n\n";
	return 0;	
}
2 EXPLICANDO O ALGORITMO
Para conseguir implementar o algoritmo, foi utilizado o método vector(ou vetor) com finalidade de organizar os estados que foram visitados e os que faltam a visitar. O algoritmo começa com uma classe bool, para testarmos se o caminho foi encontrado ou não.
Logo após, dentro da nossa classe principal, declaramos as variáveis que vamos utilizar mais os vetores necessários para organizarmos a nossa busca, porém com um detalhe, para conseguir implementar esse algoritmo, temos que destacar que é filho de quem no grafo, assim teremos também um outro vetor chamado mPai que determinará isso.
Continuemos o algoritmo, é impresso na tela um simples menu com a finalidade de instruir o usuário que realizará a busca. A forma utilizada para identificar as cidades foi por meio de números, onde no próprio menu detalha qual número pertence cada cidade, por exemplo: 0-Vitoria da Conquista, 1 – Anagé, 2 – Brumado, 3 – Itambé, 4 – Itabuna, 5 – Itapetinga, 6 – Eunápolis, 7 – Ilhéus, 8 – Camaçari e 9 - Salvador, e assim o usuário escolherá a opção desejada e a partir daqui o algoritmo realiza a busca. 
Como foi dito, as cidades foram classificadas por números, pois assim seria maissimples o método da busca. Então, para implementar o grafo foi feito uma matriz 10x10 pois contém nove cidades. Pela figura do grafo, é fácil de ver as ligações que as cidades se encontram, assim a implementação do grafo foi manual, onde grafo[0][1]=1 quer dizer estado 0 com estado 1 tem ligação, então será igual a 1 e grafo[0][9]=0 estado 0 com estado 9 não tem ligação, logo será igual a 0.
Fazemos atual=inicial pois ocorrerá mudanças nos remanejamentos dos vetores a fim de imprimir, e chegamos no primeiro while, onde irá inserir no vetor listaVisitados.push_back(atual), estou inserindo no final do vetor o valor de atual e o próximo while começa a preencher o vetor a visitar passando por toda a matriz do grafo. Logo após, fazemos uma busca no vetor de lugares a visitados, e caso o caminho seja encontrado, imprime em tela. Se acabar as opções e o vetor Visitar estiver vazio, é porque o caminho não foi encontrado.
Caso tente realizar a busca de qualquer cidade para Camaçari ou Salvador terá o caminho não encontrado, pois no grafo, Camaçari só tem caminho com Salvador.
Demonstrando de Camaçari a Salvador.