Teoría de los problemas
# Teoría de los problemas

Dentro de las diversas áreas de estudio se encuentran, en el marco de la inteligencia artificial (I.A.), las técnicas aplicadas a la resolución de problemas, pero desde el punto de vista teórico, también interesa establecer una tipología sobre el conjunto de los problemas, a efectos de por ejemplo dejar bien claro que frente a un problema determinado básicamente se presentan dos situaciones: o bien dicho problema no tiene solución, o bien sí la tiene; y dentro de esta última situación hay en lo básico dos casos posibles: o bien la resolución es algorítmica o bien no lo es.

## Tipos de problemas

Podemos encuadrar los problemas en tres grandes grupos:

* Los que no tienen solución, y que por tanto en los que nada puede hacerse. Estos casos son clasificados como problemas indecidibles (o imposibles de ser resueltos).
* Los que tienen solución algorítmica, y que por lo tanto podemos resolver paso a paso, codificando y aplicando los algoritmos para su resolución, ya sea en forma manual, ya sea con apoyo de equipos digitales.
* Y un tercer grupo que no pertenece a ninguno de los dos anteriores. En este grupo podemos tener:
   * Aquellos en que la solución algorítmica tiene complejidad NP-completa;
   * Aquellos en que los seres humanos son capaces de resolver con mayores o menores dificultades, a pesar de que no pueden formularse pertinentes algoritmos que permitan resolver la situación en forma más o menos automatizada; por ejemplo, jugar al ajedrez, jugar al fútbol, reconocer caras, hacer buenas traducciones de un idioma a otro, reconocer letras y palabras, buscar comida en un determinado medio, etc.

## Definición de problema

Es difícil definir precisamente lo que es un problema, aunque podemos decir que es algo que se propone para que sea resuelto. Nótese que resolver un problema no necesariamente significa tener un método o procedimiento para resolverlo. Además, antes de intentar buscar la solución de un problema, se deben responder los siguientes interrogantes :

* ¿Cuáles son los datos (informaciones)?
* ¿Cuáles son las soluciones posibles?
* ¿Qué es lo que caracteriza una solución satisfactoria?

También la cuestión puede encararse como que el problema plantea algo bastante difícil de resolver, por ejemplo, una duda, una pregunta, un enigma, un misterio. El concepto de problema puede ser mejor "entendido" al restringir la situación a una determinada área de conocimiento, o al plantearlo como familias de casos posibles.

* Problema de los caníbales y los misioneros ;
* Problema del viajante ;
* Problema de los puentes de Königsberg ;
* Problema del cartero chino ;
* Problema del tablero mutilado de ajedrez ;
* Problema de rutas de vehículos.
* Problema del camino más largo
* Problema del camino más corto

En la teoría de los problemas, un determinado problema puede ser representado, en lenguaje matemático, de la siguiente forma:

Y donde las letras representan:

P: Problema presentado;

B: Conjunto de datos del problema, conjunto no vacío, que establece las informaciones apropiadas del problema. Algunos de estos elementos pueden permanecer sin cambios o ser relativamente fijos, pero otros pueden ser cambiantes o estar en permanente dinámica. También es necesario establecer no solamente el estado inicial del problema, sino todos sus posibles estados intermedios.

I: Conjunto de operaciones y transformaciones, conjunto no vacío, que pueden ocurrir durante el proceso da resolución del problema, desde su fase inicial, hasta la obtención de la posible respuesta.

C: Condición, relación binaria, que debe satisfacer el problema. Esta relación caracteriza una solución satisfactoria; ella asocia a cada elemento del conjunto de datos, la solución única deseada. Más precisamente, esta relación binaria es el conjunto solución del problema.

## Caracterización de un problema

P

### Ejemplo 1

Una persona que enfrenta un problema para satisfacer ciertos objetivos, pero que no conoce qué acciones debe tomar para conseguir resolver el problema.

Mientras aún no se resuelve un problema, identificamos los siguientes componentes: (A) un objetivo a ser alcanzado; (B) un conjunto de acciones pre-pensadas para resolver tal problema; (C) la situación inicial de tal problema.

En este caso, el conjunto de datos del problema, podría ser descrito por la configuración inicial de las piezas en el tablero, las operaciones intermedias de búsqueda de la solución como movimientos de las piezas de acuerdo con las reglas, y la configuración final que es la propia solución del problema.

En este caso, la búsqueda de una solución es encontrar un par (d,k), tal que d $\in$ B e k $\in$ C.

En casos como el diagnóstico médico, estamos buscando una función que resuelva el problema; esa función se denominada función problema.

### Ejemplo 2

Sea el problema de hallar las raíces de un polinomio.

## La función problema

La función problema, si existe, puede ser encontrada de diversas formas:

* Enumeración exhaustiva: Enumerando todos los pares que ligan datos o planteamientos del problema con el conjunto solución. Evidentemente, este modo de definir una función, solamente se aplica en caso de que el conjunto de partida es finito.
* Declarativamente: Definiendo propiedades que permiten definir la solución del problema.
* Por un algoritmo: La correspondencia entre datos y resultados, en esta tercera modalidad, es hecha a través de un programa de computadora, y siempre que el mismo permita llegar efectivamente a una solución. Siendo así, un programa de computadora puede ser considerado como un modo de definir un problema.
* Por ejemplos: Puede reconocerse que, en este caso, la solución no es única: son válidas todas las funciones que sean iguales dentro de un subconjunto en que el problema es definido, y si es necesario hacer una aproximación, entonces se acostumbra a usar técnicas de inteligencia artificial como ser las redes neuronales. Así, los ejemplos se usan para entrenar a la red y obtener valores estimados de la solución para otros valores, usando la propiedad de generalización de las redes.

Los modos de definir una función, llevan a temáticas tales como Complejidad y Teoría de la computabilidad.

## Notas y referencias

* ↑ Monografía: Métodos de Solución de Problemas de Inteligencia Artificial (resumen), texto íntegro.
* ↑ Joaquín Borrego-Díaz, Presentación de la "teoria de la computabilidad", espacio digital 'SlideShare', 27 de noviembre de 2009.
* ↑ Juan Blas Climent Vidal, Teoría de la computabilidad, documento digital pdf.
* ↑ Sobre la "Teoría de la Computabilidad", sitio digital 'Decsai.ugr'.
* ↑ José Luis Alba, Jesús Cid, Reconocimiento de patrones, documento pdf, mayo de 2006.
* ↑ Ordenadores y ajedrez, sitio digital 'Wikipedia'.
