💻 🤖 Esta atividade apresenta os tipos de Busca Cega e Local, aplicados a um determinado problema
Trabalho desenvolvido durante a disciplina de inteligência artificial
O objetivo deste problema é fazer com que o algoritmo posicione oito rainhas em um tabuleiro de xadrez, sem que nenhuma delas ataque as outras. A imagem abaixo mostra os possiveis ataques de uma rainha.
Partindo desta diretrizes os algoritmos devem ter à seguinte análise, à medida que a busca vai progredindo de acordo com a coluna em que ele esta, o algoritmo deverá verificar as possibilidades de se colocar uma rainha na coluna posterior. E estas possibilidades sao os filhos do no em que ocorre a análise, que é representado na figura abaixo
Baseia-se em tabuleiro 3x3, que contém nove peças numeradas de 0 a 8, sendo que a peça vizinha ao quadrado vazio ou zerado, pode deslizar para esta posição. O objetivo deste problema é atingir um estado especificado, como é mostrado na figura abaixo.
A ideia para solucionar essa questão, é de acordo com a movimentação da peça zerada. è ideal que o algoritmo selecionado saiba identificar os possíveis moviemntos de uma posição, e está mobilidae resultará nos filhos do nó, em que ocorre tal verificação, como é mostrado na figura abaixo. Os locais com o plano de fundo cinza representam as posições que o bloco zerado ainda pode acessar.
Os algoritmos que aplicados ao problema, solucionaram de acordo com as deretrizes.
1. Busca em profundidade - Expande, sempre o nó mais profundo da borda. Quando a profundidade de um ramo chegar ao seu limite, o algoritmo migra para outro ramo. A inlustração abaixo, mostra essa busca aplicado ao problema das 8 rainhas.
2. Busca em profundidade com lista de visitados - É uma varição da profundidade normal, em que o algoritmo verifica se o nó já foi expandido, evitando os laços infinitos.
3. Busca em profundidade limitada - É especificado até que nível deverá ser aprofundada e após isto, o algoritmo verifica os outros ramos da árvore até deixar a borda vazia ou achar uma solução.
4. Busca com aprofundamento interativo - Utiliza a profundidade limitada de maneira gradativa ate chegar no objetivo. É aplicada para casos de problema de árvores com profundidade infinita, porem ela não é completa.
5. Busca em largura - E uma solucão em que após o nó raiz ser expandido, os seus nos sucessores irão ser expandidos também e depois os herdeiros destes nós, e assim por diante. A figura seguinte, mostra essa busca aplicado ao problema do puzzle.
6. Busca em custo uniforme - Os nos são expandidos de acordo com a ordem do custo, de caminho armazenados dentro dos nos.
1. Hill Climbing - É um laço repetitivo que se move de forma constante no sentido do valor factível, ou seja, a medida que as interações ocorrem o resultado tende a ir para o tabuleiro em que os ataques entre as rainhas seja zero. Na figura abaixo, mostra como se dá a resolução do algoritmo aplicado ao problema das oito rainhas. Os números dispostos no tabuleiro representam os ataques de forma direta e indireta de acordo com as suas posicões e os com plano de fundo cinza, são as melhores posições.
2. Simulated Annealing - Ele evita os mínimos locais, criados no Hill Climbing, porém ele não escolhe o melhor movimento e sim um aleatório, caso a escolha melhorar a situação, ele aceita, mas caso contrário ele seleciona outra opção e assim sucessivamente.
3. Algoritmos Genéticos - Tem como base um conjunto estado, gerados aleatoriamente, chamado de população, que são representados como possíveis disposições das rainhas em um tabuleiro. E a figura abaixo dita as etapas partindo dessa comunidade.
Simulated Annealing e Genéticos, podem apresentar alguns erros, pois estão incompletos
Sinta-se a vontade de registrar um novo problema, com um respectivo título e descrição no repositório do TrabalhoIA. Se encontrar a solução, avaliarei seu Pull Request.
Criado por Josué Batista Mota ,
esse projeto está sobre MIT license 📃.
Coloque uma ⭐️ caso esse proejto tenha lhe ajudado