Análisis de algoritmos

El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional másamplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo que resuelvaun problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda dealgoritmos eficientes.

A la hora de realizar un análisis teórico de algoritmos es corriente calcular su complejidad en un sentidoasintótico, es decir, para un tamaño de entrada suficientemente grande. Por ejemplo, la búsquedabinaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)),coloquialmente "en tiempo logarítmico". Normalmente las estimaciones asintóticas se utilizan porquediferentes implementaciones del mismo algoritmo no tienen porque tener la misma eficiencia. Noobstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado estánrelacionadas por una constante multiplicativa llamada constante oculta.

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usanalgoritmos, porque tienen más precisión y así les permite saber cuanto tiempo pueden suponer quetomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constanteoculta puede significar la diferencia entre éxito y fracaso.

Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido,debemos garantizar que el tiempo requerido para realizar un paso esté acotado superiormente por unaconstante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con quela suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertoscontextos. Si por ejemplo los números involucrados en la computación pueden ser arbitrariamentegrandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz,compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlocon enteros de 1000 dígitos).

Complejidad computacional

La teoría de la complejidad computacional es la rama de la teoría de la computación que estudia, demanera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema.Los recursos comúnmente estudiados son el tiempo (mediante una aproximación al número y tipo depasos de ejecución de un algoritmo para resolver un problema) y el espacio (mediante una aproximacióna la cantidad de memoria utilizada para resolver un problema). Se pueden estudiar igualmente otrosparámetros, tales como el número de procesadores necesarios para resolver el problema en paralelo.

Hoy en día las computadoras resuelven problemas mediante algoritmos que tienen como máximo unacomplejidad o coste computacional polinómico, es decir, la relación entre el tamaño del problema y sutiempo de ejecución es polinómica. Éstos son problemas agrupados en el conjunto P. Los problemas queno pueden ser resueltos por nuestras computadoras (las cuales son Máquinas Determinísticas), que engeneral poseen costes factorial o combinatorio, pero podrían ser procesados por una Máquina NoDeterminística, están agrupados en el conjunto NP. Estos problemas no tienen una solución practicajesdecir, una máquina determinística (como una computadora actual) no puede resolverlos en un tiemporazonable.

Clases de complejidad

En teoría de la complejidad, la clase de complejidad de los problemas de decisión que pueden serresueltos en tiempo polinómico calculado a partir de la entrada por una máquina de Turing determinista

Diagrama de clases de complejidad. Si P = NP, P contendría las zonas NP y NP-completo.

Los problemas NP-completos pueden ser descritos como los problemas en NP que tienen menosposibilidades de estar en P. Actualmente los investigadores piensan que las clases cumplen con eldiagrama mostrado por lo que P y NP-completo tendrían intersección vacía.

La importancia de la pregunta P = NP radica en que de encontrarse un algoritmo en P para un problemaNP-completo, todos los problemas NP-completos (y por ende, todos los problemas de NP) tendríansoluciones en tiempo polinómico.

Presentación

Un problema dado puede verse como un conjunto de preguntas relacionadas, donde cada pregunta serepresenta por una cadena de caracteres de tamaño finito. Por ejemplo, el problema factorización enterase describe como: Dado un entero escrito en notación binaria, retornar todos los factores primos de esenúmero. Una pregunta sobre un entero específico se llama una instancia, por ejemplo, "Encontrar losfactores primos del número 15" es una instancia del problema factorización entera.

La complejidad temporal de un problema es el número de pasos que toma resolver una instancia de unproblema, a partir del tamaño de la entrada utilizando el algoritmo más eficiente a disposición.Intuitivamente, si se toma una instancia con entrada de longitud n que puede resolverse en n2 pasos, sedice que ese problema tiene una complejidad en tiempo de n2. Por supuesto, el número exacto de pasosdepende de la máquina en la que se implementa, del lenguaje utilizado y de otros factores. Para no tenerque hablar del costo exacto de un cálculo se utiliza la notación O. Cuando un problema tiene costo entiempo O(n2) en una configuración de computador y lenguaje dado este costo será el mismo en todos loscomputadores, de manera que esta notación generaliza la noción de coste independientemente del equipoutilizado.

Ejemplos

• Extraer cualquier elemento de un vector. La indexación en un vector o array lleva el mismotiempo sea cual fuere el índice que se quiera buscar, por tanto es una operación decomplejidad constante O(l).

• Buscar en un diccionario tiene complejidad logarítmica. Se puede iniciar la búsqueda deuna palabra por la mitad del diccionario. Inmediatamente se sabe si se ha encontrado lapalabra o, en el caso contrario, en cuál de las dos mitades hay que repetir el proceso (es unproceso recursivo) hasta llegar al resultado. En cada (sub)búsqueda el problema (las

es llamada P. Cuando se trata de una máquina de Turing no-determinista, la clase se llama NP. Una delas preguntas abiertas más importantes en la actualidad es descubrir si estas clases son diferentes o no. ElClay Mathematics Institute ofrece un millón de dólares a quien sea capaz de responder a esa pregunta.

páginas en las que la palabra puede estar) se ha reducido a la mitad, lo que se correspondecon la función logarítmica. Este procedimiento de búsqueda (conocido como búsquedabinaria) en una estructura ordenada tiene complejidad logarítmica O(ln n).

• E1 proceso más común para ordenar un conjunto de elementos tiene complejidadcuadrática. El procedimiento consiste en crear una colección vacía de elementos. A ella seañade, en orden, el menor elemento del conjunto original que aún no haya sido elegido, loque implica hacer un recorrido completo del conjunto original (O(n), siendo n el númerode elementos del conjunto). Este recorrido sobre el conjunto original se realiza hasta quetodos sus elementos están en la secuencia de resultado. Se puede ver que hay que hacern selecciones (se ordena todo el conjunto) cada una con un coste n de ejecución: elprocedimiento es de orden cuadrático O(n2). Hay que aclarar que hay diversos algoritmosde ordenación con mejores resultados.

Problemas de decisión

La mayor parte de los problemas en teoría de la complejidad tienen que ver con los problemas dedecisión, que corresponden a poder dar una respuesta positiva o negativa a un problema dado. Porejemplo, el problema ES-PRIMO se puede describir como: Dado un entero, responder si ese número esprimo o no. Un problema de decisión es equivalente a un lenguaje formal, que es un conjunto de palabrasde longitud finita en un lenguaje dado. Para un problema de decisión dado, el lenguaje equivalente es elconjunto de entradas para el cual la respuesta es positiva.

Los problemas de decisión son importantes porque casi todo problema puede ser transformado en unproblema de decisión. Por ejemplo el problema CONTIENE-FACTORES descrito como: Dados dosenteros n y k, decidir si n tiene algún factor menor que k. Si se puede resolver CONTIENE-FACTOREScon una cierta cantidad de recursos, su solución se puede utilizar para resolver FACTORIZAR con losmismos recursos, realizando una búsqueda binaria sobre k hasta encontrar el más pequeño factor de n,luego se divide ese factor y se repite el proceso hasta encontrar todos los factores.

En teoría de la complejidad, generalmente se distingue entre soluciones positivas o negativas. Porejemplo, el conjunto NP se define como el conjunto de los problemas en donde las respuestas positivaspueden ser verificadas muy rápidamente (es decir, en tiempo polinómico). El conjunto Co-P es elconjunto de problemas donde las respuestas negativas pueden ser verificadas rápidamente. El prefijo"Co" abrevia "complemento". El complemento de un problema es aquel en donde las respuestas positivasy negativas están intercambiadas, como entre ES-COMPUESTO y ES-PRIMO.

Un resultado importante en teoría de la complejidad es el hecho de que independientemente de ladificultad de un problema (es decir de cuántos recursos de espacio y tiempo necesita), siempre habráproblemas más difíciles. Esto lo determina en el caso de los costes en tiempo el teorema de la jerarquíatemporal. De éste se deriva también un teorema similar con respecto al espacio.

Intratabilidad

Los problemas que pueden ser resueltos en teoría, pero no en práctica, se llaman intratables. Qué sepuede y qué no en la práctica es un tema debatible, pero en general sólo los problemas que tienensoluciones de tiempos polinomiales son solubles para más que unos cuantos valores. Entre los problemasintratables se incluyen los de EXPTIME-completo. Si NP no es igual a P, entonces todos los problemasde NP-completo son también intratables.

Para ver por qué las soluciones de tiempo exponencial no son útiles en la práctica, se puede considerar unproblema que requiera 2" operaciones para su resolución (n es el tamaño de la fuente de información).Para una fuente de información relativamente pequeña, n=100, y asumiendo que una computadora puedellevar a cabo 1010 (10 giga) operaciones por segundo, una solución llevaría cerca de 4*1012 años para

completarse, mucho más tiempo que la actual edad del universo.

Técnicas de diseño de algoritmos

• Algoritmos voraces (greedy): seleccionan los elementos más prometedores del conjunto decandidatos hasta encontrar una solución. En la mayoría de los casos la solución no es óptima.

• Algoritmos paralelos: permiten la división de un problema en subproblemas de forma que sepuedan ejecutar de forma simultánea en varios procesadores.

• Algoritmos probabilísticos: algunos de los pasos de este tipo de algoritmos están en función devalores pseudoaleatorios

• Algoritmos determinísticos: El comportamiento del algoritmo es lineal: cada paso del algoritmotiene únicamente un paso sucesor y otro ancesor.

• Algoritmos no determinísticos: El comportamiento del algoritmo tiene forma de árbol y a cadapaso del algoritmo puede bifurcarse a cualquier número de pasos inmediatamente posteriores,además todas las ramas se ejecutan simultáneamente.

• Divide y vencerás: dividen el problema en subconjuntos disjuntos obteniendo una solución decada uno de ellos para después unirlas, logrando así la solución al problema completo.

• Metalieurísticas: encuentran soluciones aproximadas (no óptimas) a problemas basándose en unconocimiento anterior (a veces llamado experiencia) de los mismos.

• Programación dinámica: intenta resolver problemas disminuyendo su coste computacionalaumentando el coste espacial.

• Ramificación y acotación: se basa en la construcción de las soluciones al problema mediante unárbol implícito que se recorre de forma controlada encontrando las mejores soluciones.

• Vuelta Atrás (Backtracking): se construye el espacio de soluciones del problema en un árbol quese examina completamente, almacenando las soluciones menos costosas.

Algoritmo voraz

Un algoritmo voraz (también conocido como ávido o devorador) es aquel que, para resolver undeterminado problema, sigue una metaheurística consistente en elegir la opción óptima en cada pasolocal con la esperanza de llegar a una solución general óptima. Este esquema algorítmico es el que menosdificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente se aplica a losproblemas de optimización.

Esquema

Dado un conjunto finito de entradas C, un algoritmo voraz devuelve un conjunto S (seleccionados) talque S C y que además cumple con las restricciones del problema inicial. Cada conjunto C quesatisfaga las restricciones se le suele denominar prometedor, y si éste además logra que la funciónobjetivo se minimice o maximice (según corresponda) diremos que C es una solución óptima.

Elementos de los que consta la técnica

• El conjunto C de candidatos, entradas del problema.• Función solución. Comprueba, en cada paso, si el subconjunto actual de candidatos elegidos

forma una solución (no importa si es óptima o no lo es).• Función de selección. Informa de cuál es el elemento más prometedor para completar la

solución. Éste no puede haber sido rechazado o escogido con anterioridad. Cada elemento esconsiderado una sola vez. Luego, puede ser rechazado o aceptado y pertenecerá a C\S.

• Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una solución.Lo aplicaremos al conjunto de seleccionados unido con el elemento más prometedor.

• Función objetivo. Es aquella que queremos maximizar o minimizar, el núcleo del problema.

Funcionamiento.

El algoritmo escoge en cada paso al mejor elemento posible, conocido como el elemento másprometedor. Se elimina ese elemento del conjunto de candidatos y, acto seguido,comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados (S {X})produce una solución factible.

En caso de que así sea, se incluye ese elemento en S. Si la inclusión no fuera factible, se descarta elelemento. Iteramos el bucle, comprobando si el conjunto de seleccionados es una solución y, si no es así,pasando al siguiente elemento del conjunto de candidatos.

Una vez finalizado el bucle, el algoritmo comprueba si el conjunto S es una solución o no, devolviendo elresultado apropiado en cada caso.

Algoritmo paralelo

En las ciencias de la computación, un algoritmo paralelo, en oposición a los, algoritmos clásicos oalgoritmos secuenciales, es un algoritmo que puede ser ejecutado por partes en el mismo instante detiempo por varias unidades de procesamiento, para finalmente unir todas las partes y obtener elresultado correcto.

Algunos algoritmos son fácilmente divisibles en partes; como por ejemplo, un algoritmo que calculetodos los números primos entre 1 y 100, donde se podría dividir los números originales ensubconjuntos y calcular los primos para cada uno de los subconjuntos de los números originales; alfinal, uniríamos todos los resultados y tendríamos la solución final del algoritmo.

Por contra, a veces los problemas no son tan fácilmente paralelizables, de ahí que estos problemas seconozcan como problemas inherentemente secuenciales. Como ejemplo de estos métodos tendríamoslos métodos numéricos iterativos como el método de Newton.

El análisis o cálculo numérico es la rama de las matemáticas que se encarga de diseñar algoritmospara, a través de números y reglas matemáticas simples simular procesos matemáticos más complejosaplicados a procesos del mundo real.

En análisis numérico, el método de Newton (conocido también como el método de Newton-Raphson o elmétodo de Newton-Fourier) es un algoritmo eficiente para encontrar aproximaciones de los ceros oraíces de una función real. También puede ser usado para encontrar el máximo o mínimo de unafunción, encontrando los ceros de su primer a derivada.

Por otro lado, algunos problemas son difícilmente paralelizables, aunque tengan una estructurarecursiva. Los algoritmos paralelos son importantes porque es más rápido tratar grandes tareas decomputación mediante la paralelización que mediante técnicas secuenciales. Esta es la forma en quese trabaja en el desarrollo de los procesadores modernos, ya que es más difícil incrementar lacapacidad de procesamiento con un único procesador que aumentar su capacidad de cómputo mediantela inclusión de unidades en paralelo, logrando así la ejecución de varios flujos de instrucciones dentrodel procesador. Pero hay que ser cauto con la excesiva paralelización de los algoritmos ya que cadaalgoritmo paralelo tiene una parte secuencial y debido a esto, los algoritmos paralelos puedes llegar a unpunto de saturación (ver Ley de Amdahl). Por todo esto, a partir de cierto nivel de paralelismo, añadir

más unidades de procesamiento puede sólo incrementar el coste y la disipación de calor.

La Ley de Amdahl, llamada así por el arquitecto de ordenadores Gene Amdahl, se usa para averiguar lamejora máxima de un sistema cuando solo una parte de éste es mejorado. Establece que "la mejoraobtenida en el rendimiento de un sistema debido a la alteración de uno de sus componentes está limitadapor la fracción de tiempo que se utiliza dicho componente".

El coste o complejidad de los algoritmos secuenciales se estima en términos del espacio (memoria) ytiempo (ciclos de procesador) que requiera. Los algoritmos paralélelos también necesitan optimizar lacomunicación entre diferentes unidades de procesamiento. Esto se consigue mediante la aplicación dedos paradigmas de programación y diseño de procesadores distintos: memoria compartida o paso demensajes.

MPI ("Message Passing Interface ", Interfaz de Paso de Mensajes) es un estándar que define la sintaxis yla semántica de las funciones contenidas en una librería de paso de mensajes diseñada para ser usada enprogramas que exploten la existencia de múltiples procesadores.

El paso de mensajes es una técnica empleada en programación concurrente para aportar sincronizaciónentre procesos y permitir la exclusión mutua, de manera similar a como se hace con los semáforos,monitores, etc. Su principal característica es que no precisa de memoria compartida, por lo que es muyimportante en la programación para sistemas distribuidos. Los elementos principales que intervienen enel paso de mensajes son el proceso que envía, el que recibe y el mensaje.

La técnica memoria compartida necesita del uso de cerrojos en los datos para impedir que se modifiquesimultáneamente por dos procesadores, por lo que se produce un coste extra en ciclos de CPUdesperdiciados y ciclos de bus. También obliga a señalizar alguna parte del algoritmo.

La técnica paso de mensajes usa canales y mensajes pero esta comunicación añade un coste al bus,memoria adicional para las colas y los mensajes y latencia en el mensaje. Los diseñadores deprocesadores paralelos usan buses especiales para que el coste de la comunicación sea pequeño perosiendo el algoritmo paralelo el que decide el volumen del tráfico.

Finalmente, una subclase de los algoritmos paralelos, los algoritmos distribuidos son algoritmosdiseñados para trabajar en entornos tipo clusters y de computación distribuida, donde se usan otrastécnicas, fuera del alcance de los algoritmos paralelos clásicos.

Algoritmo probabilista

Un algoritmo probabilista (o probabilístico) es un algoritmo que basa su resultado en la toma dealgunas decisiones al azar, de tal forma que, en promedio, obtiene una buena solución al problemaplanteado para cualquier distribución de los datos de entrada. Es decir, al contrario que un algoritmodeterminista, a partir de unos mismos datos se pueden obtener distintas soluciones y, en algunos casos,soluciones erróneas.

Existen varios tipos de algoritmos probabilísticos dependiendo de su funcionamiento, pudiéndosedistinguir:

• Algoritmos numéricos, que proporcionan una solución aproximada del problema.• Algoritmos de Monte Cario, que pueden dar la respuesta correcta o respuesta erróneas (con

probabilidad baja).• Algoritmos de Las Vegas, que nunca dan una respuesta incorrecta: o bien dan la

respuesta correcta o informan del fallo.

Consideraciones

Se puede optar por la elección aleatoria si se tiene un problema cuya elección óptima es demasiadocostosa frente a la decisión aleatoria. Un algoritmo probabilista puede comportarse de distinta formaaplicando la misma entrada. A un algoritmo determinista nunca se le permite que no termine: hacer una división por O,

entrar en un bucle infinito, etc. Si existe más de una solución para unos datos dados, un algoritmo determinista siempre

encuentra la misma solución (a no ser que se programe para encontrar varias o todas). Un algoritmo probabilista puede encontrar soluciones diferentes ejecutándose varias veces

con los mismos datos. A un algoritmo determinista no se le permite que calcule una solución incorrecta para

ningún dato. Un algoritmo probabilista puede equivocarse siempre que esto ocurra con una probabilidad

pequeña para cada dato de entrada. Repitiendo la ejecución un número suficiente de veces para el mismo dato, puede

aumentarse tanto como se quiera el grado de confianza en obtener la solución correcta. El análisis de la eficiencia de un algoritmo determinista es, en determinadas ocasiones,

difícil. El análisis de los algoritmos probabilistas es, a menudo, muy difícil.

Algoritmos numéricos

La solución obtenida es siempre aproximada pero su precisión esperada mejora aumentando el tiempo deejecución. Normalmente, el error es inversamente proporcional a la raíz cuadrada del esfuerzo invertidoen el cálculo.

Ejemplo: La aguja de Buffon

Algoritmo de Monte Carlo:

• A veces da una solución incorrecta.• Con una alta probabilidad encuentra una solución correcta sea cual sea la entrada.

Definición: Sea p un número real tal que 0 < p < l. Un algoritmo de Monte Cario es p-correcto si:.

• Devuelve una solución correcta con probabilidad mayor o igual que p, cualesquieraque sean los datos de entrada.

• A veces, p dependerá del tamaño de la entrada, pero nunca de los datos de la entradaen sí.

Un ejemplo de algoritmo de Monte Carlo (el más conocido): decidir si un número impar esprimo o compuesto.

• Ningún algoritmo determinista conocido puede responder en un tiempo "razonable" siel número tiene cientos de cifras.

• La utilización de primos de cientos de cifras es fundamental en criptografíaPierre Fermat postuló en 1640 el Pequeño teorema de Fermat: Sea n primo. Entonces, a^(n-l) mod n <> 1para todo entero a tal que 1<=a<=n-l.

Algoritmos de Las Vegas

Un algoritmo de Las Vegas nunca da una solución falsa.

• Toma decisiones al azar para encontrar una solución antes que un algoritmo determinista.• Si no encuentra solución lo admite.

Hay dos tipos de algoritmos de Las Vegas, según la posibilidad de no encontrar una solución:

• Los que siempre encuentran una solución correcta, aunque las decisiones al azar no seanafortunadas y la eficiencia disminuya.

• Los que a veces, debido a decisiones desafortunadas, no encuentran una solución.

Tipo a: Algoritmos de Sherwood

Existe una solución determinista que es mucho más rápida en media que en el peor caso.

Ejemplo: quicksort.

Tipo b: Algoritmos que, a veces, no dan respuesta.

• Son aceptables si fallan con probabilidad baja.• Si fallan, se vuelven a ejecutar con la misma entrada.• Resuelven problemas para los que no se conocen algoritmos deterministas

eficientes (ejemplo: la factorización de enteros grandes).• E1 tiempo de ejecución no está acotado pero sí es razonable con la probabilidad deseada

para toda entrada.

Algoritmo determinístico

En Ciencias de la computación, un algoritmo determinístico es un algoritmo que, en términosinformales, es completamente predictivo si se conocen las entradas al mismo. Dicho de otra forma, si seconocen las entradas del algoritmo siempre producirá la misma salida, y la máquina interna pasará por lamisma secuencia de estados. Este tipo de algoritmos ha sido el más estudiado durante la historia y por lotanto resulta ser el tipo más familiar de los algoritmos, así como el más práctico ya que puede ejecutarseen las máquinas eficientemente.

Un modelo simple de algoritmo determinístico es la función matemática, de esta forma se puedeestablecer el siguiente paralelismo: la función extrae la misma salida para una entrada dada, al igual quelos algoritmos determinísticos. La diferencia es que un algoritmo describe explícitamente como la salidase obtiene de la entrada, mientras que las funciones definen implícitamente su salida.

v

Definición formal

Formalmente los algoritmos determinísticos se pueden definir en términos de una máquina de estado: unestado describe que está haciendo la máquina en un instante particular de tiempo. Justo cuando seproduce la entrada, la máquina comienza en su estado inicial y, posteriormente, si la máquina esdeterminística, comenzará la ejecución de la secuencia de estados predeterminados. Una máquina puedeser determinística y no tener límite temporal para la ejecución o quedarse en un bucle de estados cíclicoseternamente.

Qué hace a un algoritmo no determinístico

Una variedad de factores puede ser la causa de que un algoritmo determinístico se comporte como de unaforma no determinística:

• Si emplea en la ejecución de la secuencia de estados otro estado "externo" como entrada delproceso, como por ejemplo: una entrada de un usuario, una variable objetivo, un valor deun temporizador de hardware, un valor aleatorio, etc.

• Si al operar se encuentra con concurrencia de estados, por ejemplo si tiene múltiplesprocesadores escribiendo al mismo tiempo en un fichero. En este caso el orden preciso en elque cada procesador escribe el dato puede afectar a la salida y no está pre-planificado suvalor inicial.

• Si un error (cuyo origen puede deberse al hardware o al software) causa un inesperadocambio en la secuencia de ejecución de estados.

Aunque los programas reales rara vez son puramente determinísticos, es más fácil que los seres humanosasí como otros programas determinar sobre la esencia de lo que realmente son. Por esta razón, la mayoríade los lenguajes de programación y especialmente aquellos que entran dentro de la categoría deprogramación funcional son lenguajes que hacen un esfuerzo en prevenir eventos que se ejecutan sincontrol. Por esta razón este tipo de restricciones fuerzan el carácter determinístico, a los algoritmosdeterministicos se les denomina purely functional.

Problemas con los algoritmos determinísticos :

Para algunos problemas es muy difícil implementar un algoritmo determinístico. Por ejemplo, existeneficientes y simples algoritmos probabilísticos que pueden determinar si un número entero es primo o no,pero tienen una pequeña posibilidad de equivocarse. Algunos de ellos son muy conocidos desde 1970(véase, por ejemplo, el Test de primalidad de Fermat); solamente tras otros 30 años de investigaciónfocalizada en investigar se ha encontrado un algoritmo determinístico similar, pero mucho más lento.

Otro ejemplo puede encontrarse en los problemas NP-completos. Dentro de esta categoría puedeencontrarse la mayoría de los problemas prácticos; este tipo de problemas puede resolverse rápidamenteempleando de forma masiva y paralela una máquina de Turing no determinística, pero no se haencontrado aún un algoritmo eficiente para esta tarea, al menos ahora sólo encuentran solucionesaproximadas en casos especiales.

Otro problema sobre el planteamiento de algoritmos determinísticos es que a veces no es "deseable" quelos resultados sean completamente predecibles. Por ejemplo, si se es un jugador de blackjack, unalgoritmo puede mezclar una serie de Generador de números seudoaleatorios y, de esta forma, unapostador espabilado podría averiguar los números del generador y determinar las cartas sobre la mesa dejuego permitiendo engañar durante todo el tiempo al croupier (esto ocurre actualmente). Problemassimilares pueden encontrarse en criptografía, donde las claves privadas a menudo se crean mediante unode estos generadores. Este tipo de problemas se evita mediante el empleo de un generador criptográficoseguro de números seudoaleatorios.

Algoritmo no determinístico

En Ciencias de la computación, un algoritmo no determinístico es un algoritmo que con la misma

entrada ofrece muchos posibles resultados. No se puede saber de antemano cuál será el resultado de laejecución de un algoritmo no determinístico.

Uso

En la teoría estándar de la computación la definición de algoritmo deja en claro que de por sí unalgoritmo es detenninístico.

Sin embargo, los algoritmos no determinísticos emplean modelos de computación tales como la Máquinade Turing probabilística, que no son determinísticos. Se considera entonces que los algoritmos nodeterminísticos son un caso especial.

Convirtiendo algoritmos no determinísticos en determinísticos

Una forma de simular algoritmos no determinísticos N mediante el empleo de otros deterministícos Dpuede realizarse tratando los estados de N como estados de D. Esto significa que D puede tracear todaslas posibilidades y trayectorias de ejecución del algoritmo N.

Otra posibilidad es emplear algoritmos de generación de números aleatorios que consisten en perturbarlos estados mediante el establecimiento de todas las posibilidades mediante un generador de númerosaleatorios. El resultado es un algoritmo determinístico probabilístico.

Algoritmo divide y vencerás

En la cultura popular, divide y vencerás hace referencia a un refrán que implica resolver un problemadifícil, dividiéndolo en partes más simples tantas veces como sea necesario, hasta que la resolución de laspartes se torna obvia. La solución del problema principal se construye con las soluciones encontradas.

En las ciencias de la computación, el término divide y vencerás (DYV) hace referencia a uno de los másimportantes paradigmas de diseño algorítmico. El método está basado en la resolución recursiva de unproblema dividiéndolo en dos o más subproblemas de igual tipo o similar. El proceso continúa hasta queéstos llegan a ser lo suficientemente sencillos como para que se resuelvan directamente. Al final, lassoluciones a cada uno de los subproblemas se combinan para dar una solución al problema original. Estatécnica es la base de los algoritmos eficientes para casi cualquier tipo de problema como, por ejemplo,algoritmos de ordenamiento (quicksort, mergesort, entre muchos otros) y la transformada discreta deFourier.

Sin embargo, este tipo de algoritmos también se pueden implementar como un algoritmo no recursivoque almacene las soluciones parciales en una estructura de datos explícita, como puede ser una pila, cola,o cola con prioridad. Esta aproximación da mayor libertad al diseñador, de forma que se pueda escogerqué subproblema es el que se va a resolver a continuación, lo que puede ser importante en el caso de usartécnicas como Ramificación y acotación o de optimización.

Ventajas

Resolución de problemas complejos

Este modelo algorítmico es una herramienta potente para solucionar problemas complejos, tales como elclásico juego de las torres de Hanoi. Todo lo que necesita este algoritmo es dividir el problema ensubproblemas más sencillos, y éstos en otros más sencillos hasta llegar a unos subproblemas sencillos(también llamados casos base). Una vez ahí, se resuelven y se combinan los subproblemas en ordeninverso a su inicio. Cómo dividir los problemas es, a menudo, la parte más compleja del algoritmo. Poreso, en muchos problemas, el modelo sólo ofrece la solución más sencilla, no la mejor.

Eficiencia del algoritmo

Normalmente, esta técnica proporciona una forma natural de diseñar algoritmos eficientes. Por ejemplo,si el trabajo de dividir el problema y de combinar las soluciones parciales es proporcional al tamaño delproblema (n); además, hay un número limitado p de subproblemas de tamaño aproximadamente igual an/p en cada etapa; y por último, los casos base requieren un tiempo constante (O (l)); entonces elalgoritmo divide y vencerás tiene por cota superior asintótica a O(n log n). Esta cota es la que tienen losalgoritmos divide y vencerás que solucionan problemas tales como ordenar y la transformada discreta deFourier. Ambos procedimientos reducen su complejidad, anteriormente definida por O (n2). Para terminar,cabe destacar que existen otros enfoques y métodos que mejoran estas cotas.

Paralelismo

Este tipo de algoritmos se adapta de forma natural a la ejecución en entornos multiprocesador,especialmente en sistemas de memoria compartida donde la comunicación de datos entre losprocesadores no necesita ser planeada por adelantado, por lo que subproblemas distintos se puedenejecutar en procesadores distintos.

Acceso a memoria

Los algoritmos que siguen el paradigma Divide y vencerás, tienden naturalmente a hacer un uso eficientede las memorias caches. La razón es que una vez que un subproblema es lo suficientemente pequeño, él ytodos sus subproblemas se pueden, en principio, solucionar dentro de esa caché, sin tener acceso a lamemoria principal, que es del orden de decenas de veces más lenta. Un algoritmo diseñado paraaprovechar la memoria caché de esta manera se llama modelo cache-olvidadiza, olvidadiza porque nocontiene el tamaño de la memoria como parámetro explícito. Por otra parte, estos algoritmos se puedendiseñar para muchos problemas importantes, tales como ordenación, la multiplicación de matrices, demanera que se haga un uso óptimo de la caché. En contraste, el acercamiento tradicional para explotar lacaché es hacer bloques, de esta forma, el problema se divide explícitamente en las partes de tamañosapropiados para que se pueda utilizar al caché de forma óptima, pero solamente cuando el algoritmo esmejorado para el tamaño específico de la caché de una máquina particular.

Desventajas

La principal desventaja de este método es su lentitud en la repetición del proceso recursivo: los gastosindirectos de las llamadas recursivas a la resolución de los subproblemas, junto con el hecho de tener quealmacenar la pila de llamadas (el estado en cada punto en la repetición), pueden empeorar cualquiermejora hasta entonces lograda. Esta tarea, sin embargo, depende del estilo de la implementación: concasos base lo suficientemente grandes, se reducen los gastos indirectos de la repetición de las llamadas.

Otra desventaja o inconveniente importante, es la dificultad o incluso inconveniencia de aplicar elmétodo a situaciones en las que la solución al problema general no se deriva de la suma directa y simplede los subproblemas (partes). Esto se presenta por ejemplo cuando son relevantes las interacciones oefectos mutuos entre los subproblemas, lo que genera nuevos subproblemas, al considerar cada una deestas interacciones, incrementando exponencialmente el número de subproblemas a considerar, alincrementarse la complejidad de la situación general y de sus componentes.

De modo similar, el algoritmo puede no ser aplicable cuando las interacciones no son predecibles depreciso.

Metaheurística

Una metaheurística es un método heurístico para resolver un tipo de problema computacional general,

usando los parámetros dados por el usuario sobre unos procedimientos genéricos y abstractos de unamanera que se espera eficiente. Normalmente, estos procedimientos son heurísticos. El nombre combinael prefijo griego "meta" ("más allá", aquí con el sentido de "nivel superior") y "heurístico" (de eupicrceiv,heuriskein, "encontrar").

Las metaheurísticas generalmente se aplican a problemas que no tienen un algoritmo o heurísticaespecífica que dé una solución satisfactoria; o bien cuando no es posible implementar ese métodoóptimo. La mayoría de las metaheurísticas tienen como objetivo los problemas de optimizacióncombinatoria, pero por supuesto, se pueden aplicar a cualquier problema que se pueda reformular entérminos heurísticos, por ejemplo en resolución de ecuaciones booleanas.

Las metaheurísticas no son la panacea y suelen ser menos eficientes que las heurísticas específicas, envarios órdenes de magnitud, en problemas que aceptan este tipo de heurísticas crudas.

Conceptos generales y nomenclatura

El objetivo de la optimización combinatoria es encontrar un objeto matemático finito (por ejemplo, unvector de bits o permutación) que maximice (o minimice, dependiendo del problema) una funciónespecificada por el usuario de la metaheurística. A estos objetos se les suele llamar estados, y al conjuntode todos los estados candidatos se le llama espacio de búsqueda. La naturaleza de los estados y delespacio de búsqueda son usualmente específicos del problema.

La función a optimizar se le llama función objetivo, y se da al usuario como un procedimiento caja-negraque evalúa el estado actual o la función. Dependiendo de la metaheurística, el usuario puede tener quedar otras funciones caja-negra que produzcan un nuevo estado, generan variantes del estado actual, elijanun estado entre varios, aporten valores máximos o mínimos para la función objetivo en un conjunto deestados, y en ese estilo.

Algunas metaheurísticas mantienen en cada instante de ejecución un único estado actual, y lo cambianen cada iteración por uno nuevo. Este paso básico se conoce como transición de estado, movimiento oactualización del estado. El movimiento es colina arriba o colina abajo dependiendo de si los valoresque da la función objetivo se incrementa o se decrementa. El nuevo estado puede estar construido desdela nada por un generador de estados dado por el usuario. Alternativamente, el nuevo estado puedederivar del estado actual por un mutador proporcionado por el usuario; en este caso, el nuevo estado seconoce como vecino del estado actual. Generadores y mutadores son habitualmente procedimientosprobabilísticos. El conjunto de todos los nuevos estados dados por el mutador es el vecindario del estadoactual.

Metaheurísticas más sofisticadas mantienen, en vez de un único estado actual, un conjunto de variosestados candidato. Así, el paso básico añade o elimina estados de este conjunto. En este caso, losprocedimientos dados por el usuario seleccionan estados para ser descartados, y generan nuevos estadosa añadir. El último estado puede ser generado como combinación o cruce de dos o más estados delconjunto.

Una metaheurística puede guardar información del óptimo actual, escogiendo el estado óptimo entretodos los óptimos actuales obtenidos en varias etapas del algoritmo.

Dado que el número de candidatos puede ser muy grande, normalmente, las metaheurísticas estándiseñadas de manera que puedan ser interrumpidas por un tiempo máximo especificado por el usuario. Sino se interrumpen, algunas metaheurísticas exactas examinaran todos los candidatos, y usarán métodosheurísticos sólo para escoger el orden de la enumeración; de hecho, siempre devolverán un óptimo real,si el tiempo máximo es lo suficientemente grande. En cambio, otras metaheurísticas dan sólo una garantía

probabilística pobre de poder alcanzar el óptimo, de manera que cuando el tiempo máximo se aproxima ainfinito, la probabilidad de examinar cada candidato tiende a 1.

Metaheurísticas comunes

Algunas metaheurísticas muy conocidas son

• Optimización aleatoria• Búsqueda local• Algoritmos voraces y Ascensión de colinas• Ascensión de colinas con reinicialización aleatoria• Búsqueda primero el mejor• Enfriamiento simulado• Optimización basada en colonias de hormigas• Algoritmos de Enjambre• Búsqueda Tabú• Algoritmos Genéticos• Algoritmos Meméticos GRASP• Meta-RaPS• Algoritmos Multiarranque• Inteligencia enjambre• Búsqueda por difusión estocástica• Optimización extrema• Scatter Search y Path Relinking

Hay un número enorme de variables e híbridos propuestos, y muchas más aplicaciones de lasmetaheurísticas a problemas específicos se han probado. Esta es un campo en investigación, con un grannúmero de publicaciones en revistas, un gran número de investigadores y usuarios, además de un grannúmero de aplicaciones.

Programación dinámica (computación)

En la Informática, la programación dinámica es un método para reducir el tiempo de ejecución de unalgoritmo mediante la utilización de subproblemas superpuestos y subestructuras óptimas, como sedescribe a continuación.

El matemático Richard Bellman inventó la programación dinámica en 1953.

Introducción

Una subestructura óptima significa que soluciones óptimas de subproblemas pueden ser usadas paraencontrar las soluciones óptimas del problema en su conjunto. Por ejemplo, el camino más corto entredos vértices de un grato se puede encontrar calculando primero el camino más corto al objetivo desdetodos los vértices adyacentes al de partida, y después usando estas soluciones para elegir el mejor caminode todos ellos. En general, se pueden resolver problemas con subestructuras óptimas siguiendo estos trespasos:

1. Dividir el problema en subproblemas más pequeños.2. Resolver estos problemas de manera óptima usando este proceso de tres pasos

recursivamente.3. Usar estas soluciones óptimas para construir una solución óptima al problema original.

Los subproblemas se resuelven a su vez dividiéndolos ellos mismos en subproblemas más pequeños

hasta que se alcance el caso fácil, donde la solución al problema es trivial.

En resumen, la programación dinámica hace uso de:

• Subproblemas superpuestos• Subestructuras óptimas• Memorización

La programación dinámica toma normalmente uno de los dos siguientes enfoques:

• Top-down: El problema se divide en subproblemas, y estos subproblemas se resuelvenrecordando las soluciones en caso de que sean necesarias nuevamente. Es una combinaciónde memorización y recursión,

• Bottom-up: Todos los subproblemas que puedan ser necesarios se resuelven dé antemano ydespués son usados para resolver las soluciones a problemas mayores. Este enfoque esligeramente mejor en consumo de espacio y llamadas a funciones, pero a veces resulta pocointuitivo encontrar todos los subproblemas necesarios para resolver un problema dado.

Principio de optimalidad

Cuando hablamos de optimizar nos referimos a buscar la mejor solución de entre muchas alternativasposibles. Dicho proceso de optimización puede ser visto como una secuencia de decisiones que nosproporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cual es ladecisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental yse resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz.

A menudo, aunque no sea posible aplicar la estrategia voraz, se cumple el principio de optimalidad deBellman que dicta que «dada una secuencia óptima de decisiones, toda subsecuencia de ella es, a su vez,óptima». En este caso sigue siendo posible el ir tomando decisiones elementales, en la confianza de quela combinación de ellas seguirá siendo óptima, pero será entonces necesario explorar muchas secuenciasde decisiones para dar con la correcta, siendo aquí donde interviene la programación dinámica.

Contemplar un problema como una secuencia de decisiones equivale a dividirlo en subproblemas máspequeños y por lo tanto más fáciles de resolver como hacemos en Divide y Vencerás, técnica similar a lade Programación Dinámica. La programación dinámica se aplica cuando la subdivisión de un problemaconduce a:

• Una enorme cantidad de subproblemas.• Subproblemas cuyas soluciones parciales se solapan.• Grupos de subproblemas de muy distinta complejidad.

Ejercicios resueltos con Programación Dinámica

Ejecución de n tareas en tiempo mínimo en un sistema de dos procesadores A y B• Programas en disco• Problema de los sellos con programación dinámica• Problema de la mochila con programación dinámica• Problema del producto de una secuencia de matrices con programación dinámica• Problema de las monedas con programación dinámica• Camino de coste mínimo entre dos nodos de un grafo dirigido• Problema de la división de peso• Problema de las vacas con programación dinámica• Problema del Cambio de Palabra Programación Dinámica en JAVA

Ramificación y poda

El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y Acotación) esuna variante del Backtracking mejorado sustancialmente. El término (del inglés, Branch and Bound) seaplica mayoritariamente para resolver cuestiones o problemas de optimización.

La técnica de Ramificación y poda se suele interpretar como un árbol de soluciones, donde cada ramanos lleva a una posible solución posterior a la actual. La característica de esta técnica con respecto a otrasanteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ramificación lassoluciones dadas ya no están siendo óptimas, para «podar» esa rama del árbol y no continuarmalgastando recursos y procesos en casos que se alejan de la solución óptima.

Descripción General

Nuestra meta será encontrar el valor mínimo de una función f(x) (un ejemplo puede ser el coste demanufacturación de un determinado producto) donde fijamos x rangos sobre un determinado conjunto Sde posibles soluciones. Un procedimiento de ramificación y poda requiere dos herramientas.

La primera es la de un procedimiento de expansión, que dado un conjunto fijo S de candidatos, devuelvedos o más conjuntos más pequeños S1 , S2 , ... , Sn cuya unión cubre S. Nótese que el mínimo de f(x)sobre S es min { V1, V2, ... } donde cada vi, es el mínimo de f(x) sin Si. Este paso es llamado ramificación;como su aplicación es recursiva, esta definirá una estructura de Árbol (estructura de datos) cuyos nodosserán subconjuntos de S.

La idea clave del algoritmo de ramificación y poda es: si la menor rama para algún árbol nodo (conjuntode candidatos) A es mayor que la rama padre para otro nodo B, entonces A debe ser descartada conseguridad de la búsqueda. Este paso es llamado poda, y usualmente es implementado manteniendo unavariable (programación) global m que graba el mínimo nodo padre visto entre todas las subregionesexaminadas hasta entonces. Cualquier nodo cuyo nodo hijo es mayor que m puede ser descartado. Larecursión para cuando el conjunto candidato S es reducido a un solo elemento, o también cuando el nodopadre para el conjunto S coincide con el nodo hijo. De cualquier forma, cualquier elemento de S va a serel mínimo de una función sin S.

Pseudocódigo

El pseudocódigo del algoritmo de Ramificación y poda es el siguiente:

Función RyP {P = Hijos(x,k)mientras (no vacio(P))

x(k) = extraer(P)si esFactible(x,k) y G(x,k) < óptimo

si esSolucion(x)Almacenar(x)

sinoRyP(x,k+l)

}

Donde:

• G(x) es la función de estimación del algoritmo.• P es la pila de posibles soluciones.• esFactible es la función que considera si la propuesta es válida.• esSolución es la función que comprueba si se satisface el objetivo.• óptimo es el valor de la función a optimizar evaluado sobre la mejor solución encontrada

hasta el momento. .• NOTA: Usamos un menor que (<) para los problemas de minimización y un mayor que (>)

para problemas de maximización.

Subdivisión Efectiva

La eficiencia de este método depende fundamentalmente del procedimiento de expansión de nodos, o dela estimación de los nodos padres e hijos. Es mejo elegir un método de expansión que provea que no sesolapen los subconjuntos para ahorrarnos problemas de duplicación de ramas.

Idealmente, el procedimiento se para cuando todos los nodos del árbol de búsqueda están podados oresueltos. En ese punto, todas las subregiones no podadas, tendrán un nodo padre e hijo iguales a unafunción global mínima. En la practica el procedimiento a menudo termina, cuando finaliza un tiempodado, hasta el punto que el mínimo de nodos hijos y el máximo de nodos padres sobe todas las seccionesno podadas, definen un rango de valores que contienen el mínimo global. Alternativamente, sin superarun tiempo restringido, el algoritmo debe terminar cuando un criterio de error, tal que (max-min)/(max+min), cae bajo un valor especifico.

La eficiencia del método depende especialmente de la efectividad de los algoritmos de ramificación ypoda usados. Una mala elección puede llevarnos a una repetida ramificación, sin poda, hasta que lassubregiones se conviertan en muy pequeñas. En ese caso el método seria reducido a una exhaustivaenumeración del dominio, que es a menudo impracticablemente larga. No hay un algoritmo de podauniversal que trabaje para todos los problemas, pero existe una pequeña esperanza de que alguna vez seencuentre alguno. Hasta entonces necesitaremos implementar cada uno por separado para cada aplicacióninformática, con el algoritmo de ramificación y poda especialmente diseñados para él.

Los métodos de ramificación y poda deben ser clasificados acorde a los métodos de poda, y acorde a lasmaneras de creación/clasificación de los árboles de búsqueda.

La estrategia de diseño de ramificación y poda, es muy similar al de vuelta atrás (backtracking), donde elestado del árbol es usado para resolver un problema. Las diferencias son que el método de ramificación ypoda no nos limitan a ninguna forma particular de obtener un árbol transverso, y es usado solamente paraproblemas de optimización. Este método naturalmente lleva a una forma de implementación paralela ydistribuida, como podemos ver por ejemplo en el Problema del Viajante de Comercio.

Estrategias de Poda

Nuestro objetivo principal será eliminar aquellos nodos que no lleven a soluciones buenas. Podemosutilizar dos estrategias básicas. Supongamos un problema de maximización donde se han recorrido variosnodos i=l,….,n. estimando para cada uno la cota superior CS(xi) e inferior CI(xi).Vamos a trabajar sobre un problema donde se quiere maximizar el valor (si fuese un problema deminimización entonces se aplicaría la estrategia equivalente).

Estrategia 1

Si a partir de un nodo xi se puede obtener una solución válida, entonces se podrá podar dicho nodo si lacota superior CS(xi) es menor o igual que la cota inferior CI(xj) para algún nodo j generado en el árbol.

Por ejemplo: Supongamos el problema de la mochila, el cual se va a desarrollar en la sección deejemplos, donde utilizamos un árbol binario. Entonces:

Si a partir de xi se puede encontrar un beneficio máximo de CS(xi) = 4 y a partir de Xj, se tiene aseguradoun beneficio mínimo de CI(xj) = 5, esto nos llevará a la conclusión de que se puede podar el nodo xi sinque perdamos ninguna posible solución óptima.

Estrategia 2

Si se obtiene una posible solución válida para el problema con un beneficio Bj, entonces se podrán podaraquellos nodos x¡ cuya cota superior CS(xi) sea menor o igual que el beneficio que se puede obtener Bj(este proceso sería similar para la cota inferior).

Estrategias de Ramificación

Como se comenta en la introducción de éste apartado, la expansión del árbol con las distintas estrategiasestá condicionada por la búsqueda de la solución óptima. Debido a esto todos los nodos de un niveldeben ser expandidos antes de alcanzar un nuevo nivel, cosa que es lógica ya que para poder elegir larama del árbol que va a ser explorada, se deben conocer todas las ramas posibles.

Todos estos nodos que se van generando y que no han sido explorados se almacenan en lo que sedenomina Lista de Nodos Vivos (a partir de ahora LNV), nodos pendientes de expandir por el algoritmo.

La LNV contiene todos los nodos que han sido generados pero que no han sido explorados todavía.Según como estén almacenados los nodos en la Lista (estructura de datos), el recorrido del árbol será deuno u otro tipo, dando lugar a las tres estrategias que se detallan a continuación.

Estrategia FIFO

En la estrategia FIFO (First In First Out), la LNV será una Cola (estructura de datos), dando lugar a unrecorrido en anchura del árbol.

En la figura 1 se puede observar que se comienza introduciendo en la LNV el nodo A. Sacarnos el nodode la cola y se expande generando los nodos B y C que son introducidos en la LNV. Seguidamente sesaca el primer nodo que es el B y se vuelve a expandir generando los nodos D y E que se introducen en laLNV. Este proceso se repite mientras que quede algún elemento en la cola.

Estrategia LIFO

En la estrategia LIFO (Last In First Out), la LNV será una Pila (estructura de datos), produciendo un

Lista de nodos vivos

recorrido en profundidad del árbol.

En la figura 2 se muestra el orden de generación de los nodos con una estrategia LIFO. El proceso que sesigue en la LNV es similar al de la estrategia FIFO, pero en lugar de utilizar una cola, se utiliza una pila.

En la figura 2 se muestra el orden de generación de los nodos con una estrategia LIFO. El proceso que sesigue en la LNV es similar al de la estrategia FIFO, pero en lugar de utilizar una cola, se utiliza una pila.

Estrategia de Menor Coste o LC

Al utilizar las estrategias FIFO y LIFO se realiza lo que se denomina una búsqueda "a ciegas", ya queexpanden sin tener en cuenta los beneficios que se pueden alcanzar desde cada nodo. Si la expansión serealizase en función de los beneficios que cada nodo reporta (con una "visión de futuro"), se podríaconseguir en la mayoría de los casos una mejora sustancial.

Es así como nace la estrategia de Menor Coste o LC (Least cost), selecciona para expandir entre todoslos nodos de la LNV aquel que tenga mayor beneficio (o menor coste). Por tanto, ya no estamoshablando de un avance "a ciegas".

Esto nos puede llevar a la situación de que varios nodos puedan ser expandidos al mismo tiempo. Dedarse el caso, es necesario disponer de un mecanismo que solucione este conflicto:

•

-Estrategia LC-FIFO: Elige de la LNV el nodo que tenga mayor beneficio y en caso de empate seescoge el primero que se introdujo.

-Estrategia LC-LIFO: Elige de la LNV el nodo que tenga mayor beneficio y en caso de empate seescoge el último que se introdujo.

Ramificación y Poda "Relajado

Un variante del método de ramificación y poda más eficiente se puede obtener "relajando" el problema,es decir, eliminando algunas de las restricciones para hacerlo más permisivo.

Cualquier solución válida del problema original será solución válida para el problema "relajado", pero notiene por qué ocurrir al contrario. Si conseguimos resolver esta versión del problema de forma óptima,entonces si la solución obtenida es válida para el problema original, esto querrá decir que es óptimatambién para dicho problema.

La verdadera utilidad de este proceso reside en la utilización de un método eficiente que nos resuelva elproblema relajado. Uno de los métodos más conocidos es el de Ramificación y Corte (Branch and Cut(versión inglesa)).

Ramificación y Corte

Ramificación y corte es un método de optimización combinacional para resolver problemas de enteroslineales, que son problemas de programación lineal donde algunas o todas las incógnitas estánrestringidas a valores enteros. Se trata de un híbrido de ramificación y poda con métodos de planos decorte.

Este método resuelve programas lineales sin restricciones enteras usando algoritmos regularessimplificados. Cuando se obtiene una solución óptima que tiene un valor no entero para una variable queha de ser entera, el algoritmo de planos de corte se usa para encontrar una restricción lineal más adelanteque sea satisfecha por todos los puntos factibles enteros, pero violados por la solución fraccional actual.Si se encuentra esa desigualdad, se añade al programa lineal, de tal forma que resolverla nos llevará a unasolución diferente que esperamos que sea "menos fraccional". Este proceso se repite hasta que ó bien, seencuentra una solución entera (que podemos demostrar que es óptima), ó bien no se encuentran másplanos de corte.

En este punto comienza la parte del algoritmo de ramificación y poda. Este problema se divide en dosversiones: una con restricción adicional en que la variable es más grande o igual que el siguiente enteromayor que el resultado intermedio, y uno donde la variable es menor o igual que el siguiente enteromenor. De esta forma se introducen nuevas variables en las bases de acuerdo al número de variablesbásicas que no son enteros en la solución intermedia pero son enteros de acuerdo a las restriccionesoriginales. Los nuevos programas lineales se resuelven usando un método simplificado y después elproceso repetido hasta que una solución satisfaga todas las restricciones enteras.

Durante el proceso de ramificación y poda, los planos de corte se pueden separar más adelante y puedenser o cortes globales válidos para todas las soluciones enteras factibles, o cortes locales que sonsatisfechos por todas las soluciones llenando todas las ramas de la restricción del subárbol deramificación y poda actual.

Aplicaciones en el ámbito general

Esta técnica es usada por un gran número de problemas NP-hard, tales como:

• Problema de la mochila.• Programación lineal.• Programación no lineal.

• Problema del viajante.

• Problema de asignación cuadrática (Versión Inglesa).

• Problema de máxima satisfacibilidad (Versión Inglesa).

• Búsqueda del vecino más cercano (Versión Inglesa).

• Análisis del ruido falso.

Ejemplos de problemas usando Ramificación y poda;

• Resolución de un sudoku utilizando Ramificación y poda• Resolución de un laberinto utilizando Ramificación y poda• Arquimedex.com Ejemplol de ramificar y acotar• Programación Entera Ejemplo2

Vuelta Atrás

"Vuelta atrás", (Backtracking) es una estrategia para encontrar soluciones a problemas que satisfacenrestricciones. El término "backtrack" fue acuñado por primera vez por el matemático estadounidense D,11. Lehmer en los años 1950s.

Concepto

En su forma básica, la idea de backtracking se asemeja a un recorrido en profundidad dentro de un grafodirigido. El grafo en cuestión suele ser un árbol, o por lo menos no contiene ciclos. Sea cual sea suestructura, existe sólo implícitamente. El objetivo del recorrido es encontrar soluciones para algúnproblema. Esto se consigue construyendo soluciones parciales a medida que progresa el recorrido; estassoluciones parciales limitan las regiones en las que se puede encontrar una solución completa. Elrecorrido tiene éxito si, procediendo de esta forma, se puede definir por completo una solución. En estecaso el algoritmo puede bien detenerse (si lo único que se necesita es una solución del problema) o bienseguir buscando soluciones alternativas (si deseamos examinarlas todas). Por otra parte, el recorrido notiene éxito si en alguna etapa la solución parcial construida hasta el momento no se puede completar. Ental caso, el recorrido vuelve atrás exactamente igual que en un recorrido en profundidad, eliminandosobre la marcha los elementos que se hubieran añadido en cada fase. Cuando vuelve a un nodo que tieneuno o más vecinos sin explorar, prosigue el recorrido de una solución.

'

Algoritmo de Backtrackingproc Backtracking (↕X[1 . .. i ]: TSolución, ↑ok: B)variables L: ListaComponentesinicio

si EsSolución(X) entonces ok CIERTOen otro caso ok

FALSOL=Candidatos(X)mientras ¬ ok ^ ¬ Vacía(L) hacerX [i+l] Cabeza(L); L Resto(L)Backtracking (X, ok)Fin mientras

finsifin

Podemos visualizar el funcionamiento de una técnica de backtracking como la exploración enprofundidad de un grafo. Cada vértice del grafo es un posible estado de la solución del problema. Cadaarco del grafo representa la transición entre dos estados de la solución (i.e., la toma de una decisión).

Típicamente el tamaño de este grafo será inmenso, por lo que no existirá de manera explícita. En cadamomento sólo tenemos en una estructura los nodos que van desde el estado inicial al estado actual. Sicada secuencia de decisiones distinta da lugar a un estado diferente, el grafo es un árbol (el árbol deestados).

Enfoque

Los problemas que deben satisfacer un determinado tipo de restricciones son problemas completos,donde el orden de los elementos de la solución no importa. Estos problemas consisten en un conjunto (olista) de variables a la que a cada una se le debe asignar un valor sujeto a las restricciones del problema.La técnica va creando todas las posibles combinaciones de elementos para obtener una solución. Suprincipal virtud es que en la mayoría de las implementaciones se puede evitar combinaciones,estableciendo funciones de acotación (o poda) reduciendo el tiempo de ejecución.

Vuelta atrás está muy relacionada con la búsqueda combinatoria.

Diseño e implementación

Esencialmente, la idea es encontrar la mejor combinación posible en un momento determinado, por eso,se dice que este tipo de algoritmo es una búsqueda en profundidad. Durante la búsqueda, si se encuentrauna alternativa incorrecta, la búsqueda retrocede hasta el paso anterior y toma la siguiente alternativa.Cuando se han terminado las posibilidades, se vuelve a la elección anterior y se toma la siguiente opción(hijo [si nos referimos a un árbol]). Si no hay más alternativas la búsqueda falla. De esta manera, se creaun árbol implícito, en el que cada nodo es un estado de la solución (solución parcial en el caso de nodosinteriores o solución total en el caso de los nodos hoja).

Normalmente, se suele implementar este tipo de algoritmos como un procedimiento recursivo. Así, encada llamada al procedimiento se toma una variable y se le asignan todos los valores posibles, llamando asu vez al procedimiento para cada uno de los nuevos estados. La diferencia con la búsqueda enprofundidad es que se suelen diseñar funciones de cota, de forma que no se generen algunos estados si novan a conducir a ninguna solución, o a una solución peor de la que ya se tiene. De esta forma se ahorraespacio en memoria y tiempo de ejecución.

Aplicaciones

Vuelta atrás se usa en la implementación de los lenguajes de programación tales como Lenguaje deprogramación Planner y Prolog. Además, se usa en los análisis sintácticos de los compiladores. Su uso eninteligencia artificial ha sido muy importante, dando lugar a nuevos tipos de búsquedas como el Aestrella.

Applets para simular distintos algoritmos de Backtracking

Desde Internet se pueden acceder a una serie de links a páginas que disponen de applets Java con los quepodremos comprobar de una manera clara, rápida y visual el funcionamiento de diversos algoritmos deBacktracking.

http://tracer.lsi.upc.es/visual-grab-and-go/knapsack.html

http://\\rww.hbmeyer.de/backtrack/backtren.htm

http://decsai.ugr.es/~ta_ii/algoritmos/seccion.php?id=teoria&subseccion=applets/kef5_8

http://vww.heimetli.ch/ffh/sudoku.html

Branch & Bound (Ramificación y poda)

Este método busca una solución como en el método de backtracking, pero cada solución tiene asociadoun costo y la solución que se busca es una de mínimo costo llamada óptima. Además de ramificar unasolución padre (branch) en hijos se trata de eliminar de consideración aquellos hijos cuyos descendientestienen un costo que supera al óptimo buscado acotando el costo de los descendientes del hijo (bound). Laforma de acotar es un arte que depende de cada problema. La acotación reduce el tiempo de búsqueda dela solución óptima al "podar" (pruning) los subarboles de descendientes costosos.

Algoritmo genético

Un algoritmo es una serie de pasos organizados que describe el proceso que se debe seguir, para darsolución a un problema específico.

En los años 1970, de la mano de John Henry Holland, surgió una de las líneas más prometedoras de lainteligencia artificial, la de los algoritmos genéticos. Son llamados así porque se inspiran en la evoluciónbiológica y su base genético-molecular. Estos algoritmos hacen evolucionar una población de individuossometiéndola a acciones aleatorias semejantes a las que actúan en la evolución biológica (mutaciones yrecombinaciones genéticas), así como también a una Selección de acuerdo con algún criterio, en funcióndel cual se decide cuáles son los individuos más adaptados, que sobreviven, y cuáles los menos aptos,que son descartados. También es denominado algoritmos evolutivos, e incluye las estrategias deevolución, la programación evolutiva y la programación genética. Dentro de esta última se han logradoavances curiosos:

En 1999, por primera vez en la historia, se concedió una patente a un invento no realizado directamentepor un ser humano: se trata de una antena de forma extraña, pero que funciona perfectamente en lascondiciones a las que estaba destinada. No hay, sin embargo, nada injusto en el hecho de que el autor delalgoritmo genético del que salió la forma de la antena se haya atribuido la autoría de la patente, pues élescribió el programa e ideó el criterio de selección que condujo al diseño patentado.

Un algoritmo genético es un método de búsqueda dirigida basada en probabilidad. Bajo una condiciónmuy débil (que el algoritmo mantenga elitismo, es decir, guarde siempre al mejor elemento de lapoblación sin hacerle ningún cambio) se puede demostrar que el algoritmo converge en probabilidad alóptimo. En otras palabras, al aumentar el número de iteraciones, la probabilidad de tener el óptimo en lapoblación tiende a 1 (uno).

Funcionamiento

Los algoritmos genéticos establecen una analogía entre el conjunto de soluciones de un problema,llamado fenotipo, y el conjunto de individuos de una población natural, codificando la información decada solución en una cadena, generalmente binaria, llamada cromosoma. Los símbolos que forman lacadena son llamados los genes. Cuando la representación de los cromosomas se hace con cadenas dedígitos binarios se le conoce como genotipo. Los cromosomas evolucionan a través de iteraciones,llamadas generaciones. En cada generación, los cromosomas son evaluados usando alguna medida de

aptitud. Las siguientes generaciones (nuevos cromosomas), llamada descendencia, se formanutilizando dos operadores, de cruzamiento y de mutación.

Cuándo usar estos algoritmos

Los algoritmos genéticos son de probada eficacia en caso de querer calcular funciones no derivables(o de der ivación muy comple ja ) aunque su uso es pos ib le con cua lquie rfunc ión . Deben tenerse en cuenta también las siguientes consideraciones:

• Si la función a optimizar tiene muchos máximos/mínimos locales se requerirán másiteraciones del algoritmo para "asegurar" el máximo/mínimo global.

• Si la función a optimizar contiene varios puntos muy cercanos en valor al óptimo,solamente podemos "asegurar" que encontraremos uno de ellos (no necesariamente el óptimo).

Funcionamiento de un algoritmo genético básico

Un algoritmo genético puede presentar diversas variaciones, dependiendo de cómo se aplican losoperadores genéticos (cruzamiento, mutación), de cómo se realiza la selección y de cómo se decide elreemplazo de los individuos para formar la nueva población. En general, el pseudocódigo consiste delos siguientes pasos:

Algoritmo genético i: inicialización, f(X): evaluación, ?: condición de término, Se: selección,Cr: cruzamiento, Mu: mutación, Re: reemplazo, X*: mejor solución.

• Inicialización: Se genera aleatoriamente la población inicial, que está constituida por un conjunto decromosomas los cuales representan las posibles soluciones del problema. En caso de no hacerloaleatoriamente, es importante garantizar que dentro de la población inicial, se tenga la diversidadestructural de estas soluciones para tener una representación de la mayor parte de la poblaciónposible o al menos evitar la convergencia prematura.

• Evaluación: A cada uno de los cromosomas de esta población se aplicará la función de aptitud parasaber qué tan "buena" es la solución que se está codificando.

• Condición de término El AG se deberá detener cuando se alcance la solución óptima, pero éstageneralmente se desconoce, por lo que se deben utilizar otros criterios de detención.Normalmente se usan dos criterios: correr el AG un número máximo de iteraciones(generaciones) o detenerlo cuando no haya cambios en la población. Mientras no se cumpla lacondición de término se hace lo siguiente:• Selección Después de saber la aptitud de cada cromosoma se procede a elegir los

cromosomas que serán cruzados en la siguiente generación. Los cromosomas con mejor aptitudtienen mayor probabilidad de ser seleccionados.

Cruzamiento El cruzamiento es el principal operador genético, representa la reproducción sexual,opera sobre dos cromosomas a la vez para generar dos descendientes donde se combinan lascaracterísticas de ambos cromosomas padres.

Mutación modifica al azar parte del cromosoma de los individuos, y permite alcanzar zonasdel espacio de búsqueda que no estaban cubiertas por los individuos de la población actual.

Reemplazo una vez aplicados los operadores genéticos, se seleccionan los mejoresindividuos para conformar la población de la generación siguiente

Aplicaciones

Diseño automatizado, incluyendo investigación en diseño de materiales y diseño multiobjetivo decomponentes automovilísticos: mejor comportamiento ante choques, ahorros de peso, mejora deaerodinámica, etc.

Diseño automatizado de equipamiento industrial. Diseño automatizado de sistemas de comercio en el sector financiero. Construcción de árboles filogenéticos. Optimización de carga de contenedores. Diseño de sistemas de distribución de aguas. Diseño de topologías de circuitos impresos. Diseño de topologías de redes computacionales. En Teoría de juegos, resolución de equilibrios. Análisis de expresión de genes. Aprendizaje de comportamiento de robots. Aprendizaje de reglas de Lógica difusa. Análisis lingüístico, incluyendo inducción gramática, y otros aspectos de Procesamiento de

lenguajes naturales, tales como eliminación de ambigüedad de sentido. Infraestructura de redes de comunicaciones móviles. Optimización de estructuras moleculares. Planificación de producción multicriteria. Predicción. Optimización de sistemas de compresión de datos, por ejemplo, usando wavelets. Predicción de Plegamiento de proteínas. Optimización de Layout. Predicción de estructura de RNA. En bioinformática, Alineamiento múltiple de secuencias. Aplicaciones en planificación de procesos industriales, incluyendo planificación job-shop. Selección óptima de modelos matemáticos para la descripción de sistemas biológicos. Manejo de residuos sólidos. Ingeniería de software. Construcción de horarios en grandes universidades, evitando conflictos de clases. Problema del viajante. Hallazgo de errores en programas. Optimización de producción y distribución de energía eléctrica.