Considerando que nesta Unidade estudamos diferentes métodos para a resolução de problemas por meio de buscas em um espaço de estados, de modo que um espaço de estados – state space – é uma representação dos estados possíveis pelos quais transcorremà solução de um problema, ou seja, os possíveis caminhos e estados que podemos gerar e visitar para chegar à resolução de um determinado problema;na representação gráfica da solução de um problema em um espaço de estados, utilizamos frequentemente um grafo, com nós e arcos. Assim, considerando que na seguinte Figura foi desenhado um grafo de tempos necessários, em minutos, para ir de carro de um ponto de referência da cidade para outro ponto, em condições normais de trânsito e a uma velocidade constante de 50 km/h:

Deve-se definir um estado inicial e outro final para a resolução deste problema da seguinte forma:

a.
Um custo de caminhomínimo poderia ser uma solução ótima do problema;os pontos de referência do grafo devem ser todos estados intermediários,sendo desejável que o algoritmo utilizado seja completo, além de ótimo.

b.
O maior custo de caminho poderia ser uma solução ótima do problema;os restantes pontos de referência seriam estados finais,sendo desejável que o algoritmo utilizado seja completo, além de ótimo.

c.
Um custo de caminhomáximo poderia ser uma solução ótima do problema;os restantes pontos de referência seriam estados intermediários,sendo desejável que o algoritmo utilizado seja completo, além de ótimo.

d.
Um custo de caminho mínimo poderia ser uma solução ótima do problema;os restantes pontos de referência seriam estados intermediários,sendo desejável que o algoritmo utilizado não seja completo, nem ótimo, para efetuar um teste por refutação.

e.
Um custo de caminho mínimo poderia ser uma solução ótima do problema;os restantes pontos de referência seriam estados intermediários, sendo desejável que o algoritmo utilizado seja completo, além de ótimo.