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
editarSe 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
editar1. 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
editar1. 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:
X1= la menor coordenada en x de todas las ubicaciones de las ciudades.
Y1= la mayor coordenada en y de todas las ubicaciones de las ciudades.
X2= X1.
Y2= la menor coordenada en y de todas las ubicaciones de las ciudades.
X3= la mayor coordenada en x de todas las ubicaciones de las ciudades.
Y3= Y1.
X4= X3.
Y4= Y2.
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
editarClase Aplicación
editar- La clase Aplicación contiene el método principal del programa
public class Aplicacion
{
public static void main (String args[])
{
Ventana ventana;
Coordinador coordinador;
Algoritmo algoritmo;
ventana=new Ventana();
coordinador=new Coordinador();
algoritmo=new Algoritmo();
ventana.setCoordinador(coordinador);
coordinador.setVentana(ventana);
coordinador.setAlgoritmo(algoritmo);
ventana.setVisible(true);
}
}
Clase Ciudad
editar- La clase Ciudad nos abstrae las propiedades de ubicación, nombre y cantidad de envios a dicha ciudad
public class Ciudad
{
// Variables que guardan las coordenadas de la ciudad.
int x = java.lang.Integer.MAX_VALUE, y = x;
// Variable que guardara el numero de envios que hay que realizar a esta
// ciudad.
int numeroEnvios = -1;
// Variable que guarda el nombre de la ciudad.
String nombre = "";
// Método que se encarga de pedir los datos de la ciudad
public Ciudad(String nombre,int x, int y, int numeroEnvios )
{
super();
this.x = x;
this.y = y;
this.numeroEnvios = numeroEnvios;
this.nombre = nombre;
}
public int getNumeroEnvios()
{
return numeroEnvios;
}
public int getX()
{
return x;
}
public int getY()
{
return y;
}
public String getNombre()
{
return nombre;
}
}
Clase Algoritmo
editar- La clase Algoritmo trae la implementación del algoritmo para la ubicación óptima
public class Algoritmo
{
Ciudad ciudades[];
// Variables que almacenaran las coordenadas limite del problema
int xInicial = java.lang.Integer.MAX_VALUE, yInicial = xInicial;
int xFinal = java.lang.Integer.MIN_VALUE, yFinal = xFinal;
// Variables que guardaran las coordenadas solucion encontradas.
int solucionX, solucionY;
float distanciaSolucion = java.lang.Float.MAX_VALUE;
public void calcularLimites()
{
for (int i = 0; i < ciudades.length; i++)
{
if (ciudades[i].getX() < xInicial)
{
xInicial = ciudades[i].getX();
}
if (ciudades[i].getY() < yInicial)
{
yInicial = ciudades[i].getY();
}
if (ciudades[i].getX() > xFinal)
{
xFinal = ciudades[i].getX();
}
if (ciudades[i].getY() > yFinal)
{
yFinal = ciudades[i].getY();
}
}
}
// Método que se encarga de hallar distancias
public float calcularDistancia(int x, int y)
{
float distancia = 0;
for (int i = 0; i < ciudades.length; i++)
{
distancia += ((Math.sqrt(Math.pow(x - ciudades[i].getX(), 2) + Math.pow(y - ciudades[i].getY(), 2))) * ciudades[i].getNumeroEnvios());
}
return distancia;
}
public Ciudad situarAlmacen(Ciudad[] ciudades)
{
this.ciudades = ciudades;
calcularLimites();
for (int i = xInicial; i <= xFinal; i++)
{
for (int j = yInicial; j <= yFinal; j++)
{
float distanciaActual = calcularDistancia(i, j);
if (distanciaSolucion > distanciaActual)
{
distanciaSolucion = distanciaActual;
solucionX = i;
solucionY = j;
}
}
}
return new Ciudad("Solucion", solucionX, solucionY, 0);
}
public void inicializar()
{
xInicial = java.lang.Integer.MAX_VALUE;
yInicial = xInicial;
xFinal = java.lang.Integer.MIN_VALUE;
yFinal = xFinal;
distanciaSolucion = java.lang.Float.MAX_VALUE;
}
}
Clase Coordinador
editar:La clase Coordinador coordina la [[interfaz]] con los algoritmos
public class Coordinador
{
Ventana ventana;
Algoritmo algoritmo;
public void setAlgoritmo(Algoritmo algoritmo)
{
this.algoritmo = algoritmo;
}
public void setVentana(Ventana ventana)
{
this.ventana = ventana;
}
public void evento_aplicarAlgoritmo()
{
Ciudad []ciudades=ventana.obtenerCiudades();
Ciudad ciudadSolucion;
if(ciudades!=null)
{
algoritmo.inicializar();
ciudadSolucion=algoritmo.situarAlmacen(ciudades);
ventana.getLabelSolucion().setText("Solucion: X= "+ciudadSolucion.getX()
+" Y= "+ciudadSolucion.getY());
}
}
}
Clase ManejoException
editar- La clase ManejoException crea una Exception con la información dada en mensaje
public class ManejoException extends Exception
{
String men;
public ManejoException(String mensaje)
{
men=mensaje;
}
public String getMessage()
{
return men;
}
}
Clase Tabla
editar- La clase Tabla crea una tabla abstracta reescribiendo algunos métodos para la conveniencia de la GUI.
import javax.swing.table.AbstractTableModel;
public class Tabla extends AbstractTableModel
{
int col = 1, fil = 1, i = 0;
Object[][] datos;
String[] nombres;
public boolean isCellEditable(int fil, int col)
{
if (col == 0)
return false;
else
return true;
}
public Object getValueAt(int fil, int col)
{
return datos[fil][col];
}
public int getColumnCount()
{
return nombres.length;
}
public int getRowCount()
{
return datos.length;
}
public String getColumnName(int col)
{
return nombres[col];
}
public void setValueAt(Object dato, int fil, int col)
{
datos[fil][col] = dato;
}
public void cambiarCantidadFilas(int fil)
{
this.fil = fil;
datos = new String[fil][col];
}
public void cambiarCantidadColumnas(int col)
{
this.col = col;
datos = new String[fil][col];
nombres = new String[col];
}
public void añadirNombre(String nombre)
{
nombres[i] = nombre;
i++;
}
public void inicializar()
{
fil = 0;
datos = new String[fil][col];
}
}
Clase Ventana
editar- La clase Ventana crea una GUI con un JTable para ingresar las ciudades con sus respectivos datos.
import java.awt.Dimension;
import java.awt.Toolkit;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.util.Vector;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JLabel;
import javax.swing.JOptionPane;
import javax.swing.JScrollPane;
import javax.swing.JTable;
import javax.swing.JTextField;
public class Ventana extends JFrame implements ActionListener
{
JTable tabla;
Tabla abTabla;
JScrollPane barra;
JTextField campoCantidad;
JLabel labelCantidad,labelSolucion;
JButton botonCantidad, botonHallarSolucion;
Vector<String> nombres;
Coordinador coordinador;
int cantidad;
public Ventana()
{
setLayout(null);
labelCantidad = new JLabel("Cantidad De Ciudades");
campoCantidad = new JTextField();
botonCantidad = new JButton("Ingresar");
abTabla = new Tabla();
labelSolucion=new JLabel("Solucion: ");
botonHallarSolucion = new JButton("Hallar Solucion");
abTabla.cambiarCantidadColumnas(5);
abTabla.añadirNombre("#");
abTabla.añadirNombre("Nombre");
abTabla.añadirNombre("CooX");
abTabla.añadirNombre("CooY");
abTabla.añadirNombre("Envios");
tabla = new JTable(abTabla);
tabla.setEnabled(true);
cambiarTamañoTabla(10);
tabla.getColumn("#").setMinWidth(20);
tabla.getColumn("#").setPreferredWidth(20);
tabla.getColumn("#").setPreferredWidth(20);
barra = new JScrollPane();
barra.setViewportView(tabla);
tabla.getTableHeader().setReorderingAllowed(false);
labelCantidad.setBounds(20, 40, 140, 20);
campoCantidad.setBounds(160, 40, 50, 20);
botonCantidad.setBounds(220, 40, 100, 20);
barra.setBounds(20, 100, 300, 230);
labelSolucion.setBounds(20,340,500,20);
botonHallarSolucion.setBounds(110, 370, 120, 20);
add(labelCantidad);
add(campoCantidad);
add(botonCantidad);
add(barra);
add(labelSolucion);
add(botonHallarSolucion);
setTitle("Ubicacion optima de un almacen");
setSize(350, 450);
botonCantidad.addActionListener(this);
botonHallarSolucion.addActionListener(this);
Dimension screenSize = Toolkit.getDefaultToolkit().getScreenSize();
setLocation((screenSize.width - 350) / 2, (screenSize.height - 500) / 2);
setDefaultCloseOperation(EXIT_ON_CLOSE);
}
public void actionPerformed(ActionEvent evento)
{
if (evento.getSource() == botonCantidad)
{
try
{
int cantidad = Integer.parseInt(campoCantidad.getText());
if (campoCantidad.getText().contains(".") ||
campoCantidad.getText().contains("-"))
throw new ManejoException("La cantidad de ciudades tiene que
ser un numero\nno negativo ni decimal");
cambiarTamañoTabla(cantidad);
barra.repaint();
}
catch (NumberFormatException e)
{
JOptionPane.showMessageDialog(null, "La cantidad de ciudades tiene
que ser un numero\nno negativo ni decimal");
}
catch (ManejoException e)
{
JOptionPane.showMessageDialog(null, e.getMessage());
}
}
else
{
coordinador.evento_aplicarAlgoritmo();
}
}
private void cambiarTamañoTabla(int cantidad)
{
this.cantidad = cantidad;
abTabla.cambiarCantidadFilas(cantidad);
for (int i = 0; i <cantidad; i++)
abTabla.setValueAt("" + (i + 1), i, 0);
tabla.setVisible(false);
tabla.setVisible(true);
}
public Ciudad[] obtenerCiudades()
{
int x, y, envios,i=0;
Ciudad[] ciudades = new Ciudad[cantidad];
nombres=new Vector(0,1);
try
{
for (i = 0; i < cantidad; i++)
{
if (((String) tabla.getValueAt(i, 1))==null)
throw new ManejoException("Tiene que ingresar el nombre de la
ciudad");
x = Integer.parseInt((String) tabla.getValueAt(i, 2));
y = Integer.parseInt((String) tabla.getValueAt(i, 3));
envios = Integer.parseInt((String) tabla.getValueAt(i, 4));
if (nombres.contains((String) tabla.getValueAt(i, 1)))
throw new ManejoException("hay nombres de ciudades
repetidos");
if (((String) tabla.getValueAt(i, 2)).contains("."))
throw new ManejoException("Tiene que ingresar un numero no
decimal\nError fila: "+i+" col: "+2);
if (((String) tabla.getValueAt(i, 3)).contains("."))
throw new ManejoException("Tiene que ingresar un numero no
decimal\nError fila: "+i+" col: "+3);
if (((String) tabla.getValueAt(i, 4)).contains(".") || ((String)
tabla.getValueAt(i, 4)).contains("-"))
throw new ManejoException("Tiene que ingresar un numero no
negativo ni decimal\nError fila: "+i+" col: "+4);
nombres.add((String) tabla.getValueAt(i, 1));
ciudades[i] = new Ciudad((String) tabla.getValueAt(i, 1), x, y,
envios);
}
return ciudades;
}
catch (NumberFormatException e)
{
JOptionPane.showMessageDialog(null, "Tiene que ingresar un numero\nError
fila: "+i);
}
catch (ManejoException e)
{
JOptionPane.showMessageDialog(null, e.getMessage());
}
return null;
}
public JTable getTabla()
{
return tabla;
}
public int getCantidad()
{
return cantidad;
}
public void setCoordinador(Coordinador coordinador)
{
this.coordinador = coordinador;
}
public JScrollPane getBarra()
{
return barra;
}
public JLabel getLabelSolucion()
{
return labelSolucion;
}
}
Complejidad Temporal
editarLa 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:
X1= la menor coordenada en x de todas las ubicaciones de las ciudades.
Y1= la menor coordenada en y de todas las ubicaciones de las ciudades.
X2= la mayor coordenada en x de todas las ubicaciones de las ciudades.
Y2= la mayor coordenada en y de todas las ubicaciones de las ciudades.
N= la cantidad de ciudades.
T (N)= ( X2 – X1 ) * ( Y2 – Y1 ) * N
Pruebas
editarA continuación se muestran algunas pruebas que se le pueden hacer al algoritmo:
Forma de Ejecución
editarForma 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
Por ejemplo si el path anterior era:
%SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem; C:\Archivos de programa\Intel\DMIX
el path modificado deberá quedar:
%SystemRoot%\system32;%SystemRoot%;%SystemRoot%\System32\Wbem; C:\Archivos de programa\Intel\DMIX; C:\Archivos de programa\Java\jdk1.6.0\bin
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
editar1.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í.