Algoritmo de marshall

Iniciado por verakra, 21 Marzo 2019, 04:56 AM

0 Miembros y 1 Visitante están viendo este tema.

verakra

he investigado y leido sobre el algoritmo pero no encuentro las manera de como implementarlo en C++, si alguien sabe su ayuda seria de mucha ayuda


K-YreX

Qué parte es la que no sabes implementar??
Y qué datos tienes para empezar la ejecución??
Aparte te recomiendo que insertes tu programa para ver los avances  :-X
Código (cpp) [Seleccionar]

cout << "Todos tenemos un defecto, un error en nuestro código" << endl;

verakra

no se ni como empezar , a implementar  ese algoritmo vi explicaciones de como hacerlo , pero no orientado para programarlo, osea que aprendi como hacerlo,, pero no como programarlo

K-YreX

Por lo que he leído es tener una matriz inicial e ir realizando una serie de operaciones con el fin de modificar alguno de los valores de esta. Si lo tienes hecho en papel, fíjate en las condiciones que se tienen que ir cumpliendo para tener una idea de cómo implementarlo.
Y estoy dando por hecho que ya conoces la matriz inicial.
Código (cpp) [Seleccionar]

cout << "Todos tenemos un defecto, un error en nuestro código" << endl;

Serapis

#4
Es un algoritmo relativamente sencillo de programar.
Se compone de dos partes:
- En la primera hay dos bucles anidados para rellenar la matriz (bidimensional) cuyo contenido se puede expresar como para cada nodo, la distancia desde dicho nodo a todos los otros (la distancia de un nodo a sí mismo, obviamente siempre será 0). Esta parte viene dado por los pesos de las aristas que unen dos nodos, luego según como se proporcione el origen de datos puedes venir prácticamente sin cambios de origen. Básicamente es una adaptación de los datos de entrada sobre un array bidimensional.

- En la segunda se utiliza dicha matriz en 3 bucles anidados. Los 2 primeros son un recorrido completo, en el 3 se trata de localizar el par menor que es el que se asigna. es decir siempre que se encuentra uno menor, se asigna... ahora la distancia a batir es la recién asignada (similar a la ordenación de burbuja que cuando encuentras uno menor, luego hay que seguir buscando uno menor que el ahora hallado menor).

Ahora para terminar de entenderlo toma lápiz y papel, situa 3 o 4 puntos, dales indices desde 0 a n-1... traza líneas de uno a otro, marca un valor de distancia en cada línea (no importa si es exacta o sini es aproximada, pero ayuda a entenderlo visualmente si dichos valores son aproximados).
Supongamos que tienes 4 puntos 0,1,2 y 3 de 2 a 3 la distancia es 25, el algoritmo, trata de verificar si existe una distancia más corta que 25 para llegar del punto 2 al 3, y cual es esa distancia, que es la que finalmente constará. Natualmente el algoritmo  es para todos los pares de puntos (no solo para uno), pero si primero tratas de generar un algoritmo para dados 1 par de puntos encontrar un acceso entre ellos con una distancia más corta que la directa entre ellos, el siguiente paso es añadir un bucle que envuelva a este para hacer lo mismo pero con cada par de puntos, no solo con un par.

Con esta aclaración y lo anterior debiera serte sencillo generar el algoritmo, es trivial, basta un poco de lógica...