martes, 3 de enero de 2012
jueves, 14 de julio de 2011
Quicksort
Este video es un ejemplo del metodo de Ordenamiento "Quicksort" que vimos en clase.
Referencias: No pongo referencias de ninguna pagina porque este ejemplo lo vimos en clase.
Referencias: No pongo referencias de ninguna pagina porque este ejemplo lo vimos en clase.
Busqueda Tabú
Búsqueda Tabú
La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de búsqueda local mediante el uso de estructuras de memoria: una vez que una potencial solución es determinada, se la marca como "tabú" de modo que el algoritmo no vuelva a visitar esa posible solución.
Vimos en clase un ejemplo "El problema del Viajante", aqui les dejo la definicion y la explicacion de este problema que se puede resolver con busqueda Tabú.
Problema del Viajante
El problema del viajante (TSP), es comúnmente utilizado para mostrar la funcionalidad de la búsqueda tabú.
El TSP requiere buscar un orden en el cual viajar entre ciudades, tal que la distancia recorrida sea minimizada.
Por ejemplo, si las ciudades A y B están una al lado de la otra, mientras que la ciudad C está más lejos, la distancia total recorrida será más corta si las ciudades A y B son visitadas una después de la otra, antes de visitar C.
Como encontrar un orden óptimo para visitar las ciudades en el TSP es un problema NP-difícil. los métodos de aproximación basados en heurísticas son útiles para lograr la optimalidad.
La búsqueda tabú puede utilizarse para encontrar una solución satisfactoria para el TSP. Primero, la búsqueda tabú comienza con una solución inicial, que puede ser generada con el algoritmo del vecino más cercano.
Para crear nuevas soluciones, el orden en que dos ciudades son visitadas es intercambiado. La distancia total recorrida entre todas las ciudades es utilizada para juzgar cuanto mejor es una solución de otra. Para prevenir ciclos y para salir de los óptimos locales, una solución es agregada a la lista tabú si es que es aceptada en N*(x), el vecindario de soluciones.
Se continúan creando nuevas soluciones hasta que algún criterio de parada, como por ejemplo un número arbitrario de iteraciones, es encontrado.
Una vez que la búsqueda tabú se detiene, la mejor solución es aquella que cuya distancia total a recorrer entre las ciudades es la menor.
La búsqueda tabú es un método de optimización matemática, perteneciente a la clase de técnicas de búsqueda local. La búsqueda tabú aumenta el rendimiento del método de búsqueda local mediante el uso de estructuras de memoria: una vez que una potencial solución es determinada, se la marca como "tabú" de modo que el algoritmo no vuelva a visitar esa posible solución.
Vimos en clase un ejemplo "El problema del Viajante", aqui les dejo la definicion y la explicacion de este problema que se puede resolver con busqueda Tabú.
Problema del Viajante
El problema del viajante (TSP), es comúnmente utilizado para mostrar la funcionalidad de la búsqueda tabú.
El TSP requiere buscar un orden en el cual viajar entre ciudades, tal que la distancia recorrida sea minimizada.
Por ejemplo, si las ciudades A y B están una al lado de la otra, mientras que la ciudad C está más lejos, la distancia total recorrida será más corta si las ciudades A y B son visitadas una después de la otra, antes de visitar C.
Como encontrar un orden óptimo para visitar las ciudades en el TSP es un problema NP-difícil. los métodos de aproximación basados en heurísticas son útiles para lograr la optimalidad.
La búsqueda tabú puede utilizarse para encontrar una solución satisfactoria para el TSP. Primero, la búsqueda tabú comienza con una solución inicial, que puede ser generada con el algoritmo del vecino más cercano.
Para crear nuevas soluciones, el orden en que dos ciudades son visitadas es intercambiado. La distancia total recorrida entre todas las ciudades es utilizada para juzgar cuanto mejor es una solución de otra. Para prevenir ciclos y para salir de los óptimos locales, una solución es agregada a la lista tabú si es que es aceptada en N*(x), el vecindario de soluciones.
Se continúan creando nuevas soluciones hasta que algún criterio de parada, como por ejemplo un número arbitrario de iteraciones, es encontrado.
Una vez que la búsqueda tabú se detiene, la mejor solución es aquella que cuya distancia total a recorrer entre las ciudades es la menor.
miércoles, 13 de julio de 2011
Algoritmo de Prim
El Algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas.
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
Pseudocódigo de Algoritmo
// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL
// Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas del grafo
por cada u en V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
Añadir(cola,)
distancia[u]=0
mientras cola != 0 hacer
// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.
por cada v adyacente a 'u' hacer
si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces
padre[v] = u
distancia[v] = peso(u, v)
Actualizar(cola,)
Pasos para realizar el Algoritmo
1. Se marca un nodo cualquiera, este será el nodo de partida.
2. Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente (nodo de partida), y marcamos el otro nodo en el que índice.
3. Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.
4. El proceso termina cuando tenemos todos los nodos del grafo marcados
Codigo en C++
for(int i = 0; i < cn; i++) adyacencia[i][padre] = INF; // Encuentro la menor distancia entre las filas marcadas. // El nodo padre es la linea marcada y el nodo hijo es la columna del minimo. int min = INF; for(itVec = markedLines.begin(); itVec != markedLines.end(); itVec++) for(int i = 0; i < cn; i++) if(min > adyacencia[*itVec][i]){
min = adyacencia[*itVec][i];
padre = *itVec;
hijo = i;
}
arbol[padre][hijo] = min;
arbol[hijo][padre] = min;
} return arbol;
}
Referencias:
http://www.wikipedia.com
En otras palabras, el algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo.
Pseudocódigo de Algoritmo
// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL
// Encolamos, en una cola de prioridad donde la prioridad es la distancia, todas las parejas
por cada u en V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
Añadir(cola,
distancia[u]=0
mientras cola != 0 hacer
// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
u = extraer_minimo(cola) //devuelve el minimo y lo elimina de la cola.
por cada v adyacente a 'u' hacer
si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces
padre[v] = u
distancia[v] = peso(u, v)
Actualizar(cola,
Pasos para realizar el Algoritmo
1. Se marca un nodo cualquiera, este será el nodo de partida.
2. Seleccionamos la arista de menor valor incidente en el nodo marcado anteriormente (nodo de partida), y marcamos el otro nodo en el que índice.
3. Repetir el paso 2 siempre que la arista elegida enlace un nodo marcado y otro que no lo esté.
4. El proceso termina cuando tenemos todos los nodos del grafo marcados
Codigo en C++
// Declaraciones en el archivo .h
const int INF = 1000000;
int cn; //cantidad de nodos
vector< vector > ady; //matriz de adyacencia
// Devuelve la matriz de adyacencia del arbol minimo.
vector< vector > Grafo :: prim(){
// uso una copia de ady porque necesito eliminar columnas
vector< vector > adyacencia = this->ady;
vector< vector > arbol(cn);
vector markedLines;
vector :: iterator itVec;
// Inicializo las distancias del arbol en INF.
for(int i = 0; i < cn; i++) arbol[i] = vector (cn, INF);
int padre = 0;
int hijo = 0;
while(markedLines.size() + 1 < cn){ padre = hijo;
// Marco la fila y elimino la columna del nodo padre. markedLines.push_back(padre);
const int INF = 1000000;
int cn; //cantidad de nodos
vector< vector
// Marco la fila y elimino la columna del nodo padre. markedLines.push_back(padre);
}
Referencias:
http://www.wikipedia.com
Algoritmo Euclidiano
Hoy en clase vimos lo que es un Algoritmo euclideano, y la maestra nos dio una brebe explicacion de como este funciona.
Definicion:
Método para encontrar el máximo factor común de dos enteros. Se divide el número mayor entre el número menor. Se repite la división, utilizando el residuo como divisor, hasta que el residuo se convierte en cero. El último residuo diferente a cero es el máximo factor común de los dos enteros
La explicacion es asi:
A % B = c
56 % 35 = 21 -->56 - 1X35 (56/35)
35 % 21 = 14 -->35 - 1X21 (35/21)
21 % 14 = 7 -->21 - 1X14 (21/14)
14 % 7 = 0
Ahora en Codigo.
Consola
Definicion:
Método para encontrar el máximo factor común de dos enteros. Se divide el número mayor entre el número menor. Se repite la división, utilizando el residuo como divisor, hasta que el residuo se convierte en cero. El último residuo diferente a cero es el máximo factor común de los dos enteros
La explicacion es asi:
A % B = c
56 % 35 = 21 -->56 - 1X35 (56/35)
35 % 21 = 14 -->35 - 1X21 (35/21)
21 % 14 = 7 -->21 - 1X14 (21/14)
14 % 7 = 0
Ahora en Codigo.
using namespace std;
int mcd(int x , int y){
int t;
x = (x < 0) ? -x:x;
int t;
x = (x < 0) ? -x:x;
y = (y < 0) ? -y:y;
t = (x < y) ? x : y;
while ( (x % t) || (y % t))
--t;
return t;
}
int euc(int x,int y){
return (!y) ? x : euc(y,x%y);
}
int main()
{
int x,y;
cout << "x: ";
cin >> x;
cout << "y: ";
cout << "y: ";
cin >> y;
cout << "MCD: " << mcd(x,y) << endl;
cout << "MCD: " << mcd(x,y) << endl;
cout << "MCD (euclides): " << euc(x,y) << endl;
system("PAUSE");
}
Consola
martes, 12 de julio de 2011
Tarea N°4
Arreglos, tablas y listas
Tarea 4
referencias:
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/arreglos.pdf
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/lindin.pdf
Tarea 4
referencias:
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/arreglos.pdf
http://elisa.dyndns-web.com/~elisa/teaching/comp/alg/pdf/lindin.pdf
Suscribirse a:
Entradas (Atom)