05.24.09
Métodos de ordenación: Bubble Sort
El método de intercambio directo, conocido coloquialmente con el nombre de la burbuja, es el más utilizado por los estudiantes principiantes de computación, por su fácil comprensión y programación. Pero es preciso señalar que es probablemente el método más ineficiente.
El método de intercambio directo puede trabajar de dos maneras diferentes.
-
llevando los elementos más pequeños hacia la parte izquierda del arreglo.
- llevando los elementos más grandes hacia la parte derecha del mismo.
12.18.08
Mi Sudoku por Backtracking
Os dejo el enlace a un artículo en el cual se trabaja el sudoku y se ofrece mi solución personal así como el código fuente necesario para resolver sudokus con su correspondiente trabajo de investigación en cuanto a cual es el algoritmo óptimo y tiempos de ejecución.
12.09.08
Ramificación y Poda
El método de diseño de algoritmos Ramificación y poda (también llamado Ramificación y Acotación) es una variante del Backtracking mejorado sustancialmente y se aplica 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 rama nos lleva a una posible solución posterior a la actual. La característica de esta técnica con respecto a otras anteriores (y a la que debe su nombre) es que el algoritmo se encarga de detectar en qué ramificación las soluciones dadas ya no están siendo óptimas, para «podar» esa rama del árbol y no continuar malgastando recursos y procesos.
Mas informació, ejemplos y código fuente
12.08.08
Algoritmos del Ajedrez por Backtracking
He recopilado 3 algoritmos clásicos de programación informática durante la carrera, relacionados con el ajedrez, estos son:
- El problema del Alfil y el Peón
- Recorridos del Rey
- El problema de las N – Reinas
Podemos encontrar la explicación, la solución y el codigo fuente en este enlace a un fantástico artículo sobre Algoritmos del Ajedrez por Backtracking
El Algoritmo del Rio Congo
El problema del Rio Congo
- A lo largo del río Congo hay E embarcaderos a los que nombramos con los números enteros 1, 2, . . . , E.
- Es posible ir en canoa desde un embarcadero a cualquiera de los dos siguientes en la dirección de la corriente.
- No se puede navegar contra corriente, ni tampoco ir más allá del segundo embarcadero sin efectuar escala alguna.
- Problema: Dada una función de ponderación que asigna un coste (positivo) a cada arco, calcular el camino de menor coste del primer al último embarcadero y su coste.
Implementación
Para resolver el problema se lee el grafo de un fichero que se pasa como parámetro al ejecutable. Este fichero debe contener una matriz de adyacencia donde el valor será el coste de la arista que une dos nodos, tal y como se puede ver:
Podemos encontrar el articulo completo y la descarga del código fuente en este enlace.
