martes, 18 de mayo de 2010
El artículo de Ford y de Fulkerson (1956) con el problema de flujo máximo estableció el famoso teorema del flujo máximo - mínimo corte.
Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad es un corte mínimo proporciona el flujo máximo en la red.
Propiedad: v (f) =f(S, S’)-f(S', S).
El corte con la capacidad mas pequeña se denomina corte mínimo.
Cualquier nodo compatible desde el nodo fuente al nodo destino no puede exceder la capacidad de ningún corte. Por lo tanto, el flujo máximo a través de la red esta limitado por la capacidad del corte mínimo.
Para cualquier red del flujo máximo desde el nodo fuente al nodo destino es igual a la capacidad del corte destino.
A partir de este teorema el problema de encontrar el flujo máximo en una red se traduce en encontrar las capacidades de todos los cortes y elegir la minima capacidad. Por otra parte dado el valor máximo de flujo no especifica como este flujo es distribuido a tarves de los cortes que separan el nodo fuente del destino 2n-2.
Ejemplo:
En un grafo dirigido un conjunto de flechas S tal que todo camino dirigido de s a t contiene una flecha de S, decimos que S separa a s de t.
Un corte separa a s de t y un conjunto de flechas que separa a s de t es un corte.
En un grafo dirigido el número mínimo de flechas que separa a s de t es igual al máximo número de caminos dirigidos disjuntos de flechas que unen s con t.
NOTA: que si dos caminos dirigidos no tienen flechas comunes pueden tener vértices comunes. En cambio si dos caminos no tienen vértices comunes no tienen tampoco flechas comunes.
Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
Corte: Un corte define una serie de arcos cuya supresión de la red causa una interrupción completa del flujo entre el origen y el destino. La capacidad de corte es igual a la suma de las capacidades de los arcos asociados. Entre todos los cortes posibles en la red , el corte con la menor capacidad es un corte mínimo proporciona el flujo máximo en la red.
Propiedad: v (f) =f(S, S’)-f(S', S).
El corte con la capacidad mas pequeña se denomina corte mínimo.
Cualquier nodo compatible desde el nodo fuente al nodo destino no puede exceder la capacidad de ningún corte. Por lo tanto, el flujo máximo a través de la red esta limitado por la capacidad del corte mínimo.
Para cualquier red del flujo máximo desde el nodo fuente al nodo destino es igual a la capacidad del corte destino.
A partir de este teorema el problema de encontrar el flujo máximo en una red se traduce en encontrar las capacidades de todos los cortes y elegir la minima capacidad. Por otra parte dado el valor máximo de flujo no especifica como este flujo es distribuido a tarves de los cortes que separan el nodo fuente del destino 2n-2.
Ejemplo:
En un grafo dirigido un conjunto de flechas S tal que todo camino dirigido de s a t contiene una flecha de S, decimos que S separa a s de t.
Un corte separa a s de t y un conjunto de flechas que separa a s de t es un corte.
En un grafo dirigido el número mínimo de flechas que separa a s de t es igual al máximo número de caminos dirigidos disjuntos de flechas que unen s con t.
NOTA: que si dos caminos dirigidos no tienen flechas comunes pueden tener vértices comunes. En cambio si dos caminos no tienen vértices comunes no tienen tampoco flechas comunes.
Este algoritmo se puede usar para resolver modelos de: transporte de mercancías (logística de aprovisionamiento y distribución), flujo de gases y líquidos por tuberías, componentes o piezas en líneas de montaje, corriente en redes eléctricas, paquetes de información en redes de comunicaciones, tráfico ferroviario, sistema de regadíos, etc.
Teorema de Ford-Fulkerson (1962): En cualquier red, el flujo máximo que fluye de la fuente al destino es igual a la capacidad del corte mínimo que separa a la fuente del destino.
domingo, 16 de mayo de 2010
Proyecto #5 Problemas de Corte Minimo
Definición de corte minimo
En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedan dos partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra.
Definición de capacidad de un corte
Se llama capacidad de un corte a la suma:
S Capacidad (v,w) ; v Є V1 , w ЄV2
V1 es la parte que contiene a la fuente
V2 es la parte que contiene al sumidero
Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F; es decir:
Si ЄP S JЄP Cij ³ S i F ai
La notación Si : Significa la suma sobre todos los vértices i
Demostración: observe Sj ЄP S iЄP Cji = Sj ЄP S iЄP F ij
Pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las de i, j Є P
Ahora
S i F ai= Sj ЄP Sj Fji -Sj ЄP Sj
=Sj ЄP SiЄP Fji +Sj ЄP SiЄP Fji- =Sj ЄP SiЄP Fji
=Sj ЄP SiЄP Fji -Sj ЄP SiЄP Fji- £Sj ЄP SiЄP Fji£ Sj ЄP SiЄP Cji
El corte minimal nos da la minima capacidad del corte efectuado en el grafo.
Para el cálculo de la capacidad del corte minimal no se tienen en cuenta las capacidades de las aristas del corte cuya dirección sea contraria al sentido de flujo.
TEOREMA DEL FLUJO MÁXIMO Y EL CORTE MÍNIMO
Sea F un flujo en G y sea (P, P) un corte en G si la igualdad se cumple entonces el flujo es máximo y el corte es mínimo si y solo si:
1) FI J = CI J para i ЄP, J Є P
2) Fij =0 para i Є P, J Є P
El valor del flujo maximal de una red es igual a la capacidad del corte minimal que se puede aplicar a la red.
Se puede obtener, por tanto el corte minimal de una red, conociendo el flujo maximal de la red obtenido mediante la aplicación del algoritmo anteriormente definido.
En lo que respecta a las redes, un corte es un conjunto de corte en el cual quedan dos partes disjuntas del conjunto de vértices, V1 y V2 que, situados en la red, dejan la fuente en una de ellas y al sumidero en la otra.
Definición de capacidad de un corte
Se llama capacidad de un corte a la suma:
S Capacidad (v,w) ; v Є V1 , w ЄV2
V1 es la parte que contiene a la fuente
V2 es la parte que contiene al sumidero
Sea F un flujo en G y sea (P, P) un corte en G. Entonces la capacidad de (p, p) es mayor o igual que el valor de F; es decir:
Si ЄP S JЄP Cij ³ S i F ai
La notación Si : Significa la suma sobre todos los vértices i
Demostración: observe Sj ЄP S iЄP Cji = Sj ЄP S iЄP F ij
Pues cada lado de la ecuación es simplemente la suma de Fij sobre todas las de i, j Є P
Ahora
S i F ai= Sj ЄP Sj Fji -Sj ЄP Sj
=Sj ЄP SiЄP Fji +Sj ЄP SiЄP Fji- =Sj ЄP SiЄP Fji
=Sj ЄP SiЄP Fji -Sj ЄP SiЄP Fji- £Sj ЄP SiЄP Fji£ Sj ЄP SiЄP Cji
El corte minimal nos da la minima capacidad del corte efectuado en el grafo.
Para el cálculo de la capacidad del corte minimal no se tienen en cuenta las capacidades de las aristas del corte cuya dirección sea contraria al sentido de flujo.
TEOREMA DEL FLUJO MÁXIMO Y EL CORTE MÍNIMO
Sea F un flujo en G y sea (P, P) un corte en G si la igualdad se cumple entonces el flujo es máximo y el corte es mínimo si y solo si:
1) FI J = CI J para i ЄP, J Є P
2) Fij =0 para i Є P, J Є P
El valor del flujo maximal de una red es igual a la capacidad del corte minimal que se puede aplicar a la red.
Se puede obtener, por tanto el corte minimal de una red, conociendo el flujo maximal de la red obtenido mediante la aplicación del algoritmo anteriormente definido.
domingo, 25 de abril de 2010
PROYECTO 4
Listas doblemente enlazadas
Este es el tema que elegimos para nuestra presentación.
Mis compañeras Danya A. Peralta Cano y Arely Quintanilla trabajamos
muy bien en equipo por que todas apotamos, ya que primero buscamos la
información sobre el tema seleccionado, lo checamos para saber de que
informa el tema, después cada quien dijo sus opiniones, para hacer la
presentación. Todas trabajamos para que nos quedara con calidad.
En que aspectos:
Estoy bien : Que aunque creí que el tema era difícil lo supe identificar
para después entenderlo bien.
Debo mejorar: Creo que siempre hay que mejorar cada día y
poner todo nuestra dedicación, es lo que yo hago en cada proyecto que he
entregado. Y acepto cada opinión.
Ayudo o me Ayudan: Las dos pociones son las que escojo por que el trabajo
en equipo es para eso, ya que en algunas ocasiones yo aporto; en otrs mis
compañeras pero todo es con es por igual nadie hace de más y nadie de menos
por que es un trabajo en equipo. Y mis compañeras y yo lo tratamos de hacer
bien.
Este es el tema que elegimos para nuestra presentación.
Mis compañeras Danya A. Peralta Cano y Arely Quintanilla trabajamos
muy bien en equipo por que todas apotamos, ya que primero buscamos la
información sobre el tema seleccionado, lo checamos para saber de que
informa el tema, después cada quien dijo sus opiniones, para hacer la
presentación. Todas trabajamos para que nos quedara con calidad.
En que aspectos:
Estoy bien : Que aunque creí que el tema era difícil lo supe identificar
para después entenderlo bien.
Debo mejorar: Creo que siempre hay que mejorar cada día y
poner todo nuestra dedicación, es lo que yo hago en cada proyecto que he
entregado. Y acepto cada opinión.
Ayudo o me Ayudan: Las dos pociones son las que escojo por que el trabajo
en equipo es para eso, ya que en algunas ocasiones yo aporto; en otrs mis
compañeras pero todo es con es por igual nadie hace de más y nadie de menos
por que es un trabajo en equipo. Y mis compañeras y yo lo tratamos de hacer
bien.
http://arelyquintanilla.blogspot.com/
domingo, 14 de marzo de 2010
Torres de Hanói
Introducción
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Las Torres de Hanói es un rompecabezas o juego matemático inventado en 1883 por el matemático francés Éduard Lucas.Este solitario se trata de un juego de ocho discos de radio creciente que se apilan insertándose en una de las tres estacas de un tablero. El objetivo del juego es crear la pila en otra de las estacas siguiendo unas ciertas reglas. El problema es muy conocido en la ciencia de la computación y aparece en muchos libros de texto como introducción a la teoría de algoritmos.
En su forma más tradicional, consiste en tres varillas verticales. En una de las varillas se apila un número indeterminado de discos (elaborados de madera) que determinará la complejidad de la solución, por regla general se consideran ocho discos. Los discos se apilan sobre una varilla en tamaño decreciente. No hay dos discos iguales, y todos ellos están apilados de mayor a menor radio en una de las varillas, quedando las otras dos varillas vacantes. El juego consiste en pasar todos los discos de la varilla ocupada (es decir la que posee la torre) a una de las otras varillas vacantes. Para realizar este objetivo, es necesario seguir tres simples reglas:
1. Sólo se puede mover un disco cada vez.
2. Un disco de mayor tamaño no puede descansar sobre uno más pequeño que él mismo.
3. Sólo puedes desplazar el disco que se encuentre arriba en cada varilla.
Existen diversas formas de realizar la solución final, todas ellas siguiendo estrategias diversas.
Pseudocódigo
Pseudocodigo Algoritmo Recursivo
hanoi(n, origen, destino, auxiliar)
si n=1
entonces
mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}
si no
//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino
//{mover n-1 discos de la torre auxiliar a la torre destino}
llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}
fin
fin
Pseudocódigo Algoritmo Iterativo
//los argumentos origen, destino y axuliar son variables representando las tres torres del problema original (pueden ser estructuras o simplemente el nombre de cada torre, en este caso solo representan el nombre de las torres por tanto, se asume que son de tipo texto).
//n es el numero de discos
//pilaN, pilaO, pilaD y pilaA son estructuras de tipo PILA
//tope es una variable de tipo entero.
//varaux es una variable de tipo texto (en este caso por que las torres son representadas unicamente por su nombre, es decir, esta variable debe ser del mismo tipo que origen, destino y auxiliar)
//bandera es una variable de tipo boleano
Solución Iterativa(n, origen, destino, auxiliar)
hacer tope=0 y bandera = falso
repetir mientras (n>0) y (bandera=falso)
repetir mientras (N>1)
//se guardan en las pilas los valores actuales de los parametros
tope=tope+1
pilaN[tope]=n
pilaO[tope]=origen
pilaD[tope]=destio
pilaA[tope]=auxiliar
n=n-1
varaux=destino
destino=auxiliar
auxiliar = varaux
Fin //fin de repetir mientras (N>1)
mover disco de origen a destino
bandera=verdadero
si tope >0 entonces //quiere decir que las pilas no estan vacias
n=pilaN[tope]
origen=pilaO[tope]
destino=pilaD[tope]
auxiliar=pilaA[tope]
tope=tope-1
mover disco de origen a destino
n=n-1
varaux=origen
origen=auxiliar
auxiliar=varaux
bandera=falso
Fin //fin de si tope >0 entonces
Fin //fin de repetir mientras (n>0) y (band=falso)
Fin //fin del metodo
hanoi(n, origen, destino, auxiliar)
si n=1
entonces
mover un disco de la torre origen a la torre destino //{solucion del metodo recursivo}
si no
//{mover n-1 discos de la torre origen a la torre auxiliar}
llamar hanoi(n-1, origen, auxiliar, destino) //{llamada recursiva}
Mover un disco de la torre origen a la torre destino
//{mover n-1 discos de la torre auxiliar a la torre destino}
llamar metodo hanoi(n-1, axuliar, destino, origen) //{llamada recursiva}
fin
fin
Pseudocódigo Algoritmo Iterativo
//los argumentos origen, destino y axuliar son variables representando las tres torres del problema original (pueden ser estructuras o simplemente el nombre de cada torre, en este caso solo representan el nombre de las torres por tanto, se asume que son de tipo texto).
//n es el numero de discos
//pilaN, pilaO, pilaD y pilaA son estructuras de tipo PILA
//tope es una variable de tipo entero.
//varaux es una variable de tipo texto (en este caso por que las torres son representadas unicamente por su nombre, es decir, esta variable debe ser del mismo tipo que origen, destino y auxiliar)
//bandera es una variable de tipo boleano
Solución Iterativa(n, origen, destino, auxiliar)
hacer tope=0 y bandera = falso
repetir mientras (n>0) y (bandera=falso)
repetir mientras (N>1)
//se guardan en las pilas los valores actuales de los parametros
tope=tope+1
pilaN[tope]=n
pilaO[tope]=origen
pilaD[tope]=destio
pilaA[tope]=auxiliar
n=n-1
varaux=destino
destino=auxiliar
auxiliar = varaux
Fin //fin de repetir mientras (N>1)
mover disco de origen a destino
bandera=verdadero
si tope >0 entonces //quiere decir que las pilas no estan vacias
n=pilaN[tope]
origen=pilaO[tope]
destino=pilaD[tope]
auxiliar=pilaA[tope]
tope=tope-1
mover disco de origen a destino
n=n-1
varaux=origen
origen=auxiliar
auxiliar=varaux
bandera=falso
Fin //fin de si tope >0 entonces
Fin //fin de repetir mientras (n>0) y (band=falso)
Fin //fin del metodo
Algoritmo recursivo
La Torre de Hanoi suele aparecer como ejemplo para ilustrar el concepto de recursión en los cursos de programación de computadoras, ya que existe un algoritmo recursivo sorprendentemente simple que lo resuelve (por si alguien no lo sabe, un algoritmo es recursivo si se llama a sí mismo en alguno de sus pasos). Supongamos que queremos trasladar los ocho discos del poste A al poste C. Como el disco 8 siempre está abajo del todo, la única forma de hacerlo es trasladar primero la torre de siete discos 1...7 al poste B. Entonces podremos llevar el disco 8 de A a C, y para terminar tendremos que trasladar de nuevo la torre 1...7, ahora de B a C.
Pero los discos 1...7 forman una torre totalmente similar a la inicial, así que en dos de los tres pasos anteriores nos enfrentamos con un problema análogo al original. De hecho, puede resolverse de la misma forma, trasladando ahora la torre 1...6. Por ejemplo, el primer paso (trasladar la torre 1...7 de A a B) se puede descomponer en estos tres pasos.
Por supuesto, en dos de estos tres pasos nos volvemos a encontrar con el problema original, ahora con n = 6. El proceso no es infinito, ya que llega el momento en que una torre equivale a trasladar un solo disco (esto ocurre cuando la torre es de un solo disco, claro). En resumen, el algoritmo recursivo es el siguiente.
Algoritmo para trasladar la torre 1...n del poste X al poste Z, usando como auxiliar el poste Y.
1.-Si n = 1, lleva el disco 1 de X a Z y termina.
2.-Traslada la torre 1...n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z.
3.-Lleva el disco n de X a Z.
4.-Traslada la torre 1...n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X.
Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. En realidad, lo único que hace es especificar unos pasos inevitables. Por ejemplo, como vimos antes, para resolver el puzzle es obligatorio llevar el disco n de A a C, y para ello es obligatorio llevar antes la torre 1...n a B, etc. La secuencia de movimientos que produce este algoritmo es la única solución óptima (o sea, de longitud mínima) posible. El número de movimientos es M3(n) = 2n−1, como se puede demostrar fácilmente por inducción sobre el número de discos.
Se cumple para n = 1
M3(1) = 1 = 21−1.
Si se cumple para n, se cumple para d+1
Al ejecutarse el algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así queM3(n+1) = 2 × M3(n) + 1 = 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1.
Para n = 8 el número de movimientos es de 28−1 = 255. Para n = 64, de 264−1 = 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.
Los algoritmos recursivos funcionan bien con ordenadores, pero son difíciles de aplicar para un ser humano. Si intentas resolver la torre de ocho discos aplicando el método descrito es fácil que te pierdas a no ser que vayas tomando notas de por dónde vas. Incluso para los ordenadores los algoritmos recursivos suelen ser poco económicos, en el sentido de que consumen bastante memoria (y es que ellos también necesitan. La alternativa a los algoritmos recursivos son los iterativos, en los que no hay llamadas a sí mismo, sino uno o varios bucles. Muy a menudo no existe o no se conoce una alternativa iterativa para un algoritmo recursivo, y cuando sí se conoce, suele ser mucho más complicada que la versión recursiva. Sin embargo, en el caso de la Torre de Hanoi, existen varios algoritmos iterativos muy simples.
La Torre de Hanoi suele aparecer como ejemplo para ilustrar el concepto de recursión en los cursos de programación de computadoras, ya que existe un algoritmo recursivo sorprendentemente simple que lo resuelve (por si alguien no lo sabe, un algoritmo es recursivo si se llama a sí mismo en alguno de sus pasos). Supongamos que queremos trasladar los ocho discos del poste A al poste C. Como el disco 8 siempre está abajo del todo, la única forma de hacerlo es trasladar primero la torre de siete discos 1...7 al poste B. Entonces podremos llevar el disco 8 de A a C, y para terminar tendremos que trasladar de nuevo la torre 1...7, ahora de B a C.
Pero los discos 1...7 forman una torre totalmente similar a la inicial, así que en dos de los tres pasos anteriores nos enfrentamos con un problema análogo al original. De hecho, puede resolverse de la misma forma, trasladando ahora la torre 1...6. Por ejemplo, el primer paso (trasladar la torre 1...7 de A a B) se puede descomponer en estos tres pasos.
Por supuesto, en dos de estos tres pasos nos volvemos a encontrar con el problema original, ahora con n = 6. El proceso no es infinito, ya que llega el momento en que una torre equivale a trasladar un solo disco (esto ocurre cuando la torre es de un solo disco, claro). En resumen, el algoritmo recursivo es el siguiente.
Algoritmo para trasladar la torre 1...n del poste X al poste Z, usando como auxiliar el poste Y.
1.-Si n = 1, lleva el disco 1 de X a Z y termina.
2.-Traslada la torre 1...n−1 usando este mismo algoritmo, de X a Y, usando como auxiliar Z.
3.-Lleva el disco n de X a Z.
4.-Traslada la torre 1...n−1 usando este mismo algoritmo, de Y a Z, usando como auxiliar X.
Este algoritmo siempre me ha parecido sorprendente, parece más la definición de un problema que su resolución. En realidad, lo único que hace es especificar unos pasos inevitables. Por ejemplo, como vimos antes, para resolver el puzzle es obligatorio llevar el disco n de A a C, y para ello es obligatorio llevar antes la torre 1...n a B, etc. La secuencia de movimientos que produce este algoritmo es la única solución óptima (o sea, de longitud mínima) posible. El número de movimientos es M3(n) = 2n−1, como se puede demostrar fácilmente por inducción sobre el número de discos.
Se cumple para n = 1
M3(1) = 1 = 21−1.
Si se cumple para n, se cumple para d+1
Al ejecutarse el algoritmo para n+1 se llama a sí mismo dos veces para n, más un movimiento del disco n+1. Así queM3(n+1) = 2 × M3(n) + 1 = 2 × (2n−1) + 1 = 2n+1−2+1 = 2n+1−1.
Para n = 8 el número de movimientos es de 28−1 = 255. Para n = 64, de 264−1 = 18.446.744.073.709.551.615. Si los bramanes de Benarés cambiaran un disco de sitio cada segundo necesitarían más de quinientos ochenta mil millones de años para terminar su tarea, unas cuarenta veces la edad del Universo.
Los algoritmos recursivos funcionan bien con ordenadores, pero son difíciles de aplicar para un ser humano. Si intentas resolver la torre de ocho discos aplicando el método descrito es fácil que te pierdas a no ser que vayas tomando notas de por dónde vas. Incluso para los ordenadores los algoritmos recursivos suelen ser poco económicos, en el sentido de que consumen bastante memoria (y es que ellos también necesitan. La alternativa a los algoritmos recursivos son los iterativos, en los que no hay llamadas a sí mismo, sino uno o varios bucles. Muy a menudo no existe o no se conoce una alternativa iterativa para un algoritmo recursivo, y cuando sí se conoce, suele ser mucho más complicada que la versión recursiva. Sin embargo, en el caso de la Torre de Hanoi, existen varios algoritmos iterativos muy simples.
Algoritmos iterativos
Antes de buscar un algoritmo iterativo resaltemos de nuevo un detalle importante. Aunque estamos hablando de varios algoritmos, la solución óptima (la de menos movimientos, que como hemos visto antes, para n = 8 es de 255) es única. O sea, la serie de movimientos que resulta de aplicar un algoritmo (óptimo) cualquiera será siempre la misma.
Una observación clave para encontrar un algoritmo iterativo es que el disco más pequeño se mueve una vez sí, una vez no. El primer movimiento hay que hacerlo con el disco 1. Está claro que después de mover el disco 1 (en cualquier ocasión) se debe mover un disco distinto (si no queremos perder el tiempo moviendo el mismo disco varias veces). Este movimiento debe hacerse entre los dos postes que no contienen el disco 1. A continuación no nos quedan más que dos alternativas: deshacer el último movimiento, lo que no tiene sentido, o volver a mover el disco 1. Además, cuando le toque le toque el turno a un disco distinto de 1, el movimiento estará perfectamente determinado ya que sólo intervendrán dos postes, y entre dos postes sólo hay un movimiento posible. Así que sólo puede haber duda cuando hay que mover el disco menor. Se sale de esta duda respetando una cualquiera de las siguientes reglas.
Antes de buscar un algoritmo iterativo resaltemos de nuevo un detalle importante. Aunque estamos hablando de varios algoritmos, la solución óptima (la de menos movimientos, que como hemos visto antes, para n = 8 es de 255) es única. O sea, la serie de movimientos que resulta de aplicar un algoritmo (óptimo) cualquiera será siempre la misma.
Una observación clave para encontrar un algoritmo iterativo es que el disco más pequeño se mueve una vez sí, una vez no. El primer movimiento hay que hacerlo con el disco 1. Está claro que después de mover el disco 1 (en cualquier ocasión) se debe mover un disco distinto (si no queremos perder el tiempo moviendo el mismo disco varias veces). Este movimiento debe hacerse entre los dos postes que no contienen el disco 1. A continuación no nos quedan más que dos alternativas: deshacer el último movimiento, lo que no tiene sentido, o volver a mover el disco 1. Además, cuando le toque le toque el turno a un disco distinto de 1, el movimiento estará perfectamente determinado ya que sólo intervendrán dos postes, y entre dos postes sólo hay un movimiento posible. Así que sólo puede haber duda cuando hay que mover el disco menor. Se sale de esta duda respetando una cualquiera de las siguientes reglas.
-El disco pequeño se debe mover siempre cíclicamente en el mismo sentido: hacia la derecha (de A a B, de B a C y de C a A) o hacia la izquierda (de A a C, de C a B y de B a A), según el número de discos sea par o impar respectivamente.
-El disco pequeño se debe colocar siempre, bien sobre un disco de número par, bien como único disco en el poste de destino (C) si el número de discos es impar o en el otro (B) si es par.
Teniendo en cuenta la primera regla se construye un algoritmo descubierto por Peter Buneman y Leon Levy.
1.-Si n es par, mueve el disco 1 hacia la derecha. Si es impar, muévelo hacia la izquierda.
2.-Si todos los discos están en C, fin. Si no, mueve un disco que no sea el 1 y vuelve al paso 1.
Teniendo en cuenta la segunda regla, el algoritmo podría ser el siguiente.
1.-Si es posible, lleva el disco 1 sobre un disco de número par. Si no es posible, llévalo al poste B si n es par o a C si n es impar.
2.-Si todos los discos están en C, fin. Si no, mueve un disco que no sea el 1 y vuelve al paso 1.
Para hacer este algoritmo más fácil de aplicar se pueden pintar los discos pares e impares de dos colores distintos. Incluso se puede pintar la base en tres trozos, como se ve en el dibujo (es como si los trozos de base fueran los discos n+1, n+2 y n+3).
Con esta versión del rompecabezas el último algoritmo se puede redactar así:
Lleva el disco 1 sobre un disco (o trozo de base) que no sea de su mismo color.
-Si todos los discos están en C, fin. Si no, mueve un disco distinto de 1 y vuelve al paso 1.
- El disco más pequeño no es el único que no se coloca nunca sobre otro de distinto color,
en ningún momento hay dos discos del mismo color juntos.
Lleva el disco 1 sobre un disco (o trozo de base) que no sea de su mismo color.
-Si todos los discos están en C, fin. Si no, mueve un disco distinto de 1 y vuelve al paso 1.
- El disco más pequeño no es el único que no se coloca nunca sobre otro de distinto color,
en ningún momento hay dos discos del mismo color juntos.
viernes, 19 de febrero de 2010
Ejemplos
1.-Una persona desea buscar la página en donde se encuentra el telefóno de una de sus amigas llamada Sarla Garza entonces ella debe de introducir la primera letra de su nombre ``S´´ entonces en el diagrama de flujo obtendra que el número de su amiga se encuentra en la página 5.
2.-Una persona desea saber el nombre de alguien a quien busca pero solamente tiene su número el cual es 75146901 y al introducirlo en el diagrama nos podremos dar cuenta que su nombre aparecera en la página 3 y tal vez si usamos el primer diagrama sabremos como se llama esa persona que esta localizando.
2.-Una persona desea saber el nombre de alguien a quien busca pero solamente tiene su número el cual es 75146901 y al introducirlo en el diagrama nos podremos dar cuenta que su nombre aparecera en la página 3 y tal vez si usamos el primer diagrama sabremos como se llama esa persona que esta localizando.
Este es el segundo diagrama de flujo que realizamos Lucero Guzmán Cantú y Danya Peralta Cano que se refiere al primer problema: buscar un número en la guía telefónica.
De las 7 páginas que tiene la guía desidimos declarar variables de los números telefonicos para cada página, así en el momento de imprimir sabrá el número telefonico deseado o el nombre de la persona.
Algoritmo:
1.- Inicio.
2.- Declarar variable 1-7 páginas.
3.- capturar los datos.
4.- Páginas.
5.- Imprimir el número de páginas donde se encuentra el número deseado.
6.- Fin.
De las 7 páginas que tiene la guía desidimos declarar variables de los números telefonicos para cada página, así en el momento de imprimir sabrá el número telefonico deseado o el nombre de la persona.
Algoritmo:
1.- Inicio.
2.- Declarar variable 1-7 páginas.
3.- capturar los datos.
4.- Páginas.
5.- Imprimir el número de páginas donde se encuentra el número deseado.
6.- Fin.
Mi compañera Danya Peralta Cano y yo Lucero Guzmán Cantú decidimos escoger el problema número 1: Buscar un número en la guía tefónica.
Lo que pensamos fue en que buscara el nombre o apellido de la persona. Primero le asignamos páginas a cada grupo de letras del abecedario, para que así se facilitara al momento de insertar la inicial del nombre o apellido, después al imprimir aparecerá la página deseada.
Algoritmo del primer diagrama:
1.- Inicio.
2.- Declarar variable A-Z.
3.- Capturar datos.
4.- Imprimir número de página.
5.- Fin.
Lo que pensamos fue en que buscara el nombre o apellido de la persona. Primero le asignamos páginas a cada grupo de letras del abecedario, para que así se facilitara al momento de insertar la inicial del nombre o apellido, después al imprimir aparecerá la página deseada.
Algoritmo del primer diagrama:
1.- Inicio.
2.- Declarar variable A-Z.
3.- Capturar datos.
4.- Imprimir número de página.
5.- Fin.
miércoles, 17 de febrero de 2010
Suscribirse a:
Entradas (Atom)
