¡Son muy similares y a menudo se confunden! La diferencia entre Prim y el vecino más cercano se puede resumir implementando ambos:
Prim en un gráfico para encontrar el árbol de expansión mínimo:
- Comience en cierto vértice
- Elija el vértice no visitado más cercano (repetir)
- Esto se puede elegir de cualquier vértice que haya visitado
- Termina cuando todos los vértices han sido visitados
Vecino más cercano cuando se usa para soluciones TSP:
- Cómo elegir el algoritmo de selección de funciones correcto
- ¿Qué esfuerzos hará para crear un gráfico de la estructura de datos básicos, que también puede ser entendido por una persona no técnica?
- Cómo escribir una matriz de distancia para el algoritmo Bellman Ford
- ¿Cómo va a hacer que me gusten y me interesen los algoritmos (programación)?
- ¿Se puede demostrar que es imposible volver a un entero inicial mayor que uno si aplica un algoritmo de multiplicar por tres y agregar uno cuando es impar y dividir por dos si es par?
- Comience en cierto vértice
- Elija el vértice no visitado más cercano (repetir)
- Esto solo se puede elegir del vértice en el que se encuentra actualmente
- Regrese al inicio cuando se hayan visitado todos los vértices
Entonces, la principal diferencia es que en el vecino más cercano solo puede expandir su selección desde los vértices conectados inmediatamente al que se encuentra actualmente, mientras que en Prim’s puede expandir su selección desde cualquier vértice que ya haya visitado.
También debe tenerse en cuenta que en el caso de D2 del que creo que está hablando, el vecino más cercano solo se usa para mejorar los límites de la solución de TSP, por lo que debe encontrar una ruta para volver a comenzar.
Espero haber ayudado 🙂
No dude en pedir ayuda si desea ver cómo funciona esto en una matriz de adyacencia.
