inteligencia artificial

Resolução de problemas por meio de busca

Prof. Manuel Fdez. Paradela Ledón.

Exercício ou problema?
Exercício ou problema?
“First, what is a problem? We distinguish between problems and exercises. An exercise is a question that you know how to resolve immediately. Whether you get it right or not depends on how expertly you apply specific techniques, but you don't need to puzzle out what techniques to use. In contrast, a problem demands much thought and resourcefulness before the right approach is found.” Paul Zeitz (ZEITZ, 2007).

• Um exercício é uma questão que você conhece como resolver imediatamente. • Um problema demanda muito mais reflexão e esforço para desembaraçar antes de encontrar a abordagem apropriada.

Problemas intratáveis
• São problemas tal vez possíveis de serem resolvidos com recursos ilimitados, porém impossíveis com recursos limitados;
• Quando um problema poderia ser resolvido em tempo exponencial, por exemplo, um problema com solução do tipo O(2n), tal problema poderia ser considerado INTRATÁVEL, pois nenhum computador resolve-o num tempo satisfatório, a não ser que o número "n" seja baixo.

Problemas tratáveis
• São problemas possíveis de serem solucionados com recursos limitados ou razoáveis.

• Quando a complexidade do algoritmo é polinomial, apesar do problema e sua complexidade, é considerado TRATÁVEL.
• Os problemas tratáveis são comumente classificados, por exemplo, em:

Problemas tratáveis de tipo P – Problemas P
– É a classe dos problemas resolvíveis em tempo polinomial em uma máquina determinística.

Problemas tratáveis de tipo NP - Problemas NP
– É a classe dos problemas resolvíveis em tempo polinomial em uma máquina não-determinística (as siglas significam nondeterministic polynomial time).

Computadores determinísticos e não-determinísticos
Computador determinístico só poderá estar em um estado por vez (PC comum, que executa um processo de cada vez).
Computador não