El algoritmo de inserción más cercano
El algoritmo de inserción más cercano es un algoritmo heurístico utilizado para encontrar una solución aproximada al problema del vendedor (TSP). El TSP tiene como objetivo encontrar la ruta más corta posible que visita cada ciudad (nodo) exactamente una vez y regresa a la ciudad inicial.
Cómo funciona:
1. Inicialización:
- Comience con un nodo arbitrario como el recorrido inicial (por ejemplo, un bucle de nodo único). Llamemos a este nodo `start_node`.
- Sea `v` el conjunto de nodos que aún no se han agregado al recorrido.
2. iteración:
- Encuentra el nodo más cercano: Para cada nodo `i` en la gira actual, encuentre el nodo` j` en `v` (el conjunto de nodos no visitados) que está más cerca de` i` (es decir, tiene la distancia más pequeña). Este nodo "más cercano" `J` es el que queremos insertar. Matemáticamente, estamos encontrando:
`j =argmin_ {v ∈ V} min_ {i ∈ Tour} dist (i, v)`
- Inserte el nodo más cercano: Encuentre el borde (i, k) en la gira actual donde insertar el nodo `j` entre nodos` i` y `k` da como resultado el aumento más pequeño de la gira. Es decir, encuentre `i` y 'k` tal que:
`Dist (i, j) + dist (j, k) - dist (i, k)` se minimiza.
- Inserte el nodo `j` entre nodos` i` y `k`, reemplazando efectivamente el borde (i, k) con dos bordes (i, j) y (j, k).
- Eliminar el nodo `j` del conjunto de nodos no visitados` v`.
3. Terminación:
- Repita el paso 2 hasta que todos los nodos se hayan agregado al recorrido (es decir, 'V` está vacío).
4. Cerrar el bucle:
- Conecte el último nodo agregado al recorrido al `start_node` para completar el ciclo.
Ejemplo:
Digamos que tenemos ciudades A, B, C, D y E con las siguientes distancias:
`` `` ``
A B C D E
A 0 10 15 20 25
B 10 0 35 25 30
C 15 35 0 30 20
D 20 25 30 0 10
E 25 30 20 10 0
`` `` ``
1. Inicio: Comencemos con el nodo A como la gira inicial:`tour ={a}`
2. iteración 1:
- El nodo más cercano a A es B (Distancia 10).
-Inserte B en el tour (A -> B -> A). `Tour ={a, b, a}`
3. iteración 2:
- Encuentre el nodo no visitado más cercano a cualquier nodo en la gira actual:
- Más cercano a A:C (15), D (20), E (25)
- Más cercano a B:C (35), D (25), E (30)
- El mínimo de estas distancias es 15 (A a C).
- Encuentra dónde insertar C.
- Insertar C entre A y B:15 + 35 - 10 =40
- Insertar C entre B y A:35 + 15 - 10 =40
- Inserte C entre A y B (o B y A). `Tour ={a, c, b, a}`
4. iteración 3:
- Encuentre el nodo no visitado más cercano:
- Más cercano a A:D (20), E (25)
- Más cercano a C:D (30), E (20)
- Más cercano a B:D (25), E (30)
- La distancia mínima es 20 (C a E o A a D). Llevemos C a E.
- Insertar E:
- Insertar E entre A y C:25 + 20 - 15 =30
- Insertar E entre C y B:20 + 30 - 35 =15 (¡mínimo!)
- Insertar E entre B y A:30 + 25 - 10 =45
- Inserte E entre C y B. `Tour ={a, C, E, B, A}`
5. iteración 4:
- Solo queda el nodo D.
- Más cercano a A:D (20)
- Más cercano a C:D (30)
- Más cercano a E:D (10) (¡mínimo!)
- Más cercano a B:D (25)
- Insertar D:
- Insertar D entre A y C:20 + 30 - 15 =35
- Insertar D entre C y E:30 + 10 - 20 =20
- Insertar D entre E y B:10 + 25 - 30 =5 (¡mínimo!)
- Insertar D entre B y A:25 + 20 - 10 =35
- Insertar D entre E y B. `Tour ={A, C, E, D, B, A}`
aspectos de optimización (o más bien, aproximación):
El algoritmo de inserción más cercano se optimiza al agregar iterativamente el nodo que introduce el aumento inmediato más pequeño en la longitud total del recorrido en cada paso. Este es un enfoque codicioso, lo que significa que es la mejor opción en cada etapa sin considerar el impacto global de esa elección.
* localidad: El algoritmo se centra en minimizar las distancias locales. Selecciona el nodo que está más cerca del recorrido actual, con el objetivo de mantener el segmento adicional del recorrido lo más corto posible.
* Crecimiento incremental: El recorrido se construye de forma incremental agregando un nodo a la vez. Cada decisión de inserción se basa en el estado actual de la gira, por lo que no planea ver cómo agregar un nodo específico podría afectar las inserciones futuras.
Limitaciones:
* No es óptimo: El algoritmo de inserción más cercano es un heurístico, lo que significa que no garantiza la ruta más corta absoluta. Puede atascarse en Optima Local, donde una elección temprana ligeramente diferente podría conducir a una solución general significativamente mejor.
* Naturaleza codiciosa: La naturaleza codiciosa del algoritmo puede conducir a elecciones subóptimas, especialmente en los casos en que las distancias no son uniformes. A veces, elegir un nodo un poco más al principio puede abrir oportunidades para conexiones más cortas más tarde.
* Dependencia del nodo inicial: El nodo inicial puede afectar la gira final. Diferentes nodos iniciales pueden dar lugar a diferentes rutas.
Ventajas:
* simple de implementar: Es relativamente fácil de entender e implementar.
* rápido: Generalmente es más rápido que los algoritmos que garantizan soluciones óptimas (como la búsqueda de fuerza bruta). La complejidad del tiempo es típicamente o (n^2), donde n es el número de nodos.
* Aproximación razonable: Por lo general, proporciona una aproximación razonablemente buena de la gira TSP óptima, especialmente cuando las distancias satisfacen la desigualdad del triángulo (es decir, la distancia directa entre dos puntos siempre es menor o igual a la suma de las distancias a lo largo de cualquier otra ruta).
En resumen:
El algoritmo de inserción más cercano es una heurística codiciosa que construye un recorrido en TSP al agregar repetidamente el nodo no visitado más cercano al recorrido existente. Aunque no se garantiza producir la solución óptima, es una forma rápida y simple de encontrar una aproximación razonablemente buena. Se centra en minimizar los aumentos de la distancia local en cada paso.