Código exemplo

Para executar esta atividade deve ter os Algoritmos de IIA compilados e podendo ser executados localmente, ou executar o código a partir do VPL no recurso Algoritmos IIA, de forma idêntica à AF2b.

 Ação 1: Correr o programa resultante de Algoritmos Introdução à Inteligência Artificial.

 Ação 2: O Aspirador tem uma função heurística implementada, que pode ser visualizada na exploração dos sucessores: 2.

Na informação sobre o estado, a letra h tem a informação sobre a heurística, h(n) no manual. No estado inicial o valor da heurística é 4, significando que não é possível com menos de 4 movimentos atingir-se o objetivo. A heurística sendo admissível nunca ultrapassa o custo mínimo até à solução final. Esta heurística é feita com base num procedimento simples, que conduz à solução ótima para este problema:

• Começar por um dos lados, para a sala suja mais à esquerda ou à direita (conforme a que estiver mais próxima), e ir limpando até chegar à última sala suja

Esta estratégia é óptima, o que nos ajuda aqui a ter um problema em que identificamos a heurística perfeita, e ver se os algoritmos informados fazem bom uso desta informação. Esta situação já não irá ocorrer em muitos outros problemas, ou numa versão deste problema que se complique, e veremos que os algoritmos ainda assim fazem bom uso desta.

Em vez de se implementar o algoritmo diretamente, o que se tem de definir é o custo para a solução objetivo. Neste caso será somar os movimentos até um extremo das salas sujas, os movimentos para se mover do extremo para outro, e o tempo de limpar todas as salas sujas. Não é preciso dar indicação para ir primeiro para a sala suja mais próxima, embora a ideia por detrás desta heurística foi essa intenção em mente. 

A vantagem de se utilizar um algoritmo genérico, é que se a heurística não for perfeita, mas for admissível, isto é, não sobre-estimar o custo, os algoritmos irão conseguir à mesma encontrar a solução ótima.

Reparar que apenas um estado sucessor a heurística diminui.

Ação 3: Executar manualmente o algoritmo melhor primeiro, em que avança sempre para o sucessor com a menor heurística.

Este foi o resultado da resolução manual, avançando sempre pelo melhor sucessor, com base no valor da heurística. Com uma heurística perfeita, esta solução é também óptima. Pode utilizar esta técnica para instâncias de qualquer dimensão, caso naturalmente exista uma heurística perfeita, o que nem sempre acontece.