Fuerza Bruta
Este tipo de algoritmos resuelven el problema con la estrategia mas obvia de solución que no siempre es la mejor según el número de operaciones que se requiere.
Un algoritmo de fuerza bruta para encontrar el divisor de un número natural n consistiría en enumerar todos los enteros desde 1 hasta n, chequeando si cada uno de ellos divide n sin generar resto. Otro ejemplo de búsqueda por fuerza bruta, en este caso para solucionar el problema de las ocho reinas (posicionar ocho reinas en el tablero de ajedrez de forma que ninguna de ellas ataque al resto), consistiría en examinar todas las combinaciones de posición para las 8 reinas (en total 64! /56! = 178.462.987.637.760 posiciones diferentes), comprobando en cada una de ellas si las reinas se atacan mutuamente.
Algoritmos Voraces
Estos tipos de algoritmos ofrecen una solución rápida, sin llegar a la solución completa; solucionan la opción de la solución(solución local) que tenga un costo menor en la etapa de solución en la que se encuentran, sin considerar se esa opción es parte de una solución óptima para el problema completo (solución global).
Funcionamiento:
El algoritmo escoge en cada paso al mejor elemento x conjunto de C, posible, conocido como el elemento más prometedor. Se elimina ese elemento del conjunto de candidatos, comprueba si la inclusión de este elemento en el conjunto de elementos seleccionados S unión de 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 el elemento. 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.
Programación Dinámica
Cuando un problema presenta una subestructura óptima osea cuando la solución óptima de un problema, se obtiene a partir de las soluciones óptimas de sus subproblemas más sencillos y luego utilizando esas subsoluciones para resolver problemas incrementalmente difíciles. (problema grande, lo dividimos en partes)
Programación Lineal
Para resolver un problema utilizando este método se plantea una serie de inecuaciones y luego se busca maximizar o minimizar las variables, respetando las inecuaciones.
Muchos problemas pueden plantearse en la forma de un conjunto de inecuaciones, para luego resolverlas utilizando un algoritmo genérico,
Ejemplo: el método simplex.
Es un método numérico para optimización de problemas libres multidimensionales, perteneciente a la clase más general de algoritmos de búsqueda. El que permite encontrar una solución óptima en un problema de maximización o minimización, buscando en los vértices del polígono.
En ambos casos, el método usa el concepto de un símplex, que es un politopo de
N + 1 vértices en
N dimensiones: un segmento de línea sobre una línea, un triángulo sobre un plano, un tetraedro en un espacio de tres dimensiones y así sucesivamente.
Divide y Reinarás
Ésta metodología divide las instancias del problema a resolver en instancias cada vez más pequeñas usualmente en forma recursiva, hasta llegar a la instancia en la que el problema es soluble o trivial con unas pocas instrucciones (los algoritmos de búsqueda binaria son claros ejemplos)
EJEMPLO de Búsqueda Binaria:
La búsqueda binaria sólo se puede implementar si el arreglo está ordenado. La idea consiste en ir dividiendo el arreglo en mitades. Por ejemplo supongamos que tenemos este vector:
int vector[10] =
{2,4,6,8,10,12,14,16,18,20};
La clave que queremos buscar es
6. El algoritmo funciona de la siguiente manera
- Se determinan un índice arriba y un índice abajo,
Iarriba=0 e Iabajo=9 respectivamente.
- Se determina un indice central,
Icentro = (Iarriba + Iabajo)/2, en este caso quedaría Icentro = 4.
- Evaluamos si
vector[Icentro] es igual a la clave de búsqueda, si es igual ya encontramos la clave y devolvemos Icentro.
- Si son distintos, evaluamos si
vector[Icentro] es mayor o menos que la clave, como el arreglo está ordenado al hacer esto ya podemos descartar una mitad del arreglo asegurándonos que en esa mitad no está la clave que buscamos. En nuestro caso vector[Icentro] = 4 < 6, entonces la parte del arreglo vector[0...4] ya puede descartarse.
- Reasignamos
Iarriba o Iabajo para obtener la nueva parte del arreglo en donde queremos buscar. Iarriba, queda igual ya que sigue siendo el tope. Iabajo lo tenemos subir hasta 5, entonces quedaría Iarriba = 9, Iabajo = 5. Y volvemos al paso 2.
Si la clave no fuese encontrada en algún momento Iabajo > Iarriba, con un while vamos a controlar esta condición para salir del ciclo en tal caso y devolver -1 (clave no encontrada).
Hagamos modificaciones al código de búsqueda lineal para implementar una función de búsqueda binaria.
//Busqueda binaria
//en un arreglo.
#include <iostream>
using std::cout;
using std::cin;
using std::endl;
void mostrarArreglo(const int[], int); //prototipo de funcion que
recibe un arreglo constanteint busquedaBinaria(const int[], int, int); //arreglo, tamano, clave
void ordenarArreglo(int[], int); //prototipo que modifica y ordena el
arreglovoid intercambiar(int&, int&); //prototipo, intercambia
los valores de dos elementosint main()
{
int clave =0;
const int tamano = 15;
int arreglo[tamano] = {25,17,13,16,41,32,12,115,95,84,54,63,78,21,10};
//ordenamos el arreglo para que funcione la busquedaBinaria
ordenarArreglo(arreglo,tamano);
cout << "Elementos del arreglo: " << endl;
mostrarArreglo(arreglo,tamano);
cout << "Indique un valor a buscar y se le devolvera el indice: " << endl;
cin >> clave;
cout<< "Su valor se encuentra en arreglo["<<busquedaBinaria(arreglo,tamano,clave)<<"]" << endl;
cout << "Fin del programa :)" << endl;
return 0;
}//fin de main
void mostrarArreglo(const int arreglo[], int tamano)
{
for (int i = 0 ; i < tamano ; i++)
cout << "arreglo[" << i << "]=" << arreglo[i] << endl;
}
int busquedaBinaria(const int arreglo[], int tamano, int clave)
{
int Iarriba = tamano-1;
int Iabajo = 0;
int Icentro;
while (Iabajo <= Iarriba)
{
Icentro = (Iarriba + Iabajo)/2;
if (arreglo[Icentro] == clave)
return Icentro;
else
if (clave < arreglo[Icentro])
Iarriba=Icentro-1;
else
Iabajo=Icentro+1;
}
return -1;
}
void ordenarArreglo(int arreglo[], int tamano)
{
for (int i = 0; i< tamano -1 ; i++)
for (int j = 0; j< tamano -1 ; j++)
if (arreglo[j] > arreglo[j+1])
intercambiar(arreglo[j],arreglo[j+1]);
}
void intercambiar(int &a, int &b)
{
int tmp = b;
b = a;
a = tmp;
}
Búsqueda y Enumeración
Muchos problemas(por ejemplo un juego de ajedrez) pueden modelarse con grafos y resolverse a partir de un algoritmo de exploración del grafo. Tal algoritmo especificará las reglas para moverse en el grafo en búsqueda de la solución al problema.
EJEMPLO:
Disponemos de un tablero de ajedrez de tamaño NxN, y se trata de colocar en él N reinas de manera que no se amenacen según las normas del ajedrez.
proc NReinas (↕[1 . . . i ]: TSolución, ↓N: N, ↑ok: B)
variables j : N
inicio
si i=N entonces ok=CIERTO
en otro caso
ok=FALSO
j=1
mientras ¬ok ^ (j≤N) hacer
si EsFactible (R, j) entonces
R[i + 1]= j
NReinas (R, N, ok)
finsi
j=j+1
finmientras
finsi
fin
*********
func EsFactible (↓R[1 . . . i ]: TSolución, ↓j : N): B
variables factible: B
inicio
factible=CIERTO
k=1
mientras factible ^ (k≤i) hacer
si (j=R[k])\/(i+1−k= |j−R[k]|) entonces
factible=FALSO
finsi
k=k+1
finmientras
devolver factible
fin
Algoritmos Heurísticos
El propósito de estos algoritmos no es necesariamente encontrar una solución final al problema, sino encontrar una solución aproximada cuando el tiempo o los recursos necesarios para encontrar la solución perfecta son exclusivos.
En cualquier problema de búsqueda donde hay
b opciones en cada nodo y una profundidad
d al nodo objetivo, un algoritmo de búsqueda ingenuo deberá buscar potencialmente entre
bd nodos antes de encontrar la solución. Las heurísticas mejoran la eficiencia de los algoritmos de búsqueda reduciendo el factor de ramificación de
b a (idealmente) una constante
b * .
Aunque cualquier heurística admisible devolverá una respuesta óptima, una heurística que devuelve un factor de ramificación más bajo es computacionalmente más eficiente para el problema en particular. Puede demostrarse que una heurística
h2(n) es mejor que otra
h1(n), si
h2(n) domina
h1(n), esto quiere decir que
h1(n) < h2(n) para todo
n.
http://es.wikipedia.org/wiki/Vuelta_Atr%C3%A1s
http://es.wikipedia.org/wiki/Heur%C3%ADstica_%28inform%C3%A1tica%29
http://codigomaldito.blogspot.com/2005/11/busqueda-binaria.html
- matriz de distancias.
- distancia del enlace entre el nodo i y el nodo j.
(partiendo de que la raíz tenga índice cero). Este método tiene como ventajas el tener almacenados los datos de forma más compacta y por tener una forma más rápida y eficiente de localizar los datos en particular durante un preoden transversal. Sin embargo, desperdicia mucho espacio en memoria.