Análisis correspondiente del algoritmo graph.
py:
En general, el principal problema de este algoritmo viene dada desde el principio
en el que se estructuro el problema,
puesto a que este algoritmo soluciona "grafos dirigidos" e incluso los soluciona de
manera ineficiente, siendo incapaz de solucionar grafos no dirigidos que es la meta
que debe cumplir.
Además, a la hora de ir ordenando con el algoritmo sort_graph, este le falta una
funcionalidad que logre guardar aquellos que tengan el mismo peso que la mitad,
ya que en estos momentos tal como está, va guardando de manera recursiva los
valores menores de la mitad hacia la izquierda y los valores mayores
de la mitad hacia la derecha, pero nunca hay una condición if que permita guardar
aquellos que tengan el mismo peso, perdiendo los en el proceso.
Otro problema es en search_objetive, este algoritmo toma el primer arreglo de
aristas que tenga el "objetivo" en su posición 1, por lo que realmente no está
buscando
el camino más corto o con menos peso, si no está encontrando el primer vértice
objetivo que encuentre y "no valora las demás posibilidades". Cabe recalcar que de
aquí
surge el problema de que solo pueda resolver grafos dirigidos, pero no para no
dirigidos, lo que toda la algoritmia implementada no va a cumplir aquella meta de
encontrar
la ruta más corta tomando cualquier vértice inicial y cualquier vértice final.
Y ya por último en la funcion bad_graph_algorithm, este algoritmo permite ir
conectando de manera recursiva los arreglos necesarios para ir haciendo el camino
total,
armando lo comenzando desde el nodo objetivo hasta el nodo inicial, camino que se
supone que debe ser el de menor peso, cosa que no se cumple puesto a que esta
función
escoge los caminos bajo un algoritmo search_objetive mal hecho, que escoge el
primero que encuentre ignorando todos los posibles caminos que puedan llegar a
tener un menor peso.
Mejoras propuestas e implementación de las mejoras:
Problema de los grafos no dirigidos solucionado:
Primero, se pensó en cómo se podría solucionar el problema de que pueda solucionar
grafos no dirigidos, puesto a que este es el principal problema, por lo que se
pensó en crear una función
llamada inicioDestino_invertido_mas_original(aristas) donde las aristas recibidas
desde el comienzo, se crean un doble de ellos donde el vértice destino va a ser el
vértice origen y el vértice
origen va a ser el vértice destino, creando así una lista aristas con mucha más
información sobre los posibles camino invertidos, en pocas palabras se transformó
la información de las aristas del
grafo dirigido a uno "no dirigido".
Problema del ordenamiento:
En el ordenamiento se decidió organizarlo de manera ascendente el número del
vértice inicial (posicion 0) de la lista aristas, implementadas en la función
sort_graph_firstPos(aristas) para que cuando se vaya
a buscar una arista que puede llegar a ser un posible camino, este lo haga mediante
un quicksort modificado (puesto a que necesita que el arreglo este ordenado), esta
es la necesidad, organizarlo para que el
quicksort modificado los encuentre de manera eficiente.
Problema de la búsqueda (quicksort modificado):
Este quicksort modificado en [Link] se llama
buscar_caminos(aristas,objetivo,c,f,visitados), donde aristas son la lista de
aristas ordenadas e interpretadas como un grafo no dirigido, el objetivo es el
vértice que
se está buscando, c es la posición inicial que se debe tomar en aristas, f es la
longitud final que se debe tomar en aristas y visitados permite no escoger aquellos
arreglos que tengan un vértice destino ya visitado anteriormente,
donde de manera recursiva logra encontrar todos los posibles caminos del vértice
objetivo no visitados de manera eficiente.
Problema de un algoritmo que pueda ir creando todos los posibles caminos existentes
para llegar al destino:
Esta sección se divide en tres funciones que trabajan conjuntamente para llevar a
cabo este proceso, estos son camino_corto(), armar_caminos_inicio() y
armar_caminos() sin olvidar que en estas
se usaron las demás funciones ya nombradas, primero se nombra
camino_corto(aristas,nodo_origen,nodo_destino,visitados), el cual tiene la función
de retornar el arreglo que representa el camino
más corto de todos los posibles caminos recibidos anteriormente por
armar_caminos_inicio(aristas,nodo_origen,nodo_destino,visitados), donde esta
función arma los primeros caminos encontrados comenzando desde
el nodo_origen, siendo la función muy importante para crear una base de donde se
van a comenzar a armar los caminos, luego de tenerlos, se los va a dar a una
función llamada armar_caminos(aristas,caminos,nodo_destino,visitados),
el cual, con esta base de los primeros caminos encontrados en la variable caminos,
va a comenzar a buscar nuevamente con buscar_caminos() los nuevos caminos de los
caminos iniciales, el cual no pueden estar ya visitados en la
lista visitados, hasta tal punto que de manera recursiva encuentren el
nodo_destino, ya en este punto, cuando todos los posibles caminos lo hayan
encontrado y se hayan eliminado en el transcurso del proceso aquellos que se
quedaban perdidos o atascados (sin posibles caminos),
se retornan ya todos los posibles caminos con un destino nodo ya cumplido, luego la
función armar_caminos_inicio() le va a pasar la información a camino_corto() y
siendo este último y a la vez el comienzo de todo, va a sumar
todos los pesos de todos los posibles caminos totales guardándolos de manera
individual en una lista y va a buscar cual tuvo el menor peso, siendo este el que
va a retornar y así, cumpliendo la meta.
