Number Puzzle master

Problema 8-Puzzle: Análise da solução usando Algoritmos de Busca

O jogo do 8-Puzzle é um jogo de tabuleiro de blocos deslizáveis. Existem diversas maneiras de solucioná-lo, tais como algoritmos de combinação, busca em largura, profundidade, técnicas de busca direcional, entre diversas outras.
Segundo Luger “além do seu apelo intelectual inerente, os jogos de tabuleiro têm certas propriedades que os tornaram objetos de estudo ideal para trabalhos inicias.”

Com jogos de tabuleiro, como o 8-Puzzle, onde existem regras bem definidas podemos gerar um espaço de busca bem definido, porém algumas soluções podem ser custosas para o desempenho de um determinado computador. Dado o problema podemos resolvê-lo com uma busca ...

Busca em Largura

Formalmente, uma busca em largura é um método de busca não-informada (ou desinformada) que expande e examina sistematicamente todos os vértices de um grafo direcionado ou não-direcionado. Em outras palavras, podemos dizer que o algoritmo realiza uma busca exaustiva num grafo passando por todas as arestas e vértices do grafo. Sendo assim, o algoritmo deve garantir que nenhum vértice ou aresta será visitado mais de uma vez e, para isso, utiliza uma estrutura de dados fila para garantir a ordem de chegada dos vértices. Dessa maneira, as visitas aos vértices são realizadas através da ordem de chegada na estrutura fila e um vértice que já foi marcado não pode retornar a esta estrutura.

Busca em Profundidade

O algoritmo de busca em profundidade realiza uma busca não-informada que progride através da expansão do primeiro nó filho da árvore de busca, e se aprofunda cada vez mais, até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não possui filhos. Então a busca retrocede e começa no próximo nó.
A complexidade espacial de um algoritmo de busca em profundidade é muito menor que a de um algoritmo de busca em largura. A complexidade temporal de ambos algoritmos são proporcionais ao número de