Soluciones heurísticas

En esta página, aprenderás que incluso para los problemas de tiempo no razonables, puede haber soluciones "suficientemente cercanas" a un tiempo razonable.

AAP-4.A.6, AAP-4.A.8, AAP-4.A.9

Si un problema puede ser resuelto en tiempo exponencial, puede haber un algoritmo diferente que lo haga en tiempo polinómico (es decir, más rápidamente), pero algunos problemas no pueden ser respondidos en tiempo polinómico. Es importante reconocer que un algoritmo de tiempo exponencial todavía resuelve un problema correctamente; solo que toma un tiempo irrazonablemente largo (tal vez incluso cientos de años para algunos insumos, por ejemplo).

Los algoritmos de tiempo exponencial a veces pueden ser reemplazados por heurística, que son algoritmos de tiempo polinómico que no resuelven el problema exactamente, pero dan una aproximación bastante buena. Pero la heurística es útil solo para ciertos tipos de problemas.

: Problema de decisión vs. problema de optimización 
AAP-4.A.2
  1. ¿Para qué tipo de problemas (problemas de optimización o problemas de decisión) una solución heurística puede ser útil?

Un ejemplo de un problema para el cual una solución heurística es útil es el problema del vendedor viajero: Para un grupo de ciudades, ¿cuál es la ruta más corta para que un vendedor visite cada ciudad y regrese a su ciudad de origen? Este es un buen caso para la heurística porque:

  1. Está claro que debe haber una ruta más corta.
  2. No se conoce ningún algoritmo de tiempo polinómico para este problema. (La mayoría de los informáticos piensan que no es posible escribir uno.)
  3. Hay una posible heurística: elige un camino al azar y luego intenta mejorarlo intercambiando dos ciudades repetidamente hasta que no puedas mejorar el camino con cambios tan pequeños.
Esta heurística es llamada "ascenso de colinas" porque encontrarás el mejor camino cercano (la cima de una colina), pero podría haber una colina más alta (un mejor camino) más lejos.

  1. AAP-4.A part b
    ¿En cuál de los siguientes problemas es apropiada una solución heurística?
    Encontrar el elemento más grande de una lista.
    Encontrar la mejor combinación de ingredientes para la salsa de espagueti.
    Jugar al ajedrez.
    Encontrar la combinación de una cerradura de n números.

¿Pueden resolverse todos los problemas de decisión?

Resulta que no todos los problemas de decisión (preguntas de verdadero/falso) pueden ser resueltos con un algoritmo.

: Problema resoluble vs. problema indecidible
AAP-4.B.1, AAP-4.B.2, AAP-4.B.3

Un problema resoluble (decidable) es un problema de decisión para el cual es posible escribir un algoritmo que dará una salida correcta para todas las entradas.

Un problema indecidible (undecidable) es lo opuesto.  No es posible escribir un algoritmo que dará una salida correcta para todas las entradas—aunque podría ser posible para algunos de ellos.

La pregunta  "¿el número entero es par?"es ejemplo de un problema resoluble porque es posible escribir un algoritmo que determinará si un número entero es par.

La pregunta "¿este programa de computadora que toma una entrada siempre reportará eventualmente un resultado?" es un problema indecidible. Es posible escribir un algoritmo de comprobación que sea capaz de decir por algunos programas con algunas entradas si reportarán un resultado o se atascarán en un bucle infinito y nunca reportarán. Pero resulta que no es posible escribir un algoritmo de comprobación que funcione para cualquier programa con cualquier entrada. (Puedes ver una prueba de que ningún algoritmo de comprobación de este tipo—para una computadora o persona—puede ser escrito en el Laboratorio 4 de esta unidad.)

    AAP-4.B
  1. Habla con tu compañeroQué significa que un problema sea indecidible?