Descripción detallada de los algoritmos desarrollados - Joel-Araya/Proyecto_II_Datos_II GitHub Wiki
Backtracking
Este algoritmo consiste en probar distintas sequencias de decisiones hasta encontrar una que satisfaga las condiciones que se estén buscando. Con este algoritmo recursivo, se van probando y eliminando posibilidades hasta encontrar la solución o soluciones.
Pseudocódigo:
void findSolutions(n, other params) :
if (found a solution) :
solutionsFound = solutionsFound + 1;
displaySolution();
if (solutionsFound >= solutionTarget) :
System.exit(0);
return
for (val = first to last) :
if (isValid(val, n)) :
applyValue(val, n);
findSolutions(n+1, other params);
removeValue(val, n);
Pathfinding A*
Este algoritmo consiste en, por medio de mediciones para la ruta más corta, encontrar la mejor solución o una muy cercana. Con el uso del valor heurístico, se estima cuáles nodos son los más probables a encontrar la solución más óptima y con base a este heurístico y el costo real del camino recorrido.
OPEN //the set of nodes to be evaluated
CLOSED //the set of nodes already evaluated
add the start node to OPEN
loop
current = node in OPEN with the lowest f_cost
remove current from OPEN
add current to CLOSED
if current is the target node //path has been found
return
foreach neighbour of the current node
if neighbour is not traversable or neighbour is in CLOSED
skip to the next neighbour
if new path to neighbour is shorter OR neighbour is not in OPEN
set f_cost of neighbour
set parent of neighbour to current
if neighbour is not in OPEN
add neighbour to OPEN
Algoritmo genético
Este algoritmo esta inspirado en el proceso de seleccion natural que pertenece a la clase mas amplia de algoritmos evolutivos. Se utilizan para generar soluciones de alta calidad, optimizar y buscar soluciones de problemas basandonos en operadores biologicos como mutacion, seleccion, cruce, poblacion, etc. La evolución generalmente comienza a partir de una población de individuos generados aleatoriamente y es un proceso iterativo , con la población en cada iteración llamada generación . En cada generación, se evalúa la aptitud de cada individuo de la población. Los individuos más aptos se seleccionan estocásticamente de la población actual, y el genoma de cada individuo se modifica ( recombina y posiblemente muta al azar) para formar una nueva generación. La nueva generación de soluciones candidatas se utiliza luego en la siguiente iteración del algoritmo.. Por lo general, el algoritmo termina cuando se ha producido un número máximo de generaciones o se ha alcanzado un nivel de aptitud satisfactorio para la población.
typedef struct {
int genotipo[LONG_COD];
double aptitud;
} Individuo;
double fitness (double, double);
int generarBinario (void);
Individuo generarIndividuo (void);
Individuo * generarPoblacion (void);
Individuo * seleccionTorneos(Individuo * pob);
void mutacionHijos (Individuo *);
void cruzarSeleccion (Individuo *);
Individuo elite(Individuo *);
void imprimePoblacion (Individuo *);
void imprimeGenotipo(Individuo);