Tarea: Definicion del vecino mas próximo
El algoritmo del vecino más próximo fue, en las ciencias de la computación, uno de los primeros algoritmos utilizados para determinar una solución para el problema del viajante. Este método genera rápidamente un camino corto, pero generalmente no el ideal.
Abajo está la aplicación del algoritmo del vecino más próximo al problema del viajante.
Estos son los pasos del algoritmo:
- elección de un vértice arbitrario respecto al vértice actual.
- descubra la arista de menor peso que ya este conectada al vértice actual y a un vértice no visitado V.
- convierta el vértice actual en V.
- marque V como visitado.
- si todos los vértices del dominio estuvieran visitados, cierre el algoritmo.
- vaya al paso 2.
La secuencia de los vértices visitados es la salida del algoritmo.
El algoritmo del vecino más próximo es fácil de implementar y ejecutar rápidamente, pero algunas veces puede perder rutas más cortas, que son fácilmente notadas con la visión humana, debido a su naturaleza más "ávida". Como norma general, si los últimos pasos del recorrido son comparables en longitud al de los primeros pasos, el recorrido es razonable; si estos son mucho mayores, entonces es probable que existan caminos mucho mejores.
Primera etapa :
Con una distancia dij podemos evaluar la disimilaridad entre los objetos a clasificar. Podemos crear una tabla D(n,n), simétrica, que resume las distancias entre los n objetos a clasificar, comparados dos a dos.
Suponemos que es aceptable considerar que la distancia entre dos clases que contienen un solo objeto cada una es igual a la distancia entre los objetos: d({x},{y}) = d(x,y) "x, yÎI.Los términos diagonales de D(n,n) son nulos, puesto que, si dij es una distancia :d({x},{x}) = d(x,x) = 0 "xÎI
Segunda etapa :
Buscamos en la tabla D(n,n) el término extra-diagonal mínimo, es decir el valor d({x},{y}) = d(x,y) mínimo. Formamos una nueva clase que reagrupa esos dos objetos: {x} y {y}.
Iteración :
Se recomienza a partir de la primera etapa, pero ahora sólo con n - 1 objetos a comparar, puesto que una clase contiene ahora dos objetos. Para calcular la Tabla D’(n-1, n-1) correspondiente a la nueva situación debemos darnos un criterio para calcular la distancia entre una clase que contiene dos objetos y las clases restantes que sólo contienen un objeto. La estrategia de agregación responde a ese problema...La estrategia del «vecino más cercano» consiste en elegir como distancia entre la clase{x;y} y la clase {k} la más pequeña de las dos distancias siguientes: d({x},{k}) o bien d({y},{k}). En cada etapa t de iteración del proceso de agregación por el método del «vecino más cercano», la Tabla D(n-t, n-t) es construida con la siguiente distancia ultramétrica.
Ventaja del método : simplicidad de cálculo. No requiere el
cálculo de la matriz Dt(n-t, n-t) en
cada etapa de agregación.
4 Inconveniente del método : tiene tendencia a producir un
«efecto de encadenamiento»
Ejemplo
Un repartidor de mercancías tiene encargos en varias ciudades, las cuales se representan A-B-C-D-E, y debe iniciar en la cuidad A
¿Qué ruta debe seguir para que el costo sea mínimo?
Las distancias son:
A-B=7 A-E=20 B-E=11 D-E=17
A-C=9 B-C=10 C-D=15
A-D=8 B-D=4 C-E=5
El problema se puede solucionar por fuerza bruta o utilizado heurística entre otras
Solución por fuerza bruta:
*Checamos los caminos posibles:
Ahora vamos a eliminar lo inversos, así ahorramos tiempo.
Estos son los caminos que nos quedaron después de eliminar los inversos y sustituyendo los valores de las distancias dadas.
A-B-D-C-E-A=7+4+15+5+20=51
A-B-D-E-C-A=7+4+17+5+9=42
A-B-C-D-E-A=7+10+15+17+20=69
A-B-E-D-C-A= 7+11+17+15+9=59
A-D-C-B-E-A=8+15+10+11+20=64
A-D-C-E-B-A=8+15+5+11+7=46
A-D-E-B-C-A=8+17+11+10+9=55
A-D-E-C-B-A=8+17+5+10+7=47
A-D-B-C-E-A=8+4+10+5+20=47
A-D-B-E-C-A=8+4+11+5+9=37
A-C-D-B-E-A=9+15+4+11+20=59
A-C-B-D-E-A=9+10+4+17+20=60
Como nos podemos dar cuenta el más optimo es el de 37 kilómetros de distancia.
Ahora lo hacemos por medio del vecino más cercano.
De la cuidad A es más corto digerirse hacia la cuidad B y de la cuidad B dirigirse hacia la cuidad D y de la D a la C y de la C hacia la E y de la E regresarse hacia la cuidad.
Checando la solución de fuerza bruta y el resultado que nos dio ahora nos damos cuenta que no es lo mas optimo, sin embrago con la heurística es muchísimo mas rápido de solucionar el problema.