Implementação

Implemente as estratégias de busca:

• iterativa em profundidade,
• A*
• gulosa com heurística

Aplique estas estratégias ao problema do jogo dos 15 descrito na seção 1. No caso da implementação das estratégias A* e gulosa, utilize duas heurísticas: (a) somatório do número de peças fora do lugar e (b) manhattan distance (somatório das distâncias de cada peça ao seu lugar na configuração final).

Dadas as configurações inicial e final (que são argumentos de entrada para o programa), deve imprimir os operadores utilizados no caminho que leva à solução, número de passos, tempo de execução e quantidade de memória utilizada (contabilizada como número máximo de nós armazenados simultaneamente em memória durante a execução).

Compare a sua implementação com os resultados produzidos pelos seguintes métodos de procura:

• busca em profundidade (com verificação de ciclos em cada caminho!)
• busca em largura

A implementação pode ser em qualquer linguagem.

Para cada estratégia, analise:

• tempo para chegar a uma solução,
• quantidade de espaço gasto (número de nós gerados e armazenados),
• completude (o algoritmo consegue encontrar uma solução?) e
• otimalidade (Qual é a profundidade da solução encontrada? A solução encontrada corresponde ao menor número de passos para chegar da configuração inicial à final ou com menor custo utilizando pouco tempo e pouca memória?)

Utilize gráficos ou tabelas para comparar as várias estratégias.

Utilize as seguintes configurações iniciais de teste:

1	2	3	4		1	2	3	4
5	6	8	12		13	6	8	12
13	9		7		5	9		7
14	11	10	15		14	11	10	15

Utilize a seguinte configuração final para testar as duas configurações iniciais sugeridas:

1	2	3	4
5	6	7	8
9	10	11	12
13	14	15

A primeira configuração tem solução ótima em profundidade 12 (menor número de movimentos possível para chegar da configuração inicial à configuração final).

A segunda configuração inicial não leva à configuração final proposta. Explique o porque.

Não esqueça que o seu programa deve estar preparado para receber qualquer configuração inicial ou final num formato em linha. Por exemplo,

1 2 3 4 5 6 8 12 13 9 0 7 14 11 10 15
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0

onde a primeira configuração corresponde à primeira configuração inicial sugerida anteriormente e a segunda configuração corresponde à configuração de teste sugerida também anteriormente.

O seu código deve verificar se há solução para chegar do estado inicial ao estado final antes de iniciar a busca, e deve emitir uma mensagem de erro se não houver caminho entre a solução inicial e a final.

Utilize o algoritmo 1 como base para implementar todas as buscas (este é o algoritmo geral de busca, mas com um teste inicial específico para jogos do tipo jogo dos 15 - teste de resolubilidade):

Este algoritmo, além de receber as configurações inicial e final, recebe também como parâmetro uma função de enfileiramento que será utilizada para ordenar a lista de nós (configurações) abertos (ainda não explorados).