# Algoritmia/Algoritmo para la ubicación óptima

El algoritmo que se muestra a continuación nos da una idea del funcionamiento de un algoritmo voraz usado para ayudar a las empresas o multinacionales a ubicar óptimamente sus almacenes principales dependiendo de la ubicación de las ciudades destino y la cantidad de viajes que se deben hacer a cada una de esas ciudades.
Se muestra una implementación del algoritmo con una interfaz gráfica de usuario (GUI) en el lenguaje de programación Java.

## Descripción

Se trata de una empresa de transportes que debe realizar envíos a distintas ciudades y necesitamos encontrar una solución óptima que nos diga un sitio adecuado donde situar el almacén para evitar en cierta medida recorrer mas kilómetros de los necesarios sabiendo que todos los trayectos se realizan desde el almacén hasta la ciudad en cuestión y viceversa ya que debemos vaciar y llenar el camión. Se trata de encontrar las coordenadas para dicho almacén una vez conocidas las de las ciudades y el número de envíos a cada una de ellas. Las coordenadas se trataran como coordenadas reales, en este caso si las coordenadas fueran Oeste o Sur deben ser introducidas como números negativos. Se toma como referencia la coordenada (0,0) que es el corte del Meridiano de Greenwich con el Ecuador (como un plano cartesiano). Estas son las pruebas que debemos usar en el algoritmo.

## Limitaciones

1. La solución algorítmica mostrada en este artículo tiene un enfoque voraz y siempre da una solución óptima, pero su complejidad no depende de la cantidad de ciudades ingresadas, sino de que tan distantes estén dichas ciudades entre sí. A partir de esto concluimos que si se ingresan muchas ciudades cuyas coordenadas están muy próximas, el algoritmo será óptimo, pero si se ingresan pocas ciudades muy alejadas entre sí, el algoritmo será poco óptimo.
2. Las coordenadas de las ciudades siempre deben ser enteras, puesto que el algoritmo se basa en:la capacidad de enumeración de los números enteros.

## Solución

1. Se encuentran cuatro pares ordenados, los cuales forman un rectángulo que encierra todas las coordenadas de las ubicaciones de las ciudades. Estas cuatro coordenadas se hallan de la siguiente manera:
2. Se recorre cada coordenada contenida dentro del rectángulo hallando la suma de las distancias desde esta a cada ciudad y multiplicándola por la cantidad de envíos respectivos a cada una, y se compara con el mínimo resultado de las pruebas anteriores, de tal forma que al final de hacer el recorrido del rectángulo se va a tener la coordenada cuya suma de las distancias desde ella a todas las ciudades multiplicadas por sus respectivos envíos es la menor.
A continuación se muestra el código con implementación en java:

### Implementación del algoritmo
#### Clase Aplicación

    La clase Aplicación contiene el método principal del programa

#### Clase Ciudad

    La clase Ciudad nos abstrae las propiedades de ubicación, nombre y cantidad de envios a dicha ciudad

#### Clase Algoritmo

    La clase Algoritmo trae la implementación del algoritmo para la ubicación óptima

#### Clase ManejoException

    La clase ManejoException crea una Exception con la información dada en mensaje

#### Clase Tabla

    La clase Tabla crea una tabla abstracta reescribiendo algunos métodos para la conveniencia de la GUI.

#### Clase Ventana

    La clase Ventana crea una GUI con un JTable para ingresar las ciudades con sus respectivos datos.

## Complejidad Temporal

La complejidad de este algoritmo viene dada por dos factores, el primero es la cantidad de ciudades que son ingresadas y el segundo la amplitud del rectángulo que contiene todas las ubicaciones de las ciudades. Se podría observar que para cada punto contenido en el rectángulo se le halla la suma de las distancias a las ciudades multiplicadas por el respectivo número de envíos, y para hacer esta suma hay que recorrer todas las ciudades, por tanto la posible complejidad del algoritmo viene dada por:

## Pruebas

A continuación se muestran algunas pruebas que se le pueden hacer al algoritmo:

## Forma de Ejecución

Forma 1:
    Si tiene instalado java con un IDE como Eclipse o JCreator puede copiar las clases aquí vistas en un archivo con extensión '.java' y crear un proyecto y ejecutarlo desde allí.
    Para Eclipse, abra el entorno, entre a File, New, Proyect, le da un nombre y especifica un Package dentro del proyecto, a continuación entre a Windows, Show View, Package Explorer, para abrir una ventana donde aparece el proyecto, a dentro de este debe estar el Package especificado por usted, si no se encuentra, da click derecho sobre el proyecto y le dice New, Package, le da un nombre.
    A continuación con el click derecho sobre el Package creado le dice importar, elige la dirección donde se encuentran las clases y le da aceptar.
Luego busca la clase Aplicación dentro del Package, le da click derecho y run, java aplication.
Forma 2:
    Para poder compilar y ejecutar el programa debe tener instalado en su computador el JDK de Java 1.5 o mejores actualizaciones y además debe tener el path de Windows configurado con el jdk. Para configurar el path es necesario ir a Panel de Control-> Sistema->Variables de Entorno->Path->Modificar. A continuación agregue la ruta del jdk
Más sobre configuración del path
    Antes de comenzar tiene que copiar cada una de las clases en un bloc de notas separado y guardarlo con el mismo nombre de la clase y con extensión.java. Por ejemplo: al copiar la clase Algoritmo en un bloc de notas la guarda como AlgoritmoKurskal.java.
    Para compilar abra la consola, o para Windows XP la herramienta símbolo del sistema, estando allí diríjase al directorio donde tiene todas las clases guardadas (Todas las clases deben estar en el mismo directorio para que el programa corra correctamente) y enseguida copie el siguiente comando javac Aplicación.java, esto le dice a java que compile el main del programa que se encuentra en Aplicación.java. Si hace esto correctamente deben haberse creado en el directorio de las clases varios archivos .class, uno para cada clase y con el mismo nombre de la clase.
    Para ejecutar tiene que haber compilado primero. Nuevamente abra la consola, o símbolo del sistema, y diríjase al directorio donde se encuentran todas las clases y digite el siguiente comando java Aplicación, esto le dice a java que ejecute el main del programa. Si lo hace correctamente el programa debe estar corriendo.

## Conclusiones

1.El algoritmo tiene un enfoque voraz.
2.El algoritmo siempre da la solución óptima.
3.La complejidad no solo depende de la cantidad de ciudades ingresadas, también se debe tener en cuenta que tan distantes están las ciudades entre sí.

## Enlaces Internos

1.Algoritmo Voraz
2.Algoritmo de kruskal
3.Algoritmo de Prim