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:

1. 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).
2. 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.
3. 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:

   P = ( I, B, C )

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

   +---+         +---+
   |   |   O     |   |
   | B | = = = > | C |
   |   |         |   |
   +---+         +---+

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.

     Caso A: Un Puzle

Existe un tablero de 4x4 casas y 15 piezas solamente. El problema a resolver consiste en determinar cómo tenemos que mover las piezas en el tablero, de forma de obtener una configuración previamente definida. Existe una regla para la ejecución: solamente se permite mover una pieza por vez, y hacia un lugar adyacente vacío.

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.

     Caso B: Un Diagnóstico

Un problema de diagnóstico médico puede ser modelado de una manera similar, y donde:

El problema "P" es el diagnóstico;
El conjunto "B" de datos del problema son los resultados de exámenes correspondientes al paciente y solicitados por el médico;
El conjunto "C" de la solución es el conjunto de todas las dolencias posibles.

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 solución del problema de búsqueda de las raíces de un polinomio con coeficientes reales, consiste en asociar n números complejos cn, a cada conjunto de coeficientes de un polinomio particular p(x) de grado n, de modo que se satisfaga la condición de que sea nulo el valor de p(x) haciendo x igual c, para todo c perteneciente al conjunto cn.

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.

     Ejemplo 1.1:

Sea una agenda telefónica. Obviamente, ella puede ser considerada como la función que asocia a cada nombre de persona su correspondiente teléfono.

• Declarativamente: Definiendo propiedades que permiten definir la solución del problema.

     Ejemplo 2.1:

Dado un número real, asociar dos números reales cuya suma de cuadrados sea igual al cuadrado del número real dado. Naturalmente, en este planteamiento es posible reconocer la aplicación del Teorema de Pitágoras, y desde el punto de vista gráfico, la solución puede ser visualizada como un círculo, en un plano de coordenadas ortogonales (ejes ortogonales y misma escala), de diámetro igual al número dado.

     Ejemplo 2.2:

Sea la función característica del conjunto de ecuaciones diofánticas de cuarto orden que tiene solución. Véase que a partir del tercer orden, se sabe que no hay teorema que permita saber si el problema tiene o no solución. Por lo tanto, la estrategia de solución que resta es intentar todas las posibilidades... y como existen infinitos números enteros, al aplicarse el procedimiento no puede tenerse certeza si se trata de un caso que no tiene solución, o si por el contrario sí la tiene pero la misma aún no ha sido hallada.

• 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.

     Ejemplo 3.1:

Formulario de Impuesto de Renta

• 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.

     Ejemplo 4.1:

Se acostumbra emplear redes neuronales con aprendizaje supervizado, y se usan los ejemplos para entrenar la red, y obtener valores estimados de la solución para otros valores, por aplicación de 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.

Véase también

• Resolución de problemas
• Inteligencia artificial
• Historia de la inteligencia artificial
• Sistema experto
• TRIZ
• Problemas de Hilbert
• Teoría de la computación
• Teoría de la complejidad computacional

Enlaces externos

• Jorge Muniz Barreto, Inteligência Artificial, uma abordagem híbrida.
• Jorge Muniz Barreto, Inteligencia artificial no limiar do seculo XXI (2001), ISBN 8590038254 y 9788590038252.

• Datos: Q10380368